【数据结构】6.1 二叉树（C语言）

【数据结构】——6.1 二叉树

一、树的概念和结构

1. 树的概念

​ 树（Tree）：树是一种非线性的数据结构，它是由n个有限结点组成一个具有层次关系的集合。

​ 树有一个特殊的结点，称为根结点，根节点没有前驱结点

​ 除根节点外，其余结点被分成M(M>0)个互不相交的集合，其中每一个集合又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继，因此，树是递归定义的。

​ 树形结构子树不能有交集，否则就不是树，而是另一种数据结构 图

2. 树的相关概念

• 节点的度：一个节点含有的子树个数

• 叶子节点（终端节点）：度为0的节点就是叶子节点

• 分支节点（非终端节点）：度不为0的节点

• 双亲结点（父节点）：若一个结点含有一个子节点，则该节点为子节点的父节点

• 兄弟节点：具有相同父节点的节点，兄弟节点都是亲兄弟

• 堂兄弟节点：双亲在同一层的节点叫做堂兄弟节点

• 祖先：从根节点到该节点经过的所有节点

• 子孙：以某节点为根的子树中的任意节点都叫该节点的子孙

• 节点的层次：从根处开始，根为第1层，子节点为第2层，以此类推

• 树的度：树中的最大的节点的度就是树的度

• 树的高度（深度）：树中节点的最大层次

• 森林：不相交的树的集合叫森林

3. 树的结构定义

​ 树结构的存储结构就比较复杂，若使用指针指向每个节点的子节点，则每个节点的子节点数量不同，定义固定数量的指针就会出现浪费或溢出的情况，所以我们介绍最常用的树的存储方法

​ 树结构声明

struct Tree
{
	DataType* data;
    struct Tree* child_1;
    struct Tree* child_2;
    ...					//此处又该定义几个孩子指针呢
};
1
2
3
4
5
6
7

​ 以上的存储方式显然是不好的，即便是定义成指针数组，也可能会出现大量的浪费或者溢出现象。

3.1 孩子兄弟表示法

​ 每一个节点都有一个指向自己的左孩子的指针，和一个指向右兄弟的指针。节点可以通过左孩子指针找到自己的左孩子，，再利用孩子的右兄弟指针找到自己的所有孩子。结构图如下

​ 兄弟表示法的声明

struct Tree
{
    DataType* data;		//数据域
    struct Tree* _firstChild;	//第一个孩子的指针
    struct Tree* _nextBrother;	//下一个兄弟的指针
};
1
2
3
4
5
6

3.2 双亲表示法

​ 使用线性的存储结构存储每个节点，并将它们的父节点下标也进行存储，通过子节点找父节点的方式遍历树

​ 此方式使用-1下标来表示根节点

二、二叉树的概念及结构

1. 二叉树的概念

​ 二叉树：每个节点最多只有2个子节点的树

1. 二叉树可以为空
2. 二叉树有左右之分，分为左孩子和右孩子，不可颠倒，所以二叉树是有序树
3. 二叉树左孩子的子树称为左子树，右孩子的子树称为右子树

2. 二叉树的存储结构

2.1 顺序结构

​ 二叉树的顺序结构一般只适用于完全二叉树，堆的实现就是顺序结构，非完全二叉树中空缺的位置会浪费大量空间

2.2 链式结构

• 二叉链表：二叉树一般使用链式存储结构，使用左右孩子指针指向子节点，这样的二叉树被称为二叉链表
• 三叉链表：二叉树的结点有左右孩子的指针，和指向父节点的指针，这样的二叉树成为三叉链表

二叉链表的结构体声明：

typedef int BTDataType;
typedef struct BTree
{
    struct BTree* left;
    struct BTree* right;
    BTDataType data;
} BTNode;
1
2
3
4
5
6
7

三叉链表的结构体声明：

typedef int BTDataType;
typedef struct BTree
{
    struct BTree* left;
    struct BTree* right;
    struct BTree* parent;
    BTDataType data;
} BTNode;
1
2
3
4
5
6
7
8

3. 特殊的二叉树

3.1 满二叉树

​ 满二叉树：二叉树的每一层都到达最大节点数，那么二叉树就是慢二叉树

3.2 完全二叉树

​ 完全二叉树：对于深度为k的二叉树而言，前k-1层满节点数，，第k层节点可以不满，但是节点必须是与满二叉树中的编号对应的，完全二叉树是一个很高效的数据结构

​ 满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树

4. 二叉树性质

1. 若根节点层数为1，则第i层最多有 $2^{i-1}$ 个节点
2. 深度为h的二叉树，最大节点数是 $2^h-1$ 个
3. 对于任何二叉树，若是度为0的叶子节点有$n_0$个，度为2的分支节点有$n_2$个，则一定有 $n_0=n_2+1$
4. 若对于n个节点的满二叉树，其深度为 $h=lo{g}_2(n+1)$
5. 对于n个节点的完全二叉树，对其依次进行0~n的编号，则有：
   1. 若$i>0$，则i的双亲结点的序号为 $(i-1)/2$
   2. 若$2i+1<n$，则左孩子序号为 $2i+1$
   3. 若$2i+2<n$，则右孩子序号为 $2i+2$

三、二叉树的实现

1. 二叉树结构定义

typedef char BTDataType;
typedef struct BTreeNode
{
	BTDataType data;
	struct BTreeNode* left;
	struct BTreeNode* right;
}BTNode;
1
2
3
4
5
6
7

2. 创建二叉树

1. 创建二叉树使用前序遍历，先创建根节点，再创建左右子节点
2. 输入二叉树的前序遍历结果的字符串构建二叉树，使用#来表示NULL
3. 参数中s为字符串，pi为当前下标的指针，由于每次调用函数下标都要加一，必须使用传址调用，所以使用下标的指针

BTNode* BinaryTreeCreate(BTDataType* s, int* pi)
{
    if (s[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    
    //创建节点并赋值
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    node->data = s[*pi];
    (*pi)++;
    
    //创建左子树和右子树
    node->left = BinaryTreeCreate(s, pi);
    node->right = BinaryTreeCreate(s, pi);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3. 遍历二叉树

3.1 先序遍历

1. 使用递归分治思想，先访问根节点，再访问左子树，最后访问右子树
2. 若是访问的节点为NULL，则停止访问

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11

3.2 中序遍历

1. 使用递归分治思想，先访问左子树，再访问根节点，最后访问右子树
2. 若是访问的节点为NULL，则返回

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	PreOrder(root->left);
    printf("%c ", root->data);
	PreOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11

3.3 后序遍历

1. 使用递归分治思想，先访问左子树，再访问右子树，最后访问根节点
2. 若是访问的节点为NULL，则返回

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	PreOrder(root->left);
	PreOrder(root->right);
    printf("%c ", root->data);
}
1
2
3
4
5
6
7
8
9
10
11

3.4 层序遍历

1. 层序遍历要使用队列辅助完成，队列接口已给出
2. 将节点压入队列，然后每出队列一个节点就将其子节点压入队列
3. 压入节点时要压入整个节点，这样可以通过出队列的节点找到它的子节点，不能只吧值压入队列

//队列接口
void QueueInit(Queue** ppq);				//初始化
void QueuePush(Queue** ppq, QDataType x);	 //入队列
void QueuePop(Queue** ppq);					//出队列
QDataType QueueFront(Queue* pq);			//获取队头元素
_Bool QueueEmpty(Queue* pq);				//判空
void QueueDestroy(Queue** ppq)				//销毁队列
1
2
3
4
5
6
7

void LevelOrder(BTNode* root)
{
    Queue pq = NULL;
    QueueInit(&pq);
    
    //若根节点存在，则入队列
    if (root != NULL)
    {
        QueuePush(&pq, root);
    }
    
    //若队列不为空
    while (!QueueEmpty(pq))
    {
        //该节点出队列，并打印其值
        BTNode* node = QueueFront(pq);
        QueuePop(&pq);
        printf("%c ", node->data);
        
        //该节点的子节点入队列
        if (node->left != NULL)
        {
            QueuePush(&pq, node->left);
        }
        if (node->right != NULL)
        {
            QueuePush(&pq, node->right);
        }
    }
    printf("\n");
    
    QueueDestroy(&pq);
}
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

4. 节点个数

4.1 获取二叉树节点个数

1. 使用递归分治思想，获取左子树的节点数和右子树的节点数之和，再加上根节点自己的数量就是树的节点个数
2. 若是访问的节点为NULL，则返回0，否则返回三者之和

int BTreeSize(BTNode* root)
{
	return root == NULL ? 0 
        : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}
1
2
3
4
5

4.2 获取叶子节点个数

1. 使用递归分治思想，获取左子树的叶子节点个数，再加上右子树的叶子节点个数，就是树的叶子节点个数
2. 若是访问的节点为NULL，则返回0，若是访问到叶子节点，则返回1，否则返回二者之和

int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return BTreeSize(root->left) + BTreeSize(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.3 获取第k层节点个数

1. 使用递归分治思想，获取左子树k-1层的节点数，加上右子树k-1层的节点数，就是第k层的节点数
2. 若是访问的节点为NULL，则返回0， 若是为第k层节点，则返回1，否则返回二者之和

int BTreeKLevel(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}

	return BTreeKLevel(root->left, k - 1) + BTreeKLevel(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5. 树的深度

1. 使用递归分治思想，获取左子树的深度和右子树的深度，返回最深的深度并加上自己这一层
2. 若是访问的节点为NULL，则返回0，否则返回最深的深度与自己层数之和

int BTreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int left = BTreeHeight(root->left);
	int right = BTreeHeight(root->right);
	return (left > right ? left : right) + 1;
}
1
2
3
4
5
6
7
8
9
10
11

6. 查找值为x的节点

1. 使用递归分治思想，先对比自己的值，若是为查找值则返回自己节点的地址
2. 若不是查找值，先去左子树查找，若查找到则返回，若查找不到再去右子树查找，查找到返回结果，还是没有则返回NULL
3. 若是访问的节点为NULL，则返回0， 否则进行值的对比和左右子树的查找

BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	
    //如果值为当前节点，则返回当前节点
	if (root->data == x)
	{
		return root;
	}

    //若值为左孩子，则返回左孩子
	BTNode* left = BTreeFind(root->left, x);
	if (left != NULL)
	{
		return left;
	}
	
    //若值为右孩子，则返回右孩子
	BTNode* right = BTreeFind(root->right, x);
	if(right != NULL)
	{
		return right;
	}
	
    //若都不是，则没找到，返回NULL
	return NULL;
}
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

7. 销毁二叉树

​ 销毁二叉树使用后序遍历，先销毁左右子树，再销毁当前节点，先销毁当前节点会丢失子树的地址

void BinaryTreeDestory(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    
    BinaryTreeDestory(root->left);
    BinaryTreeDestory(root->right);
    free(root);
}
1
2
3
4
5
6
7
8
9
10
11

四、完整代码

代码保存在gitee中：点击完整代码参考