链式二叉树及二叉树各种接口的实现(C)
二叉树的性质
- 若规定根节点的层数为1，则一棵非空二叉树的第 i i i层上最多有 2 i − 1 2^{i-1} 2i−1个结点.
- 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2 h − 1 2^{h}-1 2h−1
- 对任何一棵二叉树，如果度为0其叶结点个数为 n 0 n_{0} n0， 度为2的分支结点个数为 n 2 n_{2} n2，则有 n 0 = n 2 + 1 n_{0}=n_{2}+1 n0=n2+1
- 若规定根节点的层数为1，具有n个结点的满二叉树的深度， h = log 2 ( n + 1 ) h=\log_{2}(n+1) h=log2(n+1)
- 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为
i
i
i的结点有：
- 若 i > 0 i> 0 i>0， i i i位置节点的双亲序号： ( i − 1 ) / 2 (i-1)/2 (i−1)/2； i = 0 i=0 i=0， i i i为根节点编号，无双亲节点
- 若 2 i + 1 < n 2i+1<n 2i+1<n，左孩子序号： 2 i + 1 2i+1 2i+1， 2 i + 1 ≥ n 2i+1\ge n 2i+1≥n否则无左孩子
- 若
2
i
+
2
<
n
2i+2<n
2i+2<n，右孩子序号：
2
i
+
2
2i+2
2i+2，
2
i
+
2
≥
n
2i+2\ge n
2i+2≥n否则无右孩子
![![[Pasted image 20240927172102.png]]](https://i-blog.csdnimg.cn/direct/d8de3978c28946d9a1fc7c5396deadac.png)
链式结构的实现
![![[Pasted image 20240927174228.png]]](https://i-blog.csdnimg.cn/direct/f0cdcc33a1994b9e9ad18e84112be55d.png)
每棵树都可以分解成根节点，根节点的左子树，根节点的右子树
这样可以从根节点开始一直往下拆解，直到这棵树的左右两个子树都是空树停止
二叉树的遍历
- 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中。
- 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
![![[Pasted image 20240927175114.png]]](https://i-blog.csdnimg.cn/direct/c39bfcec838a454498f311236b4e5f2d.png)
- 前序
要求把树拆成根节点，左子树，右子树
遍历顺序：
1，{2，（3，N，N），（N）}，{4，（5，N，N），（6，N，N）} - 中序
左子树，根，右子树
遍历顺序：
{（N，3，N），2，（N）}，1，{（N，5，N），4，（N，6，N）}
遍历顺序 - 后序
左子树，右子树，根
遍历顺序：
{（N，N，3），（N），2}，{（N，N，5），（N，N，6），4}，1 - 层序
一层一层走
1，2，4，3，5，6
普通的链式二叉树没有意义
二叉树树的实现
链式树的定义
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
int val;
}BTNode;
- 有左右两个子树节点
- 还有val表示节点存的值
创建节点
BTNode* BuyNode(int x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node = NULL)
{
perror("malloc fail");
exit(-1);
}
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}
- malloc一个树节点的内存空间大小
- 判断空间是否创建成功
- 将节点的值置为x，左子树和右子树的指针置为空
二叉树的递归结构
递归调用展开图
![![[Pasted image 20240929160449.png]]](https://i-blog.csdnimg.cn/direct/8e3f16eda26a4aa9b3df93aab20cdad3.png)
先序中序后序遍历实现
void PrevOrder(BTNOde* root)
{
if (root == NULL)
return;
printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}
void InOrder(BTNOde* root)
{
if (root == NULL)
return;
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
void PostOrder(BTNOde* root)
{
if (root == NULL)
return;
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
- 通过递归实现遍历二叉树
- 先实现返回条件，当目前子树的根节点是空时，返回
- 这里是双路递推，先是递推左子树，再递推右子树，前中后遍历分别在两次递推的前中后访问根节点的值
节点个数
- 局部静态变量
int TreeSize(BTNode* root)
{
static int size = 0;
if (root == NULL)
return 0;
else
++size;
TreeSize(root->left);
TreeSize(root->right);
return size;
}
静态变量和全局变量存在于静态区，所以各个位置的size指同一个size，因为都是从静态区去取的，不是栈帧里面都有的
不会每次都走初始化，局部的静态成员变量只会执行一次
但是当多次调用这个函数时，size会累加，不符合预期。每次调用都要初始化为0
目前生命周期是全局的，作用域是局部的
这是不对的，这样的treesize是一次性的。
2. 手动初始化
int size = 0;
int TreeSize(BTNode* root)
{
if (root == NULL)
return 0;
else
++size;
TreeSize(root->left);
TreeSize(root->right);
return size;
}
在全局初始化size为0，之后调用的时候手动将size置为0
会发生限制安全问题
3. 变为递归子问题
遇到根节点，想求这棵树的节点个数，返回它的两棵子树的节点个数，接着找子树的子树，一直递归直到子树为空
树的节点的个数等于左子树节点的个数加右子树节点的个数再加自己
int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
![![[Pasted image 20241001113806.png]]](https://i-blog.csdnimg.cn/direct/923b030f7d7540f8954063e24fe77448.png)
叶子节点个数
节点是空，返回0
节点是叶子节点，返回1
都不是，返回左子树和右子树
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
![![[Pasted image 20241001130133.png]]](https://i-blog.csdnimg.cn/direct/55a90366ccab4f8287977856a21bc851.png)
第k层的节点个数
当前树的第k层=左子树的第k-1层+右子树的第k-1层
一直到某一节点的第一层
如果为空，返回0；不为空，返回1
int TreeKLevel(BTNode* root, int level)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 1)
{
return 1;
}
return TreeKLever(root->left, k-1)
+ TreeKLever(root->right, k-1);
}
![![[Pasted image 20241001140506.png]]](https://i-blog.csdnimg.cn/direct/ef1db95146df4a8492713e5d26920e98.png)
销毁
遇到一个根节点，先销毁左子树，再销毁右子树，回来再销毁自己
void TreeDestroy(BTNode* root)
{
if (root == NULL)
{
return;
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
不需要置空，形参的改变不影响实参
查找
如果节点为空，返回空
如果节点的值等于x，返回节点
左子树找到就不用到右子树找了
//二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, int x)
{
if (root == NULL)
return NULL;
if (root->val == x)
return root;
return TreeFind(root->left, x)
|| TreeFind(root->right, x);
}
这样返回的不是节点的指针，返回的是x在不在，是空指针或1的结果
如果这个函数返回的是bool值，只判断真和假
BTNode* TreeFind(BTNode* root, int x)
{
if (root == NULL)
return NULL;
if (root->val == x)
return root;
BTNode* ret = NULL;
ret = TreeFind(root->left, x);
if (ret)
return ret;
ret = TreeFind(root->right, x);
if (ret)
return ret;
return NULL;
}
如果左边找到了，就return一下
如果没找到，就去右边找，找到了就return
如果右边也没找到，就返回空
-
若x=3
![![[Pasted image 20241001185739.png]]](https://i-blog.csdnimg.cn/direct/2d1c991c147c44aeab47be98939affac.png)
-
若x=4
![![[Pasted image 20241001191416.png]]](https://i-blog.csdnimg.cn/direct/902a9131384f4d8e83bcc1f40ca8504a.png)
类似写法
BTNode* TreeFind(BTNode* root, int x)
{
if (root == NULL)
return NULL;
if (root->val == x)
return root;
BTNode* ret = NULL;
ret = TreeFind(root->left, x);
if (ret)
return ret;
return TreeFind(root->right, x);
}
层序遍历
先进先出
根节点入队列，出队列的时候将它的两个左子节点和右子节点插入队列
上一层带下一层
因为要存的是树的指针，所以队列的数据类型要改为BTNode*
.h文件不会被编译，而会在.c文件里面展开，所以要包含队列的.h文件，include语句要在树的结构体的下面，这样.h文件可以找见树的定义
void LevelOrder(BTNode* root)
{
Que q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
printf("%d ", front->val);
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
}
判断完全二叉树
完全二叉树走层序遍历的特征
完全二叉树在满二叉树的基础上，前n-1层都是满的，最后一层不满
但是最后一层，从左到右是连续的
如果这棵树是完全二叉树，这棵树层序遍历都是连续的
即层序：非空节点是连续的就是完全二叉树；非空节点是不连续，中间有空节点，就是非完全二叉树
要判断是否连续，层序遍历的时候，把NULL也入进去
非完全二叉树，出现空了以后，一定还有非空在队列里面
int TreeComplete(BTNode* root)
{
Que q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
if (front == NULL)
break;
QueuePush(&q, front->left);
QueuePush(&q, front->right);
QueuePop(&q);
}
//已经遇到空节点，如果队列中后面还有非空，就不是完全二叉树
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
- pop了以后还可以访问front节点，pop删除的是队列的节点，不会影响树的节点
- 队列里有指针指向树的节点
- 取front，相当于用一个front指针指向队头的节点
- 队列为空才能结束，不是到那个节点结束
返回树的高度
对于根节点而言，如果求出了左子树的高度和右子树的高度
树的高度等于左子树和右子树高的那一个加1
空树的时候，高度取0
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}
这样写运算消耗很大，会重复计算，每棵树都是这样
所以要把每次计算出来的值保存下来
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
int leftHeight = TreeHeight(root->left);
int rightHeight = TreeHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1: rightHeight + 1;
}
将比较大小封装成一个函数
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
return fmax(TreeHeight(root->left), TreeHeight(root-<right)) + 1;
}
没有重复计算
深度优先广度优先
深度优先遍历：前序遍历，递归
广度优先遍历：层序遍历，队列配合
声明定义分离实现
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
int val;
}BTNode;
BTNode* BuyNode(int x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node = NULL)
{
perror("malloc fail");
exit(-1);
}
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}
void PrevOrder(BTNOde* root)
{
if (root == NULL)
return;
printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}
void InOrder(BTNOde* root)
{
if (root == NULL)
return;
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
void PostOrder(BTNOde* root)
{
if (root == NULL)
return;
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
//节点个数
int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//叶子节点个数
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
//第k层节点个数
int TreeKLevel(BTNode* root, int level)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 1)
{
return 1;
}
return TreeKLever(root->left, k-1)
+ TreeKLever(root->right, k-1);
}
//二叉树销毁
void TreeDestroy(BTNode* root)
{
if (root == NULL)
{
return;
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
//二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, int x)
{
if (root == NULL)
return NULL;
if (root->val == x)
return root;
TreeFind(root->left, x);
TreeFind(root->right, x);
}
void LevelOrder(BTNode* root)
{
Que q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
printf("%d ", front->val);
if (front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
}
int TreeComplete(BTNode* root)
{
Que q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
if (front == NULL)
break;
QueuePush(&q, front->left);
QueuePush(&q, front->right);
QueuePop(&q);
}
//已经遇到空节点，如果队列中后面还有非空，就不是完全二叉树
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;
return fmax(TreeHeight(root->left), TreeHeight(root-<right)) + 1;
}
int main()
{
//手动构建二叉树
BTNode* node1 = BuyNode(1);
BTNode* node1 = BuyNode(2);
BTNode* node1 = BuyNode(3);
BTNode* node1 = BuyNode(4);
BTNode* node1 = BuyNode(5);
BTNode* node1 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
PrevOrder(node1);
printf("\n");
InOrder(node1);
printf("\n");
PostOrder(node1);
printf("\n");
return 0;
}