数据结构（C语言版） 第 五 章 树与二叉树 知识梳理 + 作业习题详解_一棵完全二叉树有5000个结点,可以计算出其叶结点的个数是

本系列博客为《数据结构》（C语言版）的学习笔记（上课笔记），仅用于学习交流和自我复习

---

数据结构合集链接： 《数据结构》C语言版（严蔚敏版） 全书知识梳理（超详细清晰易懂）

树和二叉树

一.树

树：是N(N≥0)个结点的有限集合，N=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

• 有且仅有一个特定的称为根的结点。
• 当N>1时，其余结点可分为m(m>0)个互不相交的有限集合T1,T2,…,Tm，其中每一个集合本身又是一棵树，并且称为根结点的子树。
  

显然树的定义是递归的，是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

1. 树的根结点没有前驱结点，除根结点之外的所有结点有且仅有一个前驱结点。
2. 树中所有结点可以有零个或者多个后继结点。

树适合于表示具有层次结构的数据。
树中的某个结点（除了根结点之外）最多之和上一层的一个结点（其父结点）有直接关系，根结点没有直接上层结点，因此在n个结点的树中最多只有n-1条边。而树中每个结点与其下一层的零个或者多个结点（即其子女结点）有直接关系。

对K来说：根结点A到K的唯一路径上的任意结点，称为K的祖先结点。如结点B是K的祖先节点，K是B的子孙结点。路径上最接近K的结点E称为K的双亲结点，K是E的孩子结点。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟节点，如K和L有相同的双亲结点E，即K和L是兄弟结点。
树中一个结点的子结点个数称为该结点的度，树中结点最大度数称为树的度。如B的度为2，但是D的度为3，所以该树的度为3.
度大于0的结点称为分支结点（又称为非终端结点）；度为0（没有子女结点）的结点称为叶子结点（又称终端结点）。在分支结点中，每个结点的分支数就是该节点的度。

结点的高度，深度和层次。

结点的层次从树根开始定义，根节点为第一层（有些教材将根节点定义为第0层），它的子结点为第2层，以此类推。
结点的深度是从根节点开始自顶向下逐层累加的。
结点的高度是从叶节点开始自底向上逐层累加的。

树的高度

（又称深度）是树中结点的最大层数。

2.有序树和无序树

树中结点的子树从左到右是有次序的，不能交换，这样的树称为有序树。有序树中，一个结点其子结点从左到右顺序出现是有关联的。反之称为无序树。在上图中，如果将子结点的位置互换，则变为一棵不同的树。
路径和路径长度：树中两个结点之间的路径是由这两个节点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。A和K的路径长度为3.路径为B，E。

3.森林

森林是m棵互不相交的树的集合。森林的概念和树的概念十分相近，因为只要把树的根节点删掉之后就变成了森林。反之，只要给n棵独立的树加上一个结点，并且把这n棵树作为该结点的子树，那么森林就变成了树。

4.树的基本性质

• 树中结点数等于所有节点的度数+1.
• 度为m的树中第i层上之多有mi−1个结点(i≥1)
• 高度为h的m叉树至多有mh−1m−1个结点。
• 具有n个结点的m叉树的最小高度为logm(n(m−1)+1)。

二、二叉树

• 性质1: 在二叉树的第 $i$ 层上至多有$2i-1$个结点 ，第i层上至少有 1个结点？
• 性质2: 深度为k的二叉树至多有2k-1个结点，深度为k时至少有 k 个结点？
• 性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1 （即n0=n2+1）

一棵完全二叉树有5000个结点，可以计算出其叶结点的个数是（ 2500）。

性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。

二叉树的顺序存储

实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。

特点：
结点间关系蕴含在其存储位置中
浪费空间，适于存满二叉树和完全二叉树

二叉树的链式存储

三叉链表

三、树的遍历（二叉树）

遍历定义

指按某条搜索路线遍访每个结点且不重复（又称周游）。

遍历用途

它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

先(前)序遍历: 对访问到的每个结点,先访问根结点,然后是左结点,然后是右结点。

中序遍历: 对访问到的每个结点,先访问左结点,然后是根结点,然后是右结点。

后序遍历: 对访问到的每个结点,先访问左结点,然后是右结点,然后是根结点。

例如：

先(前)序遍历：

1  2  4  5  7  8  3  6 
1

中序遍历：

4  2  7  5  8  1  3  6
1

后序遍历：

4  7  8  5  2  6  3  1
1

层次遍历：

1  2  3  4  5  6  7  8
1

1.先序遍历

(1)递归写法

void PreOrder(BitTree T)
{
    if(T!=NULL)
    {
        cout<<T->val<<"  ";
        PreOrder(T->l);
        PreOrder(T->r);
    }
}
1
2
3
4
5
6
7
8
9

(2)先序非递归写法

根据先序遍历的顺序，先访问根结点，然后再访问左子树和右子树。所以，对于任意结点BitTree，第一部分即直接访问根节点，之后在判断左子树是否为空，不为空时即重复上面的步骤，直到其为空。若为空，则需要访问右子树。利用栈的先进后出，每次访问左子树时都把整个节点放到栈里面，左子树访问完了就往上走，判断父节点是否有右子树，有就访问，没有或者访问完毕就继续往上找父节点，直到将树按先序遍历方式全部遍历完毕。

void PreOrder (BitTree T)
{
　　stack<BitTree>s;
　　BitTree p = T;
　　while(p || !s.empty)
　　{
　　　　if(p)
　　　　{
　　　　　　cout<<p->val<<"  ";
　　　　　　s.push(p);
　　　　　　p = p->l;
　　　　}else
　　　　{
　　　　　　p = s.top();
　　　　　　p = p->r;
　　　　　　p = p.pop();
　　　　}
　　}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

中序遍历和后序遍历的非递归方法和先序遍历一样，改一下先后顺序即可

2.中序遍历

void InOrder(BitTree T)
{
    if(T!=NULL)
    {
        InOrder(T->l);
        printf("%d\n",T->val);
        InOrder(T->r)
    }
}
1
2
3
4
5
6
7
8
9

3.后序遍历

后序遍历的性质：对于一颗树，最后的那一个结点是根节点

void PostOrder(BitTree T)
{
    if(T!=NULL)
    {
        PostOrder(T->l);
        PostOrder(T->r);
        printf("%d\n",T->val);
    }
}
1
2
3
4
5
6
7
8
9

4.层序遍历

这棵二叉树的层序遍历次序为：A、B、C、D、F、G
每次出队一个元素，就将该元素的子节点加入队列中，直至队列中元素个数为0时，出队的顺序就是该二叉树的层次遍历结果。不懂点这里

void LevelOrder(BitTree T)
{
    queue<int>q;
    if (T == NULL){return;}
    q.push(T);
    while (!q.empty())
    {
        BitTree p=q.front();
        cout<<p.val;
        q.pop();
        if(p.l)
            q.push(p.l);
        if(p.r)
            q.push(p.r);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

以上四种种遍历算法中递归遍历左子树和右子树的顺序都是固定的，只是访问根节点的顺序不同。不管采用何种遍历方法，每个结点都是访问一次，所以时间复杂度就是O(n)。

在递归遍历中，递归工作栈的深度恰巧是树的深度，所以在最坏的情况下，二叉树是有n个结点且深度为n的单支树，递归遍历算法的时间复杂度是O(n)。

四、二叉树遍历算法的应用

1.二叉树的建立

void CreateBiTree(BiTree &T）{
	cin>>ch;
	if (ch==’#’)   
		T=NULL;  	//递归结束，建空树
	else {
	    T=new BiTNode;    
	    T-＞data=ch; 	//生成根结点
	    CreateBiTree(T-＞lchild);  //递归创建左子树
 	    CreateBiTree(T-＞rchild); //递归创建右子树
  }									
}										

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

2.计算二叉树结点总数

如果是空树，则结点个数为0；
否则，结点个数为左子树的结点个数+右子树的结点个数再+1。

int NodeCount(BiTree T){
	if(T == NULL ) return 0;  			    
	else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
} 
1
2
3
4

有线段树那味了

3.计算二叉树叶子结点总数

如果是空树，则叶子结点个数为0； 否则，为左子树的叶子结点个数+右子树的叶子结点个数。

int LeadCount(BiTree T){
 	if(T==NULL) 	//如果是空树返回0
		return 0;
	if (T->lchild == NULL && T->rchild == NULL)
		return 1; //如果是叶子结点返回1
	else return LeafCount(T->lchild) + LeafCount(T->rchild);
}
1
2
3
4
5
6
7

4.计算二叉树深度

• 如果是空树，则深度为0；
• 否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者加1。

int get_deep(tree *p){
    if(p == NULL)
        return 0;
    return max(deep(p->l),deep(p->r))+1;
}
1
2
3
4
5
6

5. 重要结论

若二叉树中各结点的值均不相同，则： 由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，
但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。

由中序遍历可以知道左右子树的结点个数。

6.由中序遍历和后序遍历建树

五、森林

左指针指的是左孩子，右指针指的是兄弟，这样就避免了一颗多叉树需要像二叉树一样的每一个结点使用多个指针的情况了。



2.答案：

六、$Huffman$树

huffman树不唯一！

七、相关作业习题

1.选择判断

1.完全二叉树一定存在度为1的结点。

答案：×
满二叉树也是完全二叉树，其叶子结点的度为0。

2.哈夫曼树的结点个数不能是偶数

答案：√

假设哈夫曼树是二叉的话，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。

二叉树可以为空

3.树形结构中元素之间存在一个对多个的关系。

答案：√
树形结构元素之间存在一对多的关系，线性结构元素之间存在一对一的关系，图形结构元素之间存在多对多的关系。

4.用一维数组存储二叉树时,总是以前序遍历顺序存储结点

答案：×
总是以层次遍历的顺序存储，并且按照完全二叉树的方式建立，所以有很多空节点，会浪费存储空间，完全二叉树可以非常方便地找到孩子兄弟和双亲

5.若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序序列中的最后一个结点。

若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。

6.以下说法错误的是 ( )
A哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
B若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。
C已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。
D在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。
答案：D

7.给定一棵树，可以找到唯一的一棵二叉树与之对应。

答案：√

8.二叉树是一种特殊的树。

答案：×
9.二叉树的遍历只是为了在应用中找到一种线性次序。

答案：√

艹
10.完全二叉树中,若一个结点没有左孩子,则它必是树叶()

答案：√

若深度为1，则该结点即为根结点，又为叶子结点

11.已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为?
A.CBEFDA
B.FEDCBA
C.CBEDFA
D.不定

答案：A
12.先序遍历ABCDEF可知A为根节点，然后中序遍历CBAEDF可知CB为A的左子树，EDF为A的右子树，对于左子树，先序遍历为BC，可知B为根节点，中序遍历为CB，C为其左子树，右子树分析一样。
8.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )。

A．9
B．11
C．15
D．不确定

正确答案
B
答案解析
对任何一棵二叉树，如果终端结点数为n0，度为2的结点数为n2，则一定有n0=n2+1。所以n0=10+1=11，而与n1无关。

13.一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( )个结点
2h-1
2h+1
h+1

正确答案：B

根的高度是0

2.编程题

11.建立与遍历二叉树 (25分)

以字符串的形式定义一棵二叉树的先序序列，若字符是‘#’, 表示该二叉树是空树，否则该字符是相应结点的数据元素。读入相应先序序列，建立二叉链式存储结构的二叉树，然后中序遍历该二叉树并输出结点数据。
输入格式:
字符串形式的先序序列（即结点的数据类型为单个字符）
输出格式:
中序遍历结果
输入样例:
在这里给出一组输入。例如：
ABC##DE#G##F###

输出样例:
在这里给出相应的输出。例如：
CBEGDFA

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<math.h>
#include<cstring>
#include<bitset>
#include<vector>
#include<queue>

//#define ls (p<<1)
//#define rs (p<<1|1)

#define over(i,s,t) for(register int i = s;i <= t;++i)
#define lver(i,t,s) for(register int i = t;i >= s;--i)
//#define int __int128
#define lowbit(p) p&(-p)
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5+7;
const int M = 2007;

char ch;

struct node{
    char val;
    node *ls;
    node *rs;
};

void build(node *&t){//注意要用引用变量
    cin>>ch;
    if(ch == '#')t = NULL;
    else {
        t = new node;
        t->val = ch;
        build(t->ls);
        build(t->rs);
    }
}

void print(node *t){
    if(t){
        print(t->ls);
        cout<<(t->val);
        print(t->rs);
    }
}

void solve(){
    node *t = NULL;
    build(t);
    print(t);
}
int main()
{
    solve();
    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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62