pre order in order postorder
时间: 2024-06-18 17:03:58 浏览: 11
preorder、inorder、postorder是二叉树遍历的三种方式。其中,遍历是指按照某种规则,依次访问树中的每一个节点,且每个节点仅被访问一次。下面是这三种遍历方式的具体介绍:
1. preorder(先序遍历):先访问根节点,再访问左子树,最后访问右子树。
2. inorder(中序遍历):先访问左子树,再访问根节点,最后访问右子树。
3. postorder(后序遍历):先访问左子树,再访问右子树,最后访问根节点。
这三种遍历方式在不同的场合下都有其应用,比如先序遍历可以用于构建表达式树,中序遍历可以用于二叉搜索树的中序遍历得到升序序列,后序遍历可以用于二叉树的后序表达式计算。同时,这三种遍历方式也是算法面试中常考的知识点。
相关问题
The inorder sequence of a binary tree is ABCDEFG, and its postorder sequence is BDCAFGE, so its pre-order sequence is ( ).
The answer to your question is: ABDECFG.
To obtain the pre-order sequence, we need to start with the root node (which is A in this case), then traverse the left subtree, and finally traverse the right subtree.
From the inorder sequence, we know that the left subtree contains nodes B, C, D, and the right subtree contains nodes E, F, G.
From the postorder sequence, we know that the last node is the root node (which is G in this case), and the second-to-last node is the rightmost node in the left subtree (which is F).
Using this information, we can construct the pre-order sequence as follows:
1. Start with the root node A
2. Traverse the left subtree, which has root node B
3. Traverse the left subtree of B, which has root node D
4. Traverse the right subtree of D, which is empty
5. Return to B and traverse its right subtree, which has root node C
6. Return to A and traverse its right subtree, which has root node E
7. Traverse the left subtree of E, which is empty
8. Traverse the right subtree of E, which has root node F
9. Traverse the right subtree of F, which is empty
10. Traverse the right subtree of G, which is empty
Thus, the pre-order sequence is ABDECFG.
PThreadNode pre; void PreOrder(ThreadTree& T) { if (T == NULL) return; else { visit(T); if (T->ltag == 0) PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(ThreadTree& T) { if (T == NULL) return; else { InOrder(T->lchild); visit(T); InOrder(T->rchild); } } void PostOrder(ThreadTree& T) { if (T == NULL) return; else { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } } void visit(PThreadNode& T) { cout << T->data << " "; if (T->lchild == NULL) { T->lchild = pre; T->ltag = 1; } if (pre != NULL && pre->rchild == NULL) { pre->rchild = T; pre->rtag = 1; } pre = T; } PThreadNode createTreeNode(Elemtype data) { PThreadNode p = new ThreadNode; p->data = data; p->lchild = nullptr; p->rchild = nullptr; p->rtag = 0; p->ltag = 0; return p; }
这段代码实现了将普通二叉树转化为线索二叉树的过程,其中 pre 是一个全局变量,用于记录上一个被访问的节点。具体实现过程如下:
1. PreOrder 函数先访问当前节点,然后分别递归遍历左子树和右子树。
2. InOrder 函数先递归遍历左子树,然后访问当前节点,最后递归遍历右子树。
3. PostOrder 函数先递归遍历左子树和右子树,最后访问当前节点。
4. visit 函数实现了对当前节点的访问,具体包括输出节点的值以及线索化左右子树。如果当前节点的左子树为空,则将其左孩子线索化为 pre;如果 pre 的右孩子为空,则将其右孩子线索化为当前节点。最后将 pre 更新为当前节点,以备下一次访问使用。
5. createTreeNode 函数用于创建新节点,初始化时左右孩子均为空,线索标志位均为 0。
需要注意的是,线索化后的二叉树可以通过线索遍历来实现不需要递归的遍历操作,可以大大提高遍历的效率。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)