Chapter 5 RECURSION I1. Introduction to Recursion 2. Principles of Recursion L3 Backtracking: Postponing the Work 4. Tree-Structured Programs Look-Ahead in games I5. Pointers and Pitfalls
Chapter 5 RECURSION 1. Introduction to Recursion 2. Principles of Recursion 3. Backtracking: Postponing the Work 4. Tree-Structured Programs: Look-Ahead in Games 5. Pointers and Pitfalls
5.1 Stacks and Trees Stack DIDID space AAALALAALA DIDIDIDID 团团的门 data Time 数据结构是递归的 Start +- Finish
5.1 Stacks and Trees 数据结构是递归的
THEOREM 5.1 During the traversal of any tree, vertices are added to or deleted from the path back to the root in the fashion of a stack. Given any stack, conversely, a tree can be drawn to portray the life history of the stack, as items are pushed onto or popped from it
THEOREM 5.1 During the traversal of any tree, vertices are added to or deleted from the path back to the root in the fashion of a stack. Given any stack, conversely, a tree can be drawn to portray the life history of the stack, as items are pushed onto or popped from it
Tree-Diagram Definitions o The circles in a tree diagram are called vertices or nodes o The top of the tree is called its root o the vertices immediately below a given vertex are callled the children of that vertex The(unique vertex immediately above a given vertex is called its parent. The root is the only vertex in the tree that has no parent 分支 ◆Th兄第 ting a vertex with one immed ately above or below is called a branch. 9 Siblings are vertices with the same parent
Tree-Diagram Definitions The circles in a tree diagram are called vertices or nodes. The top of the tree is called its root. The vertices immediately below a given vertex are called the children of that vertex. The (unique) vertex immediately above a given vertex is called its parent. (The root is the only vertex in the tree that has no parent.) The line connecting a vertex with one immediately above or below is called a branch. Siblings are vertices with the same parent. 分支 兄弟
9 A vertex with no children is called a leaf or an externa/ vertex Two branches of a tree are adjacent if the lower vertex of the first branch is the upper vertex of the second. a sequence of branches in which each is adjacent to its successor is called a path. o The height of a tree is the number of vertices on a longest possible path from the root to a leaf. (Hence a tree containing only one vertex has height 1.) The depth or level of a vertex is the number of branches on a path from the root to the vertex
A vertex with no children is called a leaf or an external vertex. Two branches of a tree are adjacent if the lower vertex of the first branch is the upper vertex of the second. A sequence of branches in which each is adjacent to its successor is called a path. The height of a tree is the number of vertices on a longest possible path from the root to a leaf. (Hence a tree containing only one vertex has height 1.) The depth or level of a vertex is the number of branches on a path from the root to the vertex