二叉树
特点：每个结点最多有两颗子树，并且子树有左右之分。把一个结点拥有的子树的数量称为结点 的度，度为0的结点称为叶子结点，度不为0称为分支结点，树的最大层数称为树的深度
性质：
1.非空二叉树中的叶子结点数量等于双分支结点数量 +1
2.二叉树的第 i 层上最多有 2^(i-1) (i >= 1) 个结点
3.高度为h的二叉树最多有 2^h -1 (h >= 1) 个结点
二叉树的相关代码
/*****************************************************************************
* 函数名称: BinaryTree_CountLeafNode
* 函数功能： 计算一颗二叉树的所有叶子节点的数量
* 函数参数：
* @root 操作的树
* 返回结果： 叶子节点的数量
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/5/6
* 修改历史： 2024/5
* 函数版本： 1.0
*
*
*****************************************************************************/
/*****************************************************************************
代码解析：二叉树有可能存在的三种状态————空树，只有一个根节点，有左右子树。通过递归实现叶子节点的数量计算。只有一个根结点就是回归条件
*****************************************************************************/
//计算一颗二叉树的所有叶子节点的数量,可以采用递归实现
int BinaryTree_CountLeafNode(Tnode_t *root)
{
int n1,n2; //n1记录左子树叶子节点,n2记录右子树叶子结点
//1.递归函数必须提前写好终止条件
if (NULL == root)
{
//说明是空树，则直接返回0
return 0;
}
else if(root->lchild == NULL && root->rchild == NULL)
{
//说明只有一个根节点，则根节点就是叶子节点
return 1;
}
else
{
//说明是有子树的二叉树，则需要计算左子树的叶子节点和右子树的叶子节点
n1 = BinaryTree_CountLeafNode(root->lchild); //先计算左子树
n2 = BinaryTree_CountLeafNode(root->rchild); //再计算右子树
}
return n1+n2;
}
/*****************************************************************************
* 函数名称: BinaryTree_CountNode
* 函数功能： 计算二叉树的结点的数量
* 函数参数：
* @root 操作的树
* 返回结果： 结点的数量
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/5/6
* 修改历史： 2024/5
* 函数版本： 1.0
*
*****************************************************************************/
/*****************************************************************************
代码解析：二叉树有可能存在的状态————空树以及只有一个根结点。通过递归实现，空树为回归条件
*****************************************************************************/
//计算一颗二叉树的所有节点的数量,可以采用递归实现
int BinaryTree_CountNode(Tnode_t *root)
{
int n1,n2; //n1用于记录左子树的节点，n2用于记录右子树的节点
//递归函数先提前写好终止条件
if (NULL == root)
{
return 0;
}
//假设采用后序遍历来计算二叉树的节点数量
n1 = BinaryTree_CountNode(root->lchild);
n2 = BinaryTree_CountNode(root->rchild);
return n1+n2+1;
}
/*****************************************************************************
* 函数名称: BinaryTree_GetDepth
* 函数功能： 计算二叉树的深度
* 函数参数：
* @root 操作的树
* 返回结果： 二叉树的深度
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/5/6
* 修改历史： 2024/5
* 函数版本： 1.0
*
*****************************************************************************/
/*****************************************************************************
代码解析：二叉树有可能存在的状态————空树以及只有一个根结点。通过递归实现，空树为回归条件
(n1>n2)?n1:n2 判断结点的左右子树的深度大小 +1 加上根节点
*****************************************************************************/
//计算一颗二叉树的深度,可以采用递归实现
int BinaryTree_GetDepth(Tnode_t *root)
{
int n1,n2;//n1记录左子树的深度,n2记录右子树的深度
//1.递归函数必须提前写好终止条件
if (NULL == root)
{
//说明是空树，则返回0
return 0;
}
else
{
//说明是子树的二叉树，则分别计算左子树和右子树，取最大
n1 = BinaryTree_GetDepth(root->lchild);
n2 = BinaryTree_GetDepth(root->rchild);
}
return ( (n1>n2)?n1:n2 ) + 1;
}
二叉查找树（BST）
特点
- 如果二叉查找树有左子树，则左子树的结点的键值key要小于左子树的根结点的键值key
- 如果二叉查找树有右子树，则右子树的结点的键值key要大于右子树的根结点的键值key
- 对于二叉查找树而言，左子树和右子树也分别是二叉查找树
- 二叉查找树的结点的键值是不重复
二叉树的遍历（基本上是采用BST树）
前序遍历
/*****************************************************************************
* 函数名称: BSTree_PreOrder
* 函数功能： 前序遍历二叉树
* 函数参数：
* @Root 操作的树
* 返回结果： 布尔型
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/5/6
* 修改历史： 2024/5
* 函数版本： 1.0
*
*****************************************************************************/
//前序遍历 根左右 体现“递归”思想
bool BSTree_PreOrder(BSTnode_t *Root)
{
//使用递归函数，必须提前写好终止条件
if (NULL == Root)
{
return false;
}
//先输出根节点的键值
printf("keyval = %d\n",Root->data);
//再输出根节点的左子树
BSTree_PreOrder(Root->lchild);
//再输出根节点的右子树
BSTree_PreOrder(Root->rchild);
return true;
}
中序遍历
/*****************************************************************************
* 函数名称: BSTree_InOrder
* 函数功能： 中序序遍历二叉树
* 函数参数：
* @Root 操作的树
* 返回结果： 布尔型
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/5/6
* 修改历史： 2024/5
* 函数版本： 1.0
*
*****************************************************************************/
//中序遍历 左根右
bool BSTree_InOrder(BSTnode_t *Root)
{
//使用递归函数，必须提前写好终止条件
if (NULL == Root)
{
return false;
}
//先输出根节点的左子树
BSTree_PreOrder(Root->lchild);
//再输出根节点的键值
printf("keyval = %d\n",Root->data);
//再输出根节点的右子树
BSTree_PreOrder(Root->rchild);
}
后序遍历
/*****************************************************************************
* 函数名称: BSTree_PostOrder
* 函数功能： 后序遍历二叉树
* 函数参数：
* @Root 操作的树
* 返回结果： 布尔型
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/5/6
* 修改历史： 2024/5
* 函数版本： 1.0
*
*****************************************************************************/
//后序遍历 左右根
bool BSTree_PostOrder(BSTnode_t *Root)
{
//使用递归函数，必须提前写好终止条件
if (NULL == Root)
{
return false;
}
//先输出根节点的左子树
BSTree_PreOrder(Root->lchild);
//再输出根节点的右子树
BSTree_PreOrder(Root->rchild);
//再输出根节点的键值
printf("keyval = %d\n",Root->data);
}
BST树的插入
/*****************************************************************************
* 函数名称: BSTree_InsertNode
* 函数功能： 向BST树插入结点
* 函数参数：
* @Root 操作的树
* 返回结果： 布尔型
* 注意事项： NONE
* 函数作者： [email protected]
* 创建日期： 2024/5/6
* 修改历史： 2024/5
* 函数版本： 1.0
*
*****************************************************************************/
/*****************************************************************************
代码解析：
1）为什么是 **Root 而不是 *Root
需要改变地址里的值而不是直接改变值，因为Root是形式参数
2）(*Root)->data
->优先级比较高
3）为什么是 &(*Root)->lchild
需要取到lchild的地址
*****************************************************************************/
//向BST树中加入节点 规则：根节点的左子树的键值都是比根节点小的，根节点的右子树的键值都是比根节点大的
bool BSTree_InsertNode(BSTnode_t **Root,DataType_t KeyVal)
{
//1.创建新节点并对新结点进行初始化
BSTnode_t * New = BSTree_NewNode(KeyVal);
if (NULL == New)
{
printf("Create NewNode Error\n");
return false;
}
//2.此时分析当前的BST树是否为空树，有2种情况（空树 or 非空树）
if (NULL == *Root)
{
//此时BST树为空树，则直接把新节点作为BST树的根节点
*Root = New;
return true;
}
//3.判断KeyVal是否与Root的值相等
if ((*Root)->data == KeyVal)
{
printf("insett fail\n");
return false;
}
//4.开始递归
else if ((*Root)->data > KeyVal){
BSTree_InsertNode(&(*Root)->lchild,KeyVal);
}
else{
BSTree_InsertNode(&(*Root)->rchild,KeyVal);
}
return true;
}