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

数据结构-树速通指南
“速通个屁的树，去找鲁迅还差不多”——沃~兹基
很抱歉本文的作者是个垃圾，一边学一边更新。
请大家当做真正的指南来看，看到啥想学的请自己指过去
文章目录2.树的插入3.树的删除 4.树的遍历三.用c++中STL库搭建树四.树的拓展五.树的相关练习
一.介绍树
树是一种一对多的数据结构,是n个结点的有限集。树的概念特别的多。所以就用一个动图简单的过一遍：
结点的度：一个结点含有的子树的个数称为该结点的度；
叶结点：度为0的结点称为叶结点，也可以叫做终端结点；
分支结点：度不为0的结点称为分支结点，也可以叫做非终端结点；
结点的层次：从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推；
结点的层序编号：将树中的结点，按照从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数；
树的度：树中所有结点的度的最大值；
树的高度(深度)：树中结点的最大层次；
孩子结点：一个结点的直接后继结点称为该结点的孩子结点；
双亲结点(父结点)：一个结点的直接前驱称为该结点的双亲结点；
兄弟结点：同一双亲结点的孩子结点间互称兄弟结点。
二.手写树 1.树的建立
树常用的三种表示法为：双亲表示法，孩子表示法，孩子兄弟表示法。
（1）双亲表示法
双亲表示法就是每个结点指向自己双亲的表示方法（废话）
其结点的结构为：
其创建思路为：
双亲表示法： { 1. 创建根结点并记录根结点 { 1. 放数据到 D a t a 2. P a r e n t 指向 N U L L 2. 创建新结点 { 1. 放数据到 D a t a 2. P a r e n t 指向双亲结点双亲表示法： \begin{cases} 1.创建根结点并记录根结点\begin{cases} 1.放数据到Data\\ 2.指向NULL\\ \end{cases}\\ 2.创建新结点\begin{cases} 1.放数据到Data\\ 2.指向双亲结点\\ \end{cases}\\ \end{cases} 双亲表示法：????????????1.创建根结点并记录根结点{1.放数据到Data2.指向NULL?2.创建新结点{1.放数据到Data2.指向双亲结点??
struct Node{int Data;Node *Parent;};
这种表示法方便向上查找双亲节点，查找子节点却十分困难，通常需要遍历。
（2）孩子表示法
孩子表示法与双亲表示法恰恰相反，其结点的指针域是指向子节点的,所以优劣相反。
其结点有两种写法，第二种相对来说会更省空间
其创建思路为：
孩子表示法： { 1. 创建根结点，{ 1. c h i l d 指向 N U L L 2. 数据放入 D a t a 2. 创建子结点，{ 1. c h i l d 指向 N U L L 2. 数据放入 D a t a 3. 双亲结点的 c h i l d 指向该结点孩子表示法： \begin{cases} 1.创建根结点，\begin{cases} 1.child指向NULL\\ 2.数据放入Data\\ \end{cases}\\ 2.创建子结点，\begin{cases} 1.child指向NULL\\ 2.数据放入Data\\ 3.双亲结点的child指向该结点\\ \end{cases} \end{cases} 孩子表示法：????????????????1.创建根结点，{1.child指向NULL2.数据放入Data?2.创建子结点，??????1.child指向NULL2.数据放入Data3.双亲结点的child指向该结点??
struct Node{int Data;Node *Child[maxn];};
（3）孩子兄弟表示法
孩子兄弟表示法对于查找某个结点的某个孩子是很方便，只需要通过，然后再通过，接着一直遍历下去，就能很轻松的找到具体的孩子。
孩子兄弟表示法的结点结构如下所示：
【数据结构-树速通指南】其创建思路为：
孩子兄弟表示法： { 1. 创建根结点 { 1. 放入数据 D a t a 2. F i r s t C h i l d 指向 N U L L 3. R i g h t S i b 指向 N U L L 2. 创建新结点 { 1. 放入数据 D a t a 2. 如果是长子结点双亲结点的 F i r s t C h i l d 指向该结点 3. F i r s t C h i l d 指向 N U L L 4. 如果不是长子节点左兄弟结点的 R i g h t S i b 指向 N U L L 5. R i g h t S i b 指向 N U L L 孩子兄弟表示法： \begin{cases} 1.创建根结点\begin{cases} 1.放入数据Data\\ 2.指向NULL\\ 3.指向NULL\\ \end{cases}\\ 2.创建新结点\begin{cases} 1.放入数据Data\\ 2.如果是长子结点双亲结点的指向该结点\\ 3.指向NULL\\ 4.如果不是长子节点左兄弟结点的指向NULL\\ 5.指向NULL\\ \end{cases} \end{cases} 孩子兄弟表示法：??????????????????????????????1.创建根结点??????1.放入数据Data2.指向NULL3.指向NULL?2.创建新结点????????????????1.放入数据Data2.如果是长子结点双亲结点的指向该结点3.指向NULL4.如果不是长子节点左兄弟结点的指向NULL5.指向NULL??

数据结构-树 速通指南

数据结构-树速通指南