（精）二叉树的周游.ppt

5.2.1 抽象数据类型 在二叉树的抽象数据类型中，定义了二叉树基本操作的集合，在具体应用中可以以此为基础进行扩充 为了强调抽象数据类型与存储无关，在此并没有具体规定该抽象数据类型的存储方式 5.2.2 深度优先周游二叉树 5.2.2 深度优先周游二叉树 基于二叉树的递归定义，这三种深度优先周游的递归定义 (1) 前序法(tLR次序，preorder traversal)。其递归定义是 访问根结点； 按前序周游左子树； 按前序周游右子树。 (2) 中序法(LtR次序，inorder traversal)。其递归定义是 按中序周游左子树； 访问根结点； 按中序周游右子树。 (3) 后序法(LRt次序，postorder traversal)。其递归定义是 按后序周游左子树； 按后序周游右子树； 访问根结点。 5.2.2 深度优先周游二叉树 深度周游如下二叉树 前序序列是：A B D E G C F H I 中序序列是：D B G E A C H F I 后序序列是：D G E B H I F C A 5.2.2 深度优先周游二叉树 二叉树的周游算法与表达式的“前缀”和“后缀”表示法之间有着密切的联系。例如图5.6是表达式A+B×(C+D)的二叉树表示。按照前序方式周游，运算符出现在前面，参与运算的对象紧跟在其后，这样就形成了前缀表达式（波兰式）： + A × B + C D 按照中序方式周游，得到的结果是去掉括号的中缀表达式： A + B × C + D 下面是后序方式周游的结果，得到的是后缀表达式（逆波兰式）： A B C D + × + 先序遍历递归算法 【算法5.3】 深度优先周游二叉树或其子树 templateclass T void BinaryTreeT::PreOrder (BinaryTreeNodeT *root) { // 前序周游二叉树或其子树 if (root != NULL) { Visit(root-value()); // 访问当前结点 PreOrder(root-leftchild()); // 前序周游左子树 PreOrder(root-rightchild()); // 前序周游右子树 } } 先序遍历的非递归实现 先序遍历的非递归实现 先序遍历的非递归实现 templateclass T void BinaryTreeT::PreOrderWithoutRecursion(BinaryTreeNodeT *root) { using std::stack; // 使用STL中的栈 stackBinaryTreeNodeT* aStack; BinaryTreeNodeT *pointer = root; aStack.push(NULL); // 栈底监视哨 while (pointer) { // 或者!aStack.empty() Visit(pointer-value()); // 访问当前结点 if (pointer-rightchild() != NULL) // 非空右孩子入栈 aStack.push(pointer-rightchild()); if (pointer-leftchild() != NULL) pointer = pointer-leftchild(); // 左路下降 else { // 左子树访问完毕，转向访问右子树 pointer=aStack.top(); // 获得栈顶元素 aStack.pop(); // 栈顶元素退栈 } } } 中序遍历