二叉树的详细实现(含递归展开图)

一、二叉树

1. 概念

一颗二叉树是结点的有限集合，该集合或者为空，或者由一个根节点加上两棵别称为左子树和右子树的二叉树的组成

2.特点

每个结点最多有两棵子树，即二叉树不存在大于2的结点
二叉树的子树有左右之分其子树次序不能颠倒

3.特殊二叉树

1.满二叉树

一个二叉树，如果每一个层的结点都达到最大值，则这个二叉树就是满二叉树，也就是说如果一个二叉树的层数为k,结点总数为(2^k)-1，则就为满二叉树

2.完全二叉树

对于深度为k的，有n个结点的二叉树，且仅当其每一个结点与深度为k的满二叉树中编号从1到n的结点，称为完全二叉树

4.性质

性质1.

若规定根节点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)个结点

性质2.

若规定根节点的层数为1，则深度为h的二叉树的最大结点数是(2^h)-1

性质3.

对于任何一颗二叉树，如果度为0其叶结点个数为n0,度为2的分支节点个数为n2,则n0=n2+1
(有几个子树 ，度就为多少)

性质4.

若规定根节点的层数为1，具有n个结点的满二叉树的深度h=log N
2^h -1=N
2^h=N+1
h= log 2 N+1
但是由于大O渐进表示法的省略 ，时间复杂度化成 O(log N)
不太懂大O渐进表示法的 :时间复杂度与空间复杂度

二、二叉树整体实现

1.前序的实现

void  prevorder(BTnode* root)//前序  根 左子树 右子树
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	prevorder(root->left);
	prevorder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11

递归展开图

2.中序的实现

void  inorder(BTnode* root)//中序 左子树 根 右子树
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	inorder(root->left);
	printf("%c ", root->data);
	inorder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11

递归展开图

---

3.后序的实现

void  postorder(BTnode* root)//后序 左子树 右子树 根
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	postorder(root->left);
	postorder(root->right);
	printf("%c ", root->data);
}
1
2
3
4
5
6
7
8
9
10
11

递归展开图

4. 节点个数

int treesize(BTnode* root)//节点个数
{
	if (root == NULL)
	{
		return 0;
	}
	return treesize(root->left) + treesize(root->right) + 1;
}
1
2
3
4
5
6
7
8

递归展开图

5. 叶节点个数

int treeleafsize(BTnode* root)//叶子节点的个数
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)//只有当左右子树都为NULL时才会返回1
	{
		return  1;
	}
	 return treeleafsize(root->left)+ treeleafsize(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

递归展开图

6.层序遍历

void levelorder(BTnode* root)//层序遍历 需要借助数据结构栈来实现
{
	queue q;
	queueinit(&q);//初始化栈
	if (root)
	{
		queuepush(&q, root);//将根结点入栈
	}
	while (!queueempty(&q))
	{
		 datatype front=queuefront(&q);//出栈
		 queuepop(&q);//删除栈顶元素
		 printf("%c ", front->data);
		 if (front->left != NULL)
		 {
			 queuepush(&q, front->left);//判断此时该结点的左子树是否为空 若不空则入栈
		 }
		 if (front->right != NULL)
		 {
			 queuepush(&q, front->right);//判断此时该结点的右子树是否为空 若不空则入栈
		 }
	}
	queuedestroy(&q);//销毁内存
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24