初级数据结构：树与二叉树_二叉树2的n次方-1

编者前言

学二叉树就是学递归，多画图，多画图

对一颗二叉树的操作，就是对当前结点的操作，结合需求，进行递归。

---

树的概念

树，一个根节点，有多个子节点：

每个子结点也可以作为双亲（根）节点，有多个子节点。

当两个孩子（子）节点有一个共同的双亲结点，则称这两个节点互为兄弟节点。

一个双亲节点所拥有的孩子节点个数，称为该节点的“度”。

度不为0的节点，也称为为分支节点；度时0的节点，叫做叶节点或者终端节点。

根节点所在的层一般称为第一层；该树最多有几层，称作树的高度或者深度。–h或k

根节点以下的所有节点都是根节点的子孙节点；

多棵不相交的树的集合称作森林。

---

树与非树

从一个根节点出发到最后一层的子孙节点，这一条路径称作该根节点的子树。

• 每个子树间不相交，有N个节点的树，则有N-1条边。

---

树的表示

经典表示法，每个节点都有一个孩子节点指向自己第一个的孩子，有一个兄弟节点指向自己的兄弟。
应用场景，文件系统等。

typedef int DataType;
struct Node
{
 struct Node* _firstChild1;  第一个孩子结点
 struct Node* _pNextBrother;  指向其下一个兄弟结点
 DataType _data;  结点中的数据域
};
1
2
3
4
5
6
7

---

二叉树

• 每个节点最多有两个节点的树。

  • 二叉树最多有两个子树，左子树，右子树，依次递减；只有左子树或只有右子树；只有根节点；空树。

• 第n层的节点个数，最多有2的n–1次方个。
• 如果每一层的节点都达到最大值，则该树称作满二叉树。一个满二叉树的总节点有2的n次方–1个。
  

1. 满二叉树是完全二叉树的一个子集。
2. 一个完全二叉树的前n–1层，是满二叉树；
3. 第n层的节点没有达到最大值，且从左往右依次排列，中间不能有空节点。
4. 由此可知，一个完全二叉树的度为1的节点最多只有一个。
   

• 一个完全二叉树，最多拥有的节点总个数同满二叉树；
• 最少拥有的节点总个数：
  • 前n–1层是满的，第n层至少有一个，因此是：2的n–1次方–1 个+1个-------2的n–1次方个。
  • 前n—1层总个数和是奇数，加一个则为偶数。
• 一个完全二叉树，度为0的叶节点个数，总比，度为2的分支节点个数多一个。

以上都是将二叉树的根节点作为第一层的性质。

---

对于任意一个二叉树的前，中，后，层序遍历

先把二叉树填充至满二叉树，空的用空表示。

• 前中后序遍历属于深度优先遍历，深度用递归；层序遍历用队列。
• 前序遍历：根，左子树，右子树；中序遍历：左子树，根，右子树；后续遍历：左子树，右子树，根。
• 以前序为例，根，左子树又包含：根，左子树，右子树；…当最后一层左子树都走到叶子节点处，叶子节点的左子树为空，此时再看向右子树，也为空返回；再回看上一层的右子树…根的右子树同理。
• 层序：一层一层的遍历。
• 复杂度分析
  • 时间复杂度：O(N)，其中 N 是二叉树的节点数。每个节点恰好被遍历一次。
  • 空间复杂度： **O(N)**其中 N 是二叉树的节点数，为递归过程中栈的开销。平均情况下是 O（log2N） ，最坏的情况下树呈现链状，为 O(N) 。
• 二叉树深度优先遍历算法按照分治模式求解
  • 分解：将二叉树分成左子树、根和右子树，三棵子二叉树进行遍历
  • 解决：用二叉树深度优先遍历算法对左子树、根和右子树进行遍历
  • 合并：合并左子树、根和右子树的遍历结果得到遍历结果

---

定义树结点

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//数据
typedef char BinaryTrDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* _left;  		指向左孩子
	struct BinaryTreeNode* _right; 		指向右孩子
	BinaryTrDataType data;
	
}BTNode;            			二叉树结点类型

//申请并初始化一个二叉树节点
BTNode* AskBinTreeNode(BinaryTrDataType x)
{
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		printf("AskBTNode Failed\n");
		exit(-1);
	}
	root->_left = root->_right = NULL;
	root->data = x;
	return root;
}
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

---

创建树

BTNode* CreateBinTree()
{
	BTNode* ra = AskBinTreeNode('A');
	BTNode* rb = AskBinTreeNode('B');
	BTNode* rc = AskBinTreeNode('C');
	BTNode* rd = AskBinTreeNode('D');
	BTNode* re = AskBinTreeNode('E');
	BTNode* rf = AskBinTreeNode('F');
	ra->_left = rb;
	ra->_right = rc;
	rb->_left = rd;
	rb->_right = re;
	rc->_right = rf;
	return ra;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

遍历测试代码

int main()
{
	//创建一个二叉树
	BTNode* root = CreateBinTree();
	printf("二叉树的前序遍历：\n");
	BinTreeFrontErgodic(root);

	printf("\n");
	printf("\n");

	printf("二叉树的中序遍历：\n");
	BinTreeCentralErgodic(root);

	printf("\n");
	printf("\n");

	printf("二叉树的后序遍历：\n");
	BinTreeRearErgodic(root);
	printf("\n");
	printf("\n");
	return  0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

前序遍历

void  BinTreeFrontErgodic(BTNode* root)
{
	递归结束的标志，遍历整个树，最后那个节点
	的左右孩子都为空就停止搜寻。
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	如果根节点不为空，则打印根存放的数据
	printf("%c ", root->data);
	BinTreeFrontErgodic(root->_left);
	BinTreeFrontErgodic(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

中序遍历

void  BinTreeCentralErgodic(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinTreeCentralErgodic(root->_left);
	printf("%c ", root->data);
	BinTreeCentralErgodic(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11

---

后序遍历

void BinTreeRearErgodic(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	看他左孩子是不是空
	BinTreeRearErgodic(root->_left);
	左孩子找完，则找右孩子
	BinTreeRearErgodic(root->_right);
	此函数的节点永远是这一层的根，最后打印
	printf("%c  ", root->data);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

二叉树总结点个数

int BinTreeNodeSize(BTNode* root)
{
	//若根结点为空，返回0
	if (root == NULL)
	{
		return 0;
	}
	/若根不是空，则统计它左右孩子结点的个数;
	/如果我左右孩子结点都为空，证明下面没有节点了，只有我一个根节点。
	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	}
	return 1 + BinTreeNodeSize(root->_left) + BinTreeNodeSize(root->_right);

	/return root == NULL ? 0: 1 +BinTreeNodeSize(root->_left) + BinTreeNodeSize(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

二叉树的高度或深度

我当前根结点为空就返回0，
当我的左右孩子为空，则只有一层；否则就每访问到一次我的孩子结点就加一层；
然后比较左子树和右子树，谁访问的层数多，就返回谁。

int BinTreeTiers(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return (root->_left == NULL ? 0 : 1 + BinTreeTiers(root->_left)) >
		(root->_right == NULL ? 0 : 1 + BinTreeTiers(root->_right)) ?
		1 + BinTreeTiers(root->_left) : 1 + BinTreeTiers(root->_right);
}
1
2
3
4
5
6
7
8
9
10

二叉树第K层结点个数

等于找K-1层左子树孩子结点个数 加上 k-1 层右孩子节点个数。
二叉树一个节点最多两个分支，

1. 当k= 1 ，意味着第一层只有一个节点；
2. 递归了K-1层，到了第K（最后一）层，单颗左子树递归下来，只有两种情况，有一个或没有
3. 返回再去找你的右子树。

int BTKTierNodeNumber(BTNode* root, int k)
{
		if (root == NULL)
		{
			return 0;
		}
		if (k==1)
		{
		return 1;
		}
		/第k层结点个数 等于 k-1层 左子树结点个数 + k-1层右子树结点个数 
		return BTKTierNodeNumber(root->_left, k - 1) +
			BTKTierNodeNumber(root->_left, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

查找值为X的二叉树结点

BTNode* BinTreeFindData(BTNode* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	/对一棵二叉树的操作就是对一个节点的操作，因为二叉树的结点类型相同，其他结点递归调用即可
	/则找我左树有没有，没有再去找我的右子树，
	BTNode* retl = BinTreeFindData(root->_left, x);
	if (retl)
	{
		return retl;
	}
	/走到这里说明，左子树没有，直接返回右子树即可。
	return BinTreeFindData(root->_right, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

层序遍历，需要用队列

需要用到，队列销毁，队列创建，入队，出队，队列头部元素

结果论：

1. 把根节点入队，展示队列头元素，用二叉树节点变量接收，根节点出队
2. 同时根节点的左孩子先入对，接着右孩子
3. 先入先出，重复以上

void BinTreeTierErgodic(BTNode* root)
{
	QL bt;
	QueInit(&bt);
	if (root)
	{
		QuePush(&bt, root);
	}
	while (!QueueEmpty(&bt))
	{
		BTNode* front = QueFront(&bt);
		QuePop(&bt);
		printf("%c ", front->data);
	
		if (front->_left)
		{
			QuePush(&bt, front->_left);
		}
		if (front->_right)
		{
			QuePush(&bt, front->_right);
		}
	}
	QueDestory(&bt);
}
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

---

编者寄语

说实话，我也不是都能理解