• 二叉树正传 - 二叉树的基本操作及构建

    目录

    前言

    在二叉树前传中简要介绍了二叉树的概念及结构，没看的请戳：二叉树前传。
    本篇会着重介绍二叉树的操作，了解二叉树的前中后序遍历以及链式二叉树的构建。

    1. 二叉树的性质

    1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2 i − 1 2^{i-1} 2i−1 个结点。
    2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2 h − 1 2^{h}-1 2h−1。

    每层个数：20 + 21 + … + 2(h-1)
    利用错位相减可以得到结点总数为2h - 1。

    1. 对任何一棵二叉树, 如果度为0其叶结点个数为 n 0 n_{0} n0​, 度为2的分支结点个数为 n 2 n_{2} n2​, 则有 n 0 n_{0} n0​ ＝ n 2 n_{2} n2​ + 1。

    如果只有一个结点，那么 n 0 n_{0} n0​ = 1， n 2 n_{2} n2​ = 0，左子树添加一个结点，此时 n 0 n_{0} n0​ = 1， n 1 n_{1} n1​ = 1， n 2 n_{2} n2​ = 0，再在右子树添加一个结点，此时 n 0 n_{0} n0​ = 2， n 1 n_{1} n1​ = 0， n 2 n_{2} n2​ = 1，以此类推， n 0 n_{0} n0​永远会比 n 2 n_{2} n2​多一个。
    注意：一棵树中是允许没有度为1( n 1 n_{1} n1​) 的结点，如果是完全二叉树有且最多只有一个。
    在这里插入图片描述

    1. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= l o g 2 ( n + 1 ) log_2{(n+1)} log2​(n+1) 。

    高度为h的完全二叉树的结点范围在【2(h-1), 2h - 1】,那么h的范围在【 l o g 2 n + 1 log_2{n+1} log2​n+1， l o g 2 ( n + 1 ) log_2{(n+1)} log2​(n+1) 】。

    1. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
    • 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
    • 若2i+1=n否则无左孩子
    • 若2i+2=n否则无右孩子

    父子结点下标在前面堆的文章中介绍过，就不在详细证明。

    1.1 性质选择题

    在了解了上面的概念后，下面几道题目就很简单了。

    1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
      A 不存在这样的二叉树
      B 200
      C 198
      D 199

    根据第三条性质， n 0 n_{0} n0​ ＝ n 2 n_{2} n2​ ＋1，因此选B。

    1. 下列数据结构中，不适合采用顺序存储结构的是（ ）
      A 非完全二叉树
      B 堆
      C 队列
      D 栈

    堆和栈都适合，前面就是用顺序结构实现的，而队列和非完全二叉树则不适合，因为是单选题，选一个最不适合的就是A了。
    在这里插入图片描述
    如果是多选，可以把C也选上。

    1. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
      A n
      B n+1
      C n-1
      D n/2

    还是根据第三条性质：2n = n 0 n_{0} n0​ + n 1 n_{1} n1​ ＋ n 2 n_{2} n2​
    ∵ n 0 n_{0} n0​ ＝ n 2 n_{2} n2​ + 1
    ∴ n 2 n_{2} n2​ ＝ n 0 n_{0} n0​ - 1
    ∴ 2n = n 0 n_{0} n0​ + n 1 n_{1} n1​ + n 0 n_{0} n0​ - 1
    合并得 2n = 2 n 0 2n_{0} 2n0​ + n 1 n_{1} n1​ - 1
    又∵ 2n是一个整数
    ∴ 当 n 1 n_{1} n1​ = 1时，等式成立
    即 2n = 2 n 0 2n_{0} 2n0​
    得 n = n 0 n_{0} n0​
    所以选A。

    1. 一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
      A 11
      B 10
      C 8
      D 12

    根据第四条性质，完全二叉树的结点范围【2(h-1), 2h - 1】，先把10拿出来带入算一下，【512，1023】，该树的结点个数范围正好在这个区间内，因此B即为这棵树的高度。

    1. 一个具有767个节点的完全二叉树，其叶子节点个数为（）
      A 383
      B 384
      C 385
      D 386

    和第四题非常类似，只不过2n换成了一个具体的数，求得答案为B。

    2. 二叉树的存储结构

    二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

    1. 顺序存储
      顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
      在这里插入图片描述
    2. 链式存储
      二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所
      在的链结点的存储地址 。链式结构又分为二叉链和三叉链，到高阶数据结构如红黑树等会用到三叉链。
      在这里插入图片描述
      在这里插入图片描述

    前面着重用顺序结构来实现完全二叉树的堆，而本篇则着重使用链式存储来实现普通二叉树。

    typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{ 
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    3. 二叉树链式结构的基本操作

    再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：

    1. 空树
    2. 非空：根节点，根节点的左子树、根节点的右子树组成的.
      在这里插入图片描述

    二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的，也就是每个结点又会分为：根、左子树、右子树。

    3.1 前中后序遍历

    学习二叉树结构，最简单的方式就是遍历。

    所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。

    遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
    在这里插入图片描述
    按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

    typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* CreateTree()
{
	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	assert(n1);
	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
	assert(n2);
	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
	assert(n3);
	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
	assert(n4);
	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
	assert(n5);
	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
	assert(n6);
	//BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));
	//assert(n7);

	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;
	n6->data = 6;
	//n7->data = 7;

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n2->right = NULL;
	n4->left = n5;
	n4->right = n6;
	n3->left = NULL;
	n3->right = NULL;
	n5->left = NULL;
	n5->right = NULL;
	n6->left = NULL;
	n6->right = NULL;

	//n3->right = n7;
	//n7->left = NULL;
	//n7->right = NULL;

	return n1;
}

    • 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

    以下操作都是基于以上构建的二叉树。

    1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

    即先访问根，再访问左子树，最后访问右子树

    void PreOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	//根
	printf("%d ", root->data);
	//左子树
	PreOrder(root->left);
	//右子树
	PreOrder(root->right);
}

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

    代码递归展开图：

    在这里插入图片描述

    1. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

    先访问左子树，再访问根，最后访问右子树

    void InOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    1. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

    先访问左子树，再访问根右子树，最后访问根

    void PostOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

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

    不难看出这三种的遍历代码实现是非常类似的，只是根的访问顺序不同，代码很简单，但最重要的是递归调用的逻辑要理清楚。

    由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

    3.2 结点个数

    把大问题分成一个个规模相似的子问题，大概思路：结点个数 = 自己 + 左子树的结点个数 + 右子树的结点个数

    int TreeSize(BTNode* root)
{
	if (!root)
	{
		return 0;
	}
	return 1 + TreeSize(root->left) + TreeSize(root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    递归展开：
    在这里插入图片描述

    3.3 叶子结点个数

    思路：当此结点不是空也不是叶子，就继续递归寻找叶子，找到叶子就返回1，空返回0，把左子树和右子树的叶子结点相加就是要求的个数了。

    int TreeLeavesSize(BTNode* root)
{
	if (!root)
	{
		return 0;
	}
	if (!root->left && !root->right)
	{
		return 1;
	}
	return 	TreeLeavesSize(root->left) + TreeLeavesSize(root->right);
}

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

    3.4 树的高度

    思路：分别递归求出各自的左右子树的高度，别把高的子树+1返回就是要求的树的高度了。

    int TreeHeight(BTNode* root)
{
	if (!root)
	{
		return 0;
	}
	int LH = TreeHeight(root->left);
	int RH = TreeHeight(root->right);
	return LH > RH ? LH + 1 : RH + 1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    3.5 第k层结点的个数

    思路：当前根的第k层相当于它的左右子树的第k-1层，不断递归左右子树，当k=1时，就是第k层的结点。

    int TreeKLevel(BTNode* root, int k)
{
	if (!root || !k)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

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

    3.6 返回x的结点

    思路：先去左树找，找到了直接返回，否则去右树找。

    BTNode* FindNodeofX(BTNode* root, BTDataType x)
{
	if (!root)
	{
		return NULL;
	}
	if (root->data == x)
	{							 
		return root;
	}	
	BTNode* ret = FindNodeofX(root->left, x);
	if (!ret)
	{
		ret = FindNodeofX(root->right, x);
	}
	return ret;
}

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

    该操作还有一个主要作用是：可以充当修改操作，找到了该结点的指针，就可以修改该结点的数据。

    3.7 层序遍历

    之所以要把层序遍历放在这里是因为，该操作相较于其它操作是比较复杂，因为要用到非递归 + 队列来辅助实现。

    画图解释：
    在这里插入图片描述
    思路：上一层出队列的时候，带入它的下一层入队列。

    #include "Queue.h"
//队列的实现这里就不展开了
// 层序遍历
void LevelOrder(BTNode* root)
{
	if (!root)
	{
		return;
	}
	Queue q;
	QueueInit(&q);
	//先把根入队列
	QueuePush(&q, root);
	//队列不为空就继续
	while (!QueueEmpty(&q))
	{
		//获取队头的根
		BTNode* front = QueueFront(&q);
		//队头出队列，但是front依然保存着队头数据
		QueuePop(&q);
		printf("%d ", front->data);

		//不为空就把它的下一层入队列
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	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
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    3.8 判断二叉树是否是完全二叉树

    该操作是层序遍历的变形，比层序难一些。

    完全二叉树：前h-1层是满的，最后一层不要求满，但必须从左到右是连续的。

    大思路：还是用队列辅助，一层一层走，如果出现空了，那么后面就不能再出现空，否则就不是完全二叉树。

    int BinaryTreeComplete(BTNode* root)
{
	if (!root)
	{
		return 0;
	}
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//如果front为空就跳出循环
		if (!front)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//如果队列后面全是空则为完全二叉树
	//否则不是
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//不为空就不是了
		if (front)
		{
			QueueDestroy(&q);
			return 0;
		}
	}
	QueueDestroy(&q);
	return 1;
}

    • 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

    4. 二叉树的构建和销毁

    通过前序遍历的数组构建二叉树。例如如下的先序遍历字符串：ABC###DE##F## 其中“#”表示的是空格，空格字符代表空树。
    题目OJ：构建二叉树

    思路：题目已经很明确了，先序遍历的顺序是根，左子树，右子树，所以以例子来看，遇到A先构建A，然后递归构建A的左子树B，B的左子树C，C的左子树是空，右子树是空，返回构建B的右子树，是空返回，再构建A的左子树D，D的左子树E，E的左子树是空右子树是空，返回构建D的右子树F，F的左子树是空右子树是空返回，此时该二叉树就已经构建出来了。
    此时在进行中序遍历输出这颗二叉树即可。

    4.1 创建

    #include 
#include 

typedef struct BinaryTreeNode 
{
    char val;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

BTNode* CreateBinaryTree(char* s, int* index)
{
	//这里很容易错
	//如果为空要先把下标++，跳过当前的#字符，在返回空
    if(s[*index] == '#')
    {
        ++(*index);
        return NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    //先构建根
    root->val = s[(*index)++];
    //递归构建它的左子树
    root->left = CreateBinaryTree(s, index);
    //递归构建它的右子树
    root->right = CreateBinaryTree(s, index);
    //返回时把左右子树链接到它的根
    return root;
}

//最后中序遍历输出
void inOrder(BTNode* root)
{
    if(!root)
    {
        return;
    }
    inOrder(root->left);
    printf("%c ", root->val);
    inOrder(root->right);
}
int main()
{
    char s[101] = {0};
    gets(s);
    //该函数的参数字符数组就必须的，还需要一个下标来遍历这个字符数组
    int index = 0;
    //为什么传地址？
    //因为要在函数中改变这个下标
    //传值是无法改变
    //并且在递归中同一层的下标相等就错了
    BTNode* root = CreateBinaryTree(s, &index);
    inOrder(root);
    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

    4.2 销毁

    二叉树的销毁还是比较简单的，遍历释放即可，那么采用哪种遍历顺序呢？
    如果是先序释放，直接先把根给释放了，它的左右子树就没法进行遍历，所以先序不能。
    中序呢？先释放左子树，然后释放根，同样的，它的右子树就找不到了，所以中序也不能。
    因此只能才有后续遍历来销毁二叉树。

    //销毁树
void TreeDestroy(BTNode* root)
{
	if (!root)
	{
		return;
	}
	TreeDestroy(root->left);
	TreeDestroy(root->right);
	free(root);
}

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

    总结

    二叉树的概念以及基础操作到此就结束了，二叉树的递归操作都是基于这几种遍历的变形，所以遍历二叉树要十分熟练，以及要想清楚层层递归的大概逻辑。

    相较于前面的链表啥的难多了感觉。

  • 相关阅读:
    hive高级函数
    OSPF —— 多区域部署 + ABR + ASBR + 路由重分发
    【英语：语法基础】B1.核心语法-名词与代词
    Linux | 可重入函数 | volatile | SIGCHLD信号
    Linux免密登录——A登录B密钥设置(SSH SCP)
    shell实例第24讲：zookeeper启动、停止、查看状态脚本
    web前端期末大作业【 大学生抗疫感动专题网页设计】HTML+CSS
    JVM垃圾回收算法
    GBase 8a性能优化之资源管理
    护士人文修养测试题答案
  • 原文地址：https://blog.csdn.net/weixin_66672501/article/details/126681991