一、树的基本概念

树型结构属于非线性结构（元素的前驱和后继的个数不是为1的），这一节讲的树形结构元素的前驱个数为1，但是元素的后继个数不是为1了（可以有多个后继），所以说树形机构元素的关系是一对多或者多对多的。树型结构的特点是节点之间是有分支的，并且还具有层次关系。

（一）树的基本概念

1. 树(Tree)是n(n≥0)个结点的有限集合T，若n=0时称为空树，否则:
   (1)有且只有一个特殊的称为树的根(Root)结点;
   (2)若n>1时， 其余的结点被分为m(m>0)个互不相交的子集$T$₁$,T$₂,$T$₃ … $T$_m ,其中每个子集本身又是一棵树，称其为根的子树(Subtree)。
2. 这是树的递归定义，即用树来定义树，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：
   （1）树的根节点没有前驱，除根节点外的所有结点有且仅有一个前驱
   （2）树种所有结点可以有零个或多个后继
3. 树适合于表示具有层次结构的数据，树中的某个节点（除根节点外）最多只和上一层的一个结点（其父节点）有直接关系，根节点没有直接上层结点，因此在n个结点的树种有n-1条边，而树中每个结点与其下一层的零个或多个节点（及其子女结点）有直接关系

（二）树的基本术语

（A）结点相关

1. 结点
2. 结点的度
3. 树的度：树中结点度最大值
4. 叶子结点（终端结点）、非叶子结点（非终端结点或分支结点）：除根结点以外，分支结点又称为内部结点。
5. 孩子结点、双亲结点、兄弟结点：一个结点的子树的根称为该结点的孩子结点，该结点是孩子结点的双亲结点或父结点，同一双亲结点的所有子结点互称为兄弟结点
6. 层次：规定树中根结点的层次为1，其余结点的层次等于其双亲结点的层次加1
7. 层次路径：从根结点开始，到达某结点p所经过的所有结点成为结点p的层次路径（有且仅有一条）【同一双亲的两个孩子之间不存在路径】
8. 堂兄结点：双亲结点在同一层上的所有结点互称为堂兄结点
9. 祖先结点：结点p的层次路径上的所有结点（p除外）称为p的祖先
10. 子孙结点：子树中的任意结点

（B）树整体相关

1. 树的深度：树中结点的最大层次值，又称为树的高度
2. 有序树和无序树：对于一棵树，若其中每一个结点的子树(若有）具有一定的次序，则称为有序树
3. 森林：是m（m≥0）棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。【m=0，表示空森林】
4. 结点的高度：从叶结点开始从底向上逐层累加
5. 结点的深度：从根结点开始从顶向下逐层累加

（三）树的表示形式

（1）倒悬树：最常用的表示形式
（2）嵌套集合：是一些集合的集体，对于任何两个集合，或者不想交，或者一个集合包含另一个集合
（3）广义表形式：例如（A(B(E(K,L),F),C(G(M,N),D(H,I,J)
（4）凹入法表示形式

（四）树的性质

1. 结点数=总度数+1
2. 区分度为m的树，m叉树
   度为m的树：各结点的度最大值为m，但是其他结点的度不一定是m
   m叉树：每个结点最多只能有m个孩子的树

3. 度为m的树第i层至多有m^i-1 个结点（i≥1）
4. m叉树第i层至多有m^i-1个结点（i≥1）
4. 高度为h的m叉树至多有 (m^h-1) /(m-1)个结点:m⁰+m¹…+mⁿ
5. 高度为h的m叉树至少有h个结点
6. 高度为h，度为m的树至少有h+m-1个结点
7. 具有h个结点的m叉树的最小高度为[log_m(n(m-1)+1)]

二、二叉树

（一）二叉树的定义

1. 特点：①每个结点至多只有两棵子树 ②左右子树不能颠倒（二叉树是有序树）
2. 二叉树(Binary tree )是n(n≥0)个结点的有限集合。
   若n=0时称为空树,否则:
   (1)有且只有一个特殊的称为树的根(Root)结点;
   (2)若n>1时，其余的结点被分成为二个互不相交的子集$T$₁ , $T$₂ ,分别称之为左、右子树，并且左、右子树又都是二叉树。
   由此可知，二叉树的定义是递归的。
3. 特点：二叉树结构简单，存储效率高，树的操作算法相对简单，且任何树都很容易转化成二叉树
4. 二叉树的形态：（1）空二叉树（2）单结点二叉树（3）右子树为空（4）左子树为空（5）左右子树都不为空
5. 二叉树与度为2的树的区别：

• 度为2的树至少有3个结点，而二叉树可以为空
• 度为2的有序树的孩子的左右次序是相对另一孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，次序就是确定的

（二）几个特殊的二叉树

1. 满二叉树

（1）一棵高度为h，且含有2h - 1个结点的二叉树
（2）特点：
①只有最后一层有叶子结点
②不存在度为 1 的结点
③按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为 i/2 （如果有的话）
（3）基本特点：a.是每一层上的结点数总是最大结点数。b. 满二叉树的所有的支结点都有左、右子树。c. 可对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自左至右”的原则进行。

2. 完全二叉树

（1）当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树
（2） 特点：
①只有最后两层可能有叶子结点
②最多只有一个度为1的结点
③同左③ ④ i≤ n/2 为分支结点， i> n/2 为叶子结点

（3）完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例
（4）特点：① 若完全二叉树的深度为 $k$ ，则所有的叶子结点都出现在第 $K$ 层或 $K-1$ 层 ② 对于任意结点，如果其右子树的最大层次为 $l$ ，则左子树的最大层次为 $l$ 或 $l+1$
（5）性质：
① n个结点的完全二叉树深度为 $[log2n]+1$
②若对一棵有n个结点的完全二叉树(深度为 $[log2n]+1$ 的结点按层(从第1层到第 $[log2n]+1$ 层)序自左至右进行编号，则对于编号为 $i$ ($1\le i\le n$)的结点:
a. 若i=1:则结点i是二叉树的根，无双亲结点;否则，若i>1,则其双亲结点编号是[i/2]。
b. 如果2i>n:则结点i为叶子结点，无左孩子;否则，其左孩子结点编号是2i。
c. 如果2i+1>n:则结点i无右孩子;否则，其右孩子结点编号是2i+1。

3. 二叉排序树

1. 一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
   （1）左子树上所有结点的关键字均小于根结点的关键字；
   （2）右子树上所有结点的关键字均大于根结点的关键字。
   左子树和右子树又各是一棵二叉排序树。
2. 左子树关键字<根节点关键字<右子树关键字
3. 

4. 平衡二叉树

1. 树上任一结点的左子树和右子树的深度之差不超过1。
2. 平衡的二叉树可以有更高的搜索效率
3. 

(三) 二叉树的性质

1. 基础性质

1.设非空二叉树中度为0、1和2的结点个数分别为n₀、n₁和n₂，则 n₀ = n₂ + 1（叶子结点比二分支结点多一个）
假设树中结点总数为 n，则
① n = n₀ + n₁ + n₂ ② n = n₁ + 2n₂ +1 => ② - ①n₀ = n₂ + 1
2. 二叉树第 i 层至多有 2^i-1 个结点（i≥1） m叉树第 i 层至多有 m^i-1 个结点（i≥1）
3. 高度为h的二叉树至多有 2^ℎ − 1^{个结点（满二叉树),高度为h的m叉树至多有(m}h^-1) /(m-1)个结点

2. 完全二叉树性质

1. 具有n个（n > 0）结点的完全二叉树的高度h为 [log₂(n+1)]或[log₂n]+1
   
2. 对于完全二叉树，可以由的结点数 n 推出度为0、1和2的结点个数为n₀、n₁和n₂，完全二叉树最多只有一个度为1的结点，即n₁=0或1 n₀ = n₂ + 1 则 n0 + n2 一定是奇数
   ①若完全二叉树有2k个（偶数）个结点，则必有n₁=1， n₀ = k，n₂ = k-1
   ② 若完全二叉树有2k-1个(奇数)个结点，则必有n₁=0，n₀ = k，n₂ = k-1

(四）二叉树的顺序存储

1. 基础实现：

#define MaxSize 100
struct TreNode{
   ElemType value; //结点中的数据元素
   bool isEmpty;//结点是否为空

};
TreeNode t[MaxSize];
1
2
3
4
5
6
7

定义一个长度为MaxSize的数组t，按照从上至下，从左至右的顺序依次存储完全二叉树中的各个结点。

2. 初始化

bool InitT(TreeNode L[]){
   for(int i=0;i<MaxSize;i++){
    t[i].isEmpty=true;
   }
}
1
2
3
4
5

3. 完全二叉树查找是否有左右孩子双亲，可以用：设当前结点为i

• 如果2i≤n，那么就存在左孩子
• 如果2i+1≤n，那么就存在右孩子
• 如果i＞[n/2]，那么就是叶子结点，反之，是分支结点

4. 如果不是完全二叉树是不可以用上述结论。需要重新设计
5. 如果是一个普通二叉树，需要编号与完全二叉树一一对应起来，如下

这样就形成二叉树如图

6. 对于顺序存储而言，最坏的情况下，一个深度为k且只有k个结点的单支树需要长度为2^k-1的一位数组

(五）二叉树的链式存储

1. 实现方式;

typedef struct BiTNood{
   ElemType value; //结点中的数据元素
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

1
2
3
4
5

注意：n个结点的二叉链表共有n+1个空链域，因此可以用于构造线索二叉树

struct ElemType{
  int value;
};
typedef struct BiTNood{
   ElemType value; //结点中的数据元素
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//定义一个空树
BiTree root=NULL;
//插入根节点
root = (BiTree)malloc(sizeof(BiTNode));
root->data={1};
root->lchild=NULL;
root->rchild=Null;
//插入新结点
BiTNode *p=(BiTNode *)malloc(sizeif(BiTNode));
p->data={2};
p->lchild=NULL;
p->rchild=NULL;
root->lchild=p;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

问题是：很难找到父节点（寻找子结点简单）

2. 加入双亲结点的存储（三叉链表）

typedef struct BiTNood{
   ElemType value; //结点中的数据元素
  struct BiTNode *lchild,*rchild;
   struct BiTNode *parent;
}BiTNode,*BiTree;
1
2
3
4
5

(六) 先中后序遍历 （递归算法）

先序：根左右（前缀表达式）
中序：左根右（中缀表达式）
后序：左右根（后缀表达式）

1. 先序遍历

（1）规则：想访问根节点后访问左结点，右结点
（2）代码思想：
① 如果二叉树为空，那就什么也不做
② 如果二叉树非空，先序遍历左子树，访问根节点，先序遍历右子树
（3）代码：

typedef struct BiTNood{
   ElemType value; //结点中的数据元素
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void InOrder(BiTree T){
  if(T!=NULL){
   visit(T);
    InOrder(T->lchild);
    InOrder(T->rchild);
  }
}
1
2
3
4
5
6
7
8
9
10
11

（4）分析：①空间复杂度：O(h)
② 每一个结点都会在第一次访问时处理
③每一个结点都会路过三次

2. 中序遍历

（1）代码实现：

  if(T!=NULL){
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
  }
1
2
3
4
5

（2）分析：①只有在第二次路过结点时才会访问 ②空间复杂度 O（h）

3. 后序遍历

（1）代码实现：

  if(T!=NULL){
    InOrder(T->lchild);
    InOrder(T->rchild);
    visit(T);
  }
1
2
3
4
5

（2）分析：①只有在第三次路过结点时才会访问 ②空间复杂度 O（h）

（七）先中后序遍历（非递归算法）

void preorder1(BiTree root)
{
    BiTree s[MAX_TREE_SIZE],p;
    int top;
    top=0;
    p=root;
    while(p||top>0)
    {
        while(p)
        {
            cout<<p->data<<" ";
            top++;
            s.[top]=p;
            p=p->lchild;   
        }
        if(top>0)
        {
            p=s[top];
            top--;
            p=p->rchild;
        }
    }
    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

前中后都差不多，不过是顺序变化

（八）层次遍历

1. 算法思想：
   （1）初始化一个辅助队列
   （2）跟结点入队
   （3）若队列非空，则队头结点出队，访问该结点，并将其左、右结点插入队尾
   （4）重复（3）直到队列为空
2. 代码实现（顺序存储方式）：

//；二叉树的顺序储存结构
#define MAX_TREE 10000;
typedef  Telemtype SiTree[MAX_PATH];
SiTree bT;
void leveltree(BiTree *t)
{
      BiTree s[100],p;
      int front rear;
    front=rear=0;
    p=t;
     if(t!=NULL)
     {
         rear++;
         s[rear]=p;
         while(front!=rear)
         {  front++;
            p=s[front];
            count<<p->data;
            if(p->lchild)
            {
                rear++;
                s[rear]=p->lchild;
                
            }
             if(p->rchild)
            {
                rear++;
                s[rear]=p->rchild;
                
            }
             
         }
     }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

3. 代码实现（链队列）

typedef struct Bnode	/*定义二叉树存储结构*/
{ char data;
  struct Bnode *lchild,*rchild;
}Bnode,*Btree;
 
void Createtree(Btree &T)	/*创建二叉树函数*/
{
    //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	if(ch=='#')
        T=NULL;			//递归结束，建空树
	else{
		T=new Bnode;
		T->data=ch;					//生成根结点
		Createtree(T->lchild);	//递归创建左子树
		Createtree(T->rchild);	//递归创建右子树
	}
    return;
}
bool Leveltraverse(Btree T)
{
    Btree p;
    if(!T)
        return false;
    queue<Btree>Q; //创建一个普通队列(先进先出)，里面存放指针类型
    Q.push(T); //根指针入队
    while(!Q.empty()) //如果队列不空
    {
        p=Q.front();//取出队头元素
        Q.pop(); //队头元素出队
        cout<<p->data<<"\t";
        if(p->lchild)
            Q.push(p->lchild); //左孩子指针入队
        if(p->rchild)
            Q.push(p->rchild); //右孩子指针入队
    }
    return true;
} 
int main()
{  Btree mytree;
    Createtree(mytree);//创建二叉树
    Leveltraverse(mytree);//层次遍历二叉树
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

（九）构造二叉树

1. 根据遍历构造二叉树

1. 分析可以发现，一个已知二叉树的先中后序遍历顺序一定，但是一个已知的先中后序遍历得到的树是不一定的
2. 层次遍历也是不一定的
3. 给出先中后序一种是无法得到确定的二叉树，因此需要进行组合（先+中）（中+后）（中+层次）注意：前+后是无法得到唯一的，一定要有中序序列，缺少中序无论如何组合都没有办法得到唯一的树。
4. 以给出前序+中序构造二叉树为例，方法技巧：
   ① 前序第一个结点一定是根结点（层次遍历第一个也是根结点，后序遍历的最后一个结点一定是根结点），进而可以在中序中寻得被根结点分开的两部分
   ② 中序中前部分为左树，后部分为右树，可以利用这两部分的长度去分开前序中的左右子树。
   ③ 利用递归的思想，每一个子树都适用
5. 总结：找到树的根结点，并根据中序序列划分左右子树，再找到左右子树根结点

2. 代码构造二叉树

void creatree(BiTree &t);
{
    char ch;
    count<<ch<<" ";
    t->data=ch;
    if(ch!='@')
    {
        t=new BiTNode;
        creatree(t->lchild);
        creatree(t->rchild);
        
    }
    else 
        t=NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

三、线索二叉树

1. 二叉树存在的问题：
   （1）每次进行遍历的时候，只能从根结点开始遍历某个子树，无法从分支或叶子结点开始遍历整个树
   （2）无法找到一个结点的遍历顺序中的前驱，只能设置两个指针，一个记录，当前一个记录上一个被访问的结点，才有可能得到前驱，要经过一个完整的遍历
2. 改进：利用n个结点的树有n+1个空链域，空链域指向前后驱，没有前驱后继设置为NULL，分为前驱线索（左孩子充当），后继线索（右孩子充当）。

（一）线索二叉树的存储结构

1. 代码实现

typedef struct ThreadNode{
  ElemType data;
  struct ThreadNode *lchild,*rchild;
  int ltag,rtag;
}ThreadNode,*ThreadTree;
1
2
3
4
5

2. 结构

tag=0 的时候指向自己的左右孩子
tag=1 的时候指向的是自己的前后驱（说明没有孩子）
3. 画出线索二叉树

（二）对二叉树进行线索化

1. 以中序为例
   附设一个指针pre始终指向刚访问的结点，若指针p指向当前访问的结点，则pre指向他的前驱。
   下面以中序线索树的建立为例，介绍在中序遍历过程中如何修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。附设指针pre, 并始终保持指针pre指向当前访问的由指针p所指结点的前驱。

typedef struct ThreadNode{
  ElemType data;
  struct ThreadNode *lchild,*rchild;
  int ltag,rtag;
}ThreadNode,*ThreadTree;
ThreadNode *pre = NULL;
//中序线索二叉树
void CreateInThread(ThreadTree T){
  pre = NULL; //pre初始为NULL
  if(T!=NULL){  //非空二叉树才可以进行线索化
     InThread(T);  //终须线索化二叉树
     if(pre->rchild==NULL)
               pre->rtag=1; //处理遍历的最后一结点
  }
}
//中序遍历二叉树，一边遍历一边中序线索化
void InTread(ThreadTree T){
 if(T!=NULL){
    InThread(T->lchild);
    visit(T);
    InThread(T->rchild);
  } 
}
void visit(ThreadNode *q){
// 建前驱线索
if (p->lchild==NULL)      
  {    
        p->ltag = 1;    
         p->lchild = pre; 
}
// 建后继线索
if (pre->rchild==NULL&&pre!=NULL)   
  { 
       pre->rtag = 1;   
        pre->rchild = p; 
} 
pre = p;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

2. 先序遍历需要注意转圈问题，所以需要修改一部分代码

void InTread(ThreadTree T){
 if(T!=NULL){
    visit(T);
    if (T->ltag==0)
       InThread(T->lchild);//只有左指针指向的的确是左孩子时才访问
    InThread(T->rchild);
  } 
1
2
3
4
5
6
7

3. 后序不存在转圈问题

（三）在线索二叉树查找前驱后继

1. 中序线索二叉树

A. 寻找后继结点

（1）寻找指定结点*p的中序后继next的思想
①若p->rtag==1,则next=p->rchild
② 若p->rtag==0，则说明指定结点有右孩子，那么为右子树最左边的最后一个结点（如果p的右孩子是个叶子结点，那next=p->rchild）
（2）代码

ThreadNode *Firstnode(ThreadNode *p){
    //循环找到最左下结点（不一定是叶子结点,可能只是没有左孩子但是有右孩子）
    while(p->ltag==0) p=p->lchild;
    return p;
}
ThreadNode *Nextnode(ThreadNode *p){
   //右子树中最左下的结点
   if(p->rtag==0) return Firstnode(p->rchild);
   //如果右边是孩子，那么就找右子树中最左下的结点
   //如果不是，那么就是本身右指针指向的后驱
   else return p->rchild;
}
1
2
3
4
5
6
7
8
9
10
11
12

（3）根据上述思路就可以利用线索二叉树进行非递归中序遍历，只需要加入如下代码：

void visit(ThreadNode *q){
   // 建前驱线索
   if (p->lchild==NULL)      
    {  p->ltag = 1;  p->lchild = pre; 
    }
   // 建后继线索
    if (pre->rchild==NULL&&pre!=NULL)   
    {   pre->rtag = 1;    pre->rchild = p; 
    } 
     pre = p;
}
void Inorder (ThreadNode *T){
   for(ThreadNode *p = Firstnode(T);p!=NULL;p=Nextnode(p)){
    visit(p);
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

空间复杂度：O（1）

B.寻找前驱结点

（1）寻找中序遍历指定点*p的前驱结点
①若p->ltag==1,则next=p->lchild
② 若p->ltag==0，则说明指定结点有左孩子，那么为左子树最右边的最后一个结点（如果p的右孩子是个叶子结点，那next=p->lchild）
（2）代码：

ThreadNode *lastnode(ThreadNode *p){
    while(p->rtag==0) p=p->rchild;
    return p;
}
ThreadNode *Prenode(ThreadNode *p){
   if(p->ltag==0) return Firstnode(p->lchild);
   else return p->lchild;
}
void visit(ThreadNode *q){
   if (p->lchild==NULL)      
    {  p->ltag = 1;  p->lchild = pre; 
    }
    if (pre->rchild==NULL&&pre!=NULL)   
    {   pre->rtag = 1;    pre->rchild = p; 
    } 
     pre = p;
}
void Inorder (ThreadNode *T){
   for(ThreadNode *p = lastnode(T);p!=NULL;p=Prenode(p)){
    visit(p);
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

注意：利用这种方式进行的中序遍历是逆向的

2. 先序线索二叉树

A. 寻找后继结点

在先序线索二叉树中找到指定结点p的先序后继next
（1）若是叶子结点右标志为1，则右链为线索，指向其后继，即若p->rtag==1，则next=p->rchild
（2）若p->rtag==0,则一定有右孩子
① 若p有左孩子，那么后继为左孩子
② 若p没有左孩子，那么后继为右孩子

B. 寻找前驱结点

（1） 若p->ltag==1，则next=p->lchild
（2）若p->ltag==0，则说明有左孩子，而先序顺序为根左右，则左右子树只可能是根的后继，进而是找不到前驱的，只能进行重新先序遍历，则需要进行建立三叉链表，如下：
① 如果能找到p的父节点，且p是左孩子，则前驱为该父节点
② 如果能找到p的父节点，且p是右孩子，且其左兄弟为空，则前驱为该父节点
③ 如果能找到p的父节点，且p是右孩子，且其左兄弟非空，则前驱为前面最后一个被遍历的结点
④ 如果不能找到p的父节点(即p为根结点)，则p没有先序前驱。

3. 后续线索二叉树

A. 寻找后继

（1） 若p->rtag==1，则next=p->rchild
（2）若p->rtag==0,则一定有右孩子，由于后序遍历顺序为左右根，所以没有办法在二叉链表结构中找到后继，则要么从头遍历，要么使用三叉链表，三叉链表思路为：
①如果可以找到p的父节点，且p是右孩子，则后续后继为父节点
②如果可以找到p的父节点，且p是左孩子，且右兄弟为空，则后续后继为父节点
③如果可以找到p的父节点，且p是左孩子，且右兄弟非空，则后续后继为右兄弟子树中第一个被后序遍历的结点
④如果p是根节点，没有父节点，则没有后续后继结点

B. 寻找前驱

在后续线索二叉树中找到指定结点*p的后续前驱pre
（1）若p->ltag==1，则next=p->lchild
（2）若p->ltag==0，则说明一定有左孩子，右孩子不得而知
① 假设有右孩子，则后序前驱为右孩子
② 假设没有右孩子，则后序前驱为左孩子

4. 总结上述

×的都可以用三叉链表或者从头开始遍历寻找的方法

四、普通的树

（一）树的存储结构—双亲表示法（顺序存储）

1. 代码实现

typedef struct {
  ElemType data;
  int parent;
}PTNode;
typedef struct{
  PTNode nodes[Max_TREE_SIZE];
  int n;
}PTree;
1
2
3
4
5
6
7
8

2. 结构示意

树为：
根节点固定存储在0，-1表示没有双亲

3. 增加数据元素，直接在表后增加，无序按照逻辑上的次序存储
4. 删除数据元素，①可以将parent数值变为-1，表示为空；② 将表中最后一个数据覆盖删除数据这一行；删除后节点数-1【前提：删除一个叶结点】
5. 缺点：查找指定结点的额孩子只能从头遍历，且遍历时如果删除元素时用的第一种方案则会有一次查找空数据使遍历更慢
6. 优点：查找双亲更快

（二）存储结构—孩子表示法（顺序+链式存储）

1. 代码实现

#define Max_TREE_SIZE 100
struct CTNode{
  int child; //孩子结点在数组中的位置
  struct CTNode *next;//下一个孩子
};
typedef struct{
  ElemType data;
  struct CTNode *firstChild;//第一个孩子
}CTBox;
typedef struct{
 CTBox nodes[Max_TREE_SIZE];
 int n,r;//节点数和根的位置
}CTree;
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 示意
   
3. 优缺点：查找孩子结点方便，但是查找双亲结点就不方便了

（三）存储结构—孩子兄弟表示法（链式存储）

1. 代码实现

#define Max_TREE_SIZE 100
typedef struct CSNode{
   ELemType data; //数据域
   struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针
}CSNode,*CSTree;
1
2
3
4
5

2. 实例
   
3. 会考树和二叉树的相互转换，因为上述结构实质就是树用二叉树的样子存储起来，也会考二叉树与森林转换
4. 例题：

（四）对树和森林的遍历

1.先根遍历

（1）思想：如果树不空的话，那么就先访问根结点，再依次对每棵子树进行先根遍历
（2）代码：

void PreOrder(TreeNode *R){
  if(R!=NULL){
    visit(R);//访问根结点
    while(R还有下一个子树T){
        PreOrder(T);//先根遍历下一棵子树
    }
  }
}
1
2
3
4
5
6
7
8

（3）示例：

发现：树的先根遍历序列与这个树对应的二叉树的先序序列相同

2.后根遍历

（1）代码实现：

void PostOrder(TreeNode *R){
  if(R!=NULL){
    while(R还有下一个子树T){
        PostOrder(T);//后根遍历下一棵子树
    }
       visit(R);//访问根结点
  }
}
1
2
3
4
5
6
7
8

（2）示例

（3）发现：树的先根遍历序列与这个树对应的二叉树的先序序列相同

3. 层次遍历（队列实现）

（1）思想：
① 若树非空，则根结点入队
② 若队列非空，队头元素出队并访问，同时将该元素的孩子一次入队
③ 重复②直到队列为空
（类似于广度优先遍历）

（五）森林

森林是m（m≥0）棵互不相交的树的集合。每棵树去掉根结点后，其各个子树又组成森林

1.先序遍历

若森林为非空，则按如下规则进行遍历
① 访问森林中第一课树的根结点
② 先序遍历第一棵树中根结点的子树森林
③ 先序遍历除去第一棵树之后剩余的树构成的森林
效果等于依次对各个树进行先根遍历，也可以等同于转换为二叉树后的先序遍历

2. 中序遍历

若森林为非空，则按如下规则进行遍历
①先序遍历第一棵树中根结点的子树森林
②访问森林中第一课树的根结点的
③ 先序遍历除去第一棵树之后剩余的树构成的森林
效果等于依次对各个树进行后根遍历，也可以等同于转换为二叉树后的中序遍历序列

总结

五、基础操作

1. 求二叉树结点的深度

算法基本思想: 二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。

int findtree(BiTree *t)
{    int l,r;
    if(t==NULL) return 0;
    else 
    {
        l=findtree(t->lchhild);
        r=findtree(t->rchild);
        if(l<r)  return r+1;
        else return l+1;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13

2. 统计二叉树中叶子结点的个数

int addTnode(Bitree *t)
{
    if(t=NULL) return 0;
    else 
        if(t->rchild==NULL&&t->lchild==NULL)
          n++;
    addTnode(t->rchild);
    addTnode(t->lchild);
    return n;
} 

1
2
3
4
5
6
7
8
9
10
11

3. 复制二叉树

void copytree(BiTree t1,BiTree t2)
{    if(t1==NULL)
       t2=NULL;
     else {
       t2=new BiTNode;
       t2->data=t1->data;
       t2->lchild=NULL;
       t2->rchild=NULL;
       copytree(t1->rchild,t2->rchild);
       copytree(t1->lchild,t2->lchild);
     }
    
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

六、遍历部分完整代码

#define _CRT_SECURE_NO_WARNINGS // VS忽略警告，其它应该不需要

#include 
#include 
#include 
#include 

#define MAX_SIZE 128
#define STR_SIZE 1024

typedef struct Node {    // 定义二叉链
    char         data;   // 数据元素
    struct Node* lchild; // 指向左孩子节点
    struct Node* rchild; // 指向右孩子节点
} BTNode;                // struct Node 的别名

typedef struct Quene {      // 定义顺序队
    int     front;          // 队头指针
    int     rear;           // 队尾指针
    BTNode* data[MAX_SIZE]; // 存放队中元素
} SqQueue;                  // struct Queue 的别名

/**
 * 队列函数
 */
void initQueue(SqQueue** q);             // 初始化队列
bool emptyQueue(SqQueue* q);             // 判断队列空
bool enQueue(SqQueue* q, BTNode* node);  // 入队
bool deQueue(SqQueue* q, BTNode** node); // 出队

/**
 * 二叉树函数
 */
// void createBTNode2(BTNode** BT);                  // 创建二叉树
int  createBTNode(BTNode** BT, char* str, int n); // 创建二叉树
void preOrder(BTNode* BT);                        // 前序遍历
void inOrder(BTNode* BT);                         // 中序遍历
void postOrder(BTNode* BT);                       // 后序遍历
void levelOrder(BTNode* BT);                      // 层次遍历

/**
 * 画树函数
 */
void draw_level(BTNode* node, bool left, char* str); // 画分支
void draw(BTNode* root);                             // 画根节点

/***************************************************************************
 * @date    2019/12/08
 * @brief   层次遍历二叉树
 * @param   BT  二叉树根节点
 ***************************************************************************/
void levelOrder(BTNode* BT) {
    SqQueue* q;       // 定义队列
    initQueue(&q);    // 初始化队列
    if (BT != NULL) { // 根节点指针进队列
        enQueue(q, BT);
    }
    // 一层一层的把节点存入队列，当没有孩子节点时就不再循环
    while (!emptyQueue(q)) {      // 队不为空循环
        deQueue(q, &BT);          // 出队时的节点
        printf("%c", BT->data);   // 输出节点存储的值
        if (BT->lchild != NULL) { // 有左孩子时将该节点进队列
            enQueue(q, BT->lchild);
        }
        if (BT->rchild != NULL) { // 有右孩子时将该节点进队列
            enQueue(q, BT->rchild);
        }
    }
}

int main() {
    // 例子：ABDH###E##CF##G##
    BTNode* BT;
    printf("请输入字符串：");
    char* str = (char*)malloc(sizeof(char) * STR_SIZE);
    scanf("%s", str);
    if (strlen(str) == createBTNode(&BT, str, 0)) {
        printf("二叉树建立成功\n");
    }
    // printf("请输入字符串：");
    // createBTNode2(&BT);
    // draw(BT);

    printf("\n先序遍历结果：");
    preOrder(BT);

    printf("\n中序遍历结果：");
    inOrder(BT);

    printf("\n后序遍历结果：");
    postOrder(BT);

    printf("\n层序遍历结果：");
    levelOrder(BT);

    return 0;
}

// 初始化队列
void initQueue(SqQueue** q) {
    if (!((*q) = (SqQueue*)malloc(sizeof(SqQueue)))) {
        printf("内存分配失败！");
        exit(-1);
    }
    (*q)->front = (*q)->rear = -1; // 置 -1
}

// 判断队列是否为空
bool emptyQueue(SqQueue* q) {
    // 首指针和尾指针相等，说明为空。空-返回真，不空-返回假
    if (q->front == q->rear) {
        return true;
    }
    return false;
}

// 进队列
bool enQueue(SqQueue* q, BTNode* node) {
    // 判断队列是否满了。满（插入失败）-返回假，不满（插入成功）-返回真
    if (q->rear == MAX_SIZE - 1) {
        return false;
    }
    q->rear++;               // 头指针加 1
    q->data[q->rear] = node; // 传值
    return true;
}

// 出队列
bool deQueue(SqQueue* q, BTNode** node) {
    // 判断是否空了。空（取出失败）-返回假，不空（取出成功）-返回真
    if (q->front == q->rear) {
        return false;
    }
    q->front++;                // 尾指针加 1
    *node = q->data[q->front]; // 取值
    return true;
}

// 创建二叉树
int createBTNode(BTNode** BT, char* str, int n) {
    char ch = str[n++];  // 把第 n 个字符赋给ch,方便后面判断，字符下标后移
    if (ch != '\0') {    // 如果 ch 不等于结束符就继续创建，否则就结束
        if (ch == '#') { // 以 # 号代表 NULL，下面没有了
            *BT = NULL;
        } else {
            if (!(*BT = (BTNode*)malloc(sizeof(BTNode)))) {
                printf("内存分配失败！");
                exit(-1);
            } else {
                (*BT)->data = ch;
                n           = createBTNode(&((*BT)->lchild), str, n); // 左递归创建
                n           = createBTNode(&((*BT)->rchild), str, n); // 右递归创建
            }
        }
    }
    // 返回 n，记录字符串使用到哪里了
    return n;
}
// 创建二叉树
// void createBTNode2(BTNode** BT) {
//     char ch;
//     ch = getchar();
//     if (ch == '#') {
//         *BT = NULL;
//     } else {
//         if (!(*BT = (BTNode*)malloc(sizeof(BTNode)))) {
//             printf("内存分配失败！");
//             return;
//         } else {
//             (*BT)->data = ch;
//             createBTNode2(&((*BT)->lchild)); // 分配成功则接着建立左子树和右子树
//             createBTNode2(&((*BT)->rchild));
//         }
//     }
// }

// 先序遍历
void preOrder(BTNode* BT) {
    if (BT != NULL) {           // 判断不为空
        printf("%c", BT->data); // 访问根节点
        preOrder(BT->lchild);   // 递归，先序遍历左子树
        preOrder(BT->rchild);   // 递归，先序遍历右子树
    }
}

// 中序遍历
void inOrder(BTNode* BT) {
    if (BT != NULL) {
        inOrder(BT->lchild);
        printf("%c", BT->data);
        inOrder(BT->rchild);
    }
}

// 后序遍历
void postOrder(BTNode* BT) {
    if (BT != NULL) {
        postOrder(BT->lchild);
        postOrder(BT->rchild);
        printf("%c", BT->data);
    }
}

/*****************************************************************************
* @date   2020/4/19
* @brief  水平画树
* @param  node	二叉树节点
* @param  left	判断左右
* @param  str 	可变字符串
*****************************************************************************/
void draw_level(BTNode* node, bool left, char* str) {
    if (node->rchild) {
        draw_level(node->rchild, false, strcat(str, (left ? "|     " : "      ")));
    }

    printf("%s", str);
    printf("%c", (left ? '\\' : '/'));
    printf("-----");
    printf("%c\n", node->data);

    if (node->lchild) {
        draw_level(node->lchild, true, strcat(str, (left ? "      " : "|     ")));
    }
    //  "      " : "|     " 长度为 6
    str[strlen(str) - 6] = '\0';
}

/*****************************************************************************
* @date   2020/4/19
* @brief  根节点画树
* @param  root	二叉树根节点
*****************************************************************************/
void draw(BTNode* root) {
    char str[STR_SIZE];
    memset(str, '\0', STR_SIZE);

    /**
     * 1. 在 windows 下，下面是可执行的
     * 2. 在 Linux   下，执行会报 Segmentation fault
     *      需要使用中间变量
     */
    if (root->rchild) {
        draw_level(root->rchild, false, str);
    }
    printf("%c\n", root->data);
    if (root->lchild) {
        draw_level(root->lchild, true, str);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250