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

（4）对于上述表示法的总结
其实也应该看出来了，不同的表示方法各有优劣，我们在实际应用中要根据实际需求来选择和组合不同的表示方法，并且一般来说，箭头所指，查询所向(这只能算半个废话)，根据我们的需要，我们可以衍生出很多诸如双亲兄弟、双亲孩子、双亲表兄弟等等等等，所以死记硬背是记不完的，这也是树灵活和强大之处。
2.树的插入
由于树的种类很多，插入要求也不尽相同，只能用“按要求插入”这句废话来囊括，即通过一定的规则进行定位，并使新增结点后的树符合特定规则，具体实施在树的拓展中针对不同的树再具体讲解，这里列出主要是为了着重强调树的插入一般情况下是插入叶子结点。
3.树的删除
树的删除分为删除树和删除结点，一定要看题看仔细（吃亏人现身说法）。
（1）整树删除
删除一整棵树实质上就是对树进行遍历，并对遍历到的结点进行删除,但是问题在于如果遍历的顺序不对，就会出现删除当前结点后无法继续进行遍历的情况，由于树的表示方法多种多样，所以删除操作也是不固定的，以孩子表示法的树为例，我们就要运用递归从叶子结点开始逐个删除，如图所示：
也可以看出有后序遍历那个味了，还挺正宗(本来就是) 。
后序遍历代码后面的部分会详细讲，所以这里的代码先看看吧。
void delete(Tree *T){for(int i = 0;i < maxn;i++){if(T->root->child[i]){T->root = T->root->child[i];delete(T);}}delete T->root;//删除看这里}
（2）结点删除
同样以孩子表示法的树为例，结点删除大致分为分叉结点删除和叶子结点删除。
α . \alpha. α.分叉结点删除
分叉结点的删除涉及到一个问题，该结点被删除后，其子树和原树断开了。其实我们只需遵循一个“继承”的原则，即被删结点的双亲结点的子结点变为被删结点的子结点，被删结点的子结点的双亲结点变为了被删结点的双亲结点。这像不像绕口令，但是想必大家在学链表的时候都绕过吧，这里是一致的。给个图来理解吧：
//假设是已经通过诸如遍历等方式找到了要删除结点的双亲结点void delete(Tree *T){Node *n = T->ParentNode->child[a];for(int i = 0;i < maxn;i++){T->ParentNode->child[k++] = n->child[i];}}
β . \beta. β.叶子结点删除
叶子结点的删除比较简单，因为无需顾虑（死了没人牵挂）,而且应该也注意到了上面整树删除给的例子都是删除叶子结点的，所以给个图看看就行了：
4.树的遍历
以二叉树为例，树的遍历有四种，先序遍历，中序遍历，后序遍历，层次遍历。其中前三种遍历方式几乎是一致的递归，而后序遍历和层次遍历可以对应图的遍历，所以也涉及到一些深搜、广搜的应用。
(1).先序遍历
先序遍历的思路就是“先”访问当前节点，再访问其左右子节点。
其动图如下：
其代码如下：
void Preorder_traversal(Node *n){cout << n->data;//访问该节点preorder_traversal(n->leftchild);preorder_traversal(n->rightchild);}
(2).中序遍历
中序遍历的思路就是先访问其左子节点，“中”访问当前节点，再访问右子节点。
其动图如下：
其代码如下：
void Mediumorder_traversal(Node *n){Mediumorder_traversal(n->leftchild);cout << n->data;//访问该节点Mediumorder_traversal(n->rightchild);}
其实对比一下前序遍历基本没有变化。

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

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