数据结构-树速通指南( 三 ) _中序遍历

(3).后序遍历
后序遍历就是先访问左右子节点，“后”访问当前节点。
其动图如下：
其代码如下：
void Postorder_traversal(Node *n){Postorder_traversal(n->leftchild);Postorder_traversal(n->rightchild);cout << n->data;//访问该节点}
到现在你就可以发现，前中后遍历的递归代码是一样的，唯一不同的就是访问当前节点的先后次序，先访问就是先序，中间访问就是中序，最后访问就是后序。
(4).层次遍历
层次遍历顾名思义就是一层一层的遍历节点，具体方法用队列实现，这里请前往[数据结构-队列速通指南](
)对应部分讲解
(5).已知两种遍历次序求特定遍历次序
对于这种问题的主要思想就是首先要了解不同的遍历方式对应的次序差异，例如先序遍历由于每次都是从根结点开始访问的，所以先序遍历的次序总是第一个为根结点。同样的中序遍历就是访问根节点左边的就是其左孩子，右边的就是右孩子。而后序遍历就是最后一个为根结点。所以一般情况下分为两种：1.已知前序中序求后序 2.已知后序中序求前序。
而在知道这些以后该怎么求呢？其思路如下：
已知前序中序求后序 { 1. 找到前序遍历第一个结点为根结点。2. 找到中序遍历的根结点位置，左边为左子树，右边为右子树 3. 再继续对左右子树重复上述步骤。已知前序中序求后序 \begin{cases} 1.找到前序遍历第一个结点为根结点。\\ 2.找到中序遍历的根结点位置，左边为左子树，右边为右子树\\ 3.再继续对左右子树重复上述步骤。\end{cases} 已知前序中序求后序??????1.找到前序遍历第一个结点为根结点。2.找到中序遍历的根结点位置，左边为左子树，右边为右子树3.再继续对左右子树重复上述步骤。?
已知后序中序求先序同理。
三.用c++中STL库搭建树
STL库中并没有直接用来建各种类型树的容器（某些树除外），所以我们用来优化树结构，以解决静态数组的不足，以达到更加方便存储子节点和遍历的目的。
直接上代码：
//因为STL是c++独有，所以会逐步往c++方向的代码靠齐class Tree{int Data;//存储数据vector child;//用动态数组存储子节点static void insert(Tree *par,int Data){//插入节点shared_ptr n(new Tree);//建立新节点n->Data = http://www.kingceram.com/post/Data;//录入数据par->child.emplace_back(n);//加入父母节点的子节点数组中}static void tra(Tree *root){//遍历树,试试能不能看出是哪种遍历方式cout << root->Data;//访问当前节点if(root->child.size()) for(Tree *it : root->child) tra(it);//访问子节点}};
四.树的拓展 1.并查集
数据结构-并查集速通指南
2.最小生成树
数据结构-最小生成树速通指南
3.字典树
数据结构-字典树速通指南
4.AVL树 5.二叉搜索树 6.KD树 7.哈夫曼树 8.B树 9.红黑树 10.线段树 11.决策树 12.森林 13.B+树 14.B*树 15.堆 16.基数树 17.默克尔树 18.梅克尔帕特里夏树 19.LSM树 20.R树 21.伸展树 22.笛卡尔树五.树的相关练习

数据结构-树 速通指南( 三 )

数据结构-树速通指南( 三 )