数据结构---二叉树
一、树的相关术语
A
/ \
B C
/ \ \
D E F
-
节点（Node）
树的基本单位，包含数据及指向子节点的链接（指针）。 -
根节点（Root）
树的顶层节点，没有父节点（节点A）。 -
边（Edge）
连接两个节点的有向或无向连线，表示父子关系。 -
父节点（Parent）
若节点P直接指向节点C，则P是C的父节点（如A是B的父节点）。 -
子节点（Child）
被父节点直接指向的节点（如B和C是A的子节点）。 -
兄弟节点（Sibling）
同一父节点的子节点互为兄弟（如B和C）。 -
叶子节点（Leaf）
没有子节点的节点（如D、E、F）。 -
内部节点（Internal Node）
至少有一个子节点的非根节点（如B、C）。 -
子树（Subtree）
树中任意节点及其后代构成的子结构（如以B为根的子树包含B、D、E）。 -
森林（Forest）
由多棵互不相交的树组成的集合（删除根节点后，子树形成森林）。 -
度（Degree）
-
节点的度：子节点数量（如
A的度为 2，D的度为 0）。 -
树的度：树中节点的最大度（如二叉树的最大度为 2）。
-
-
二叉树（Binary Tree）
每个节点最多有 2 个子节点（左、右子节点）。 -
二叉搜索树（BST）
左子树所有节点值 ≤ 根节点值 ≤ 右子树所有节点值。 -
平衡树（Balanced Tree）
任意节点的左右子树高度差不超过 1（如 AVL 树）。 -
完全二叉树（Complete Binary Tree）
除最后一层外，其他层必须满，且最后一层节点靠左排列。 -
满二叉树（Full Binary Tree）
所有非叶子节点均有 2 个子节点，且所有叶子在同一层。
-
堂兄弟节点（Cousin）
父节点不同但祖父节点相同的节点（如D和F）。 -
节点的深度优先编号（DFN）
在 DFS 遍历中被访问的顺序编号。 -
最小公共祖先（LCA）
两个节点在树中的最低深度公共祖先（如B是D和E的 LCA）。
二、二叉树的性质
1. 基本性质
-
度数为 2 的节点：在二叉树中，每个节点的度数（子节点数）不超过 2（即 0、1 或 2）。
-
子树区分：即使某个节点只有一个子节点，也要区分它是左子树还是右子树。
2. 特殊类型的二叉树
-
满二叉树 (Full Binary Tree)
每一层的节点数都达到最大值，即所有非叶子节点都有 2 个子节点，且所有叶子节点在同一层。-
深度为 kk 的满二叉树，节点总数 =2k−1=2k−1。
-
-
完全二叉树 (Complete Binary Tree)
除最后一层外，其他层都是满的，且最后一层的节点尽可能靠左排列。-
适用于数组存储（堆结构）。
-
-
完美二叉树 (Perfect Binary Tree)
所有叶子节点都在同一层，且所有非叶子节点都有 2 个子节点（与满二叉树类似）。 -
平衡二叉树 (Balanced Binary Tree)
任意节点的左右子树高度差不超过 1（如 AVL 树、红黑树）。
3. 节点关系
-
第 ii 层的最大节点数：2i−12i−1（根节点为第 1 层）。
-
深度为 kk 的二叉树的最大节点数：2k−12k−1（即满二叉树）。
-
叶子节点数 n0n0 与度为 2 的节点数 n2n2 的关系：
n0=n2+1n0=n2+1（对任何非空二叉树成立）。 -
总节点数 nn 与边数的关系：
边数 =n−1=n−1（因为除根节点外，每个节点有且仅有一条入边）。
4. 存储结构
-
链式存储：通过节点结构（
data, left, right）动态分配内存。 -
顺序存储（数组）：适用于完全二叉树，节点按层序存储，索引关系：
-
父节点索引 ii（从 1 开始），则左子节点为 2i2i，右子节点为 2i+12i+1。
-
5. 遍历方式
-
深度优先遍历（DFS）：
-
前序遍历（根 → 左 → 右）
-
中序遍历（左 → 根 → 右）
-
后序遍历（左 → 右 → 根）
-
-
广度优先遍历（BFS）：按层遍历（使用队列实现）。
6. 应用场景
-
二叉搜索树（BST）：支持高效查找、插入、删除（平均 O(logn)O(logn)）。
-
堆（完全二叉树）：实现优先队列。
-
Huffman 树：用于数据压缩。
-
表达式树：表示数学表达式。
三、二叉树的基本功能实现
以该数为例
1
/ \
2 4
/ / \
3 5 6
\
6
1、头文件及二叉树的创建
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTDatatype;
typedef struct BinaryTreeNode
{
BTDatatype data;
struct BInaryTreeNode* left;
struct BInaryTreeNode* right;
}BTNode;
2、创建节点
BTNode* BuyNode(int x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
//创建节点
BTNode* CreatNode()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
BTNode* node7 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
node3->right = node7;
return node1;
}
3、遍历(递归实现)
①先序遍历
void InOrder(BTNode* root) {
if (root == NULL) {
printf("N ");
return;
}
InOrder(root->left); // 1. 遍历左子树
printf("%d ", root->data); // 2. 访问根
InOrder(root->right); // 3. 遍历右子树
}
执行过程：
访问根节点 1。
递归遍历左子树（根为 2）：
访问 2，遍历左子树（3）。
访问 3，左子树为空（打印 N），右子树为 6。
访问 6，左右子树均为空（打印 N N）。
递归遍历右子树（根为 4）：
访问 4，左子树为 5（访问后打印 N N），右子树为 6（访问后打印 N N）。
输出结果
1 2 3 N 6 N N N 4 5 N N 6 N N
②中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
思路与前序类似
输出结果
N 3 N 6 N 2 N 1 N 5 N 4 N 6 N
③后序遍历
void OutOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
OutOrder(root->left);
OutOrder(root->right);
printf("%d ", root->data);
}
结果
N N N 6 3 N 2 N N 5 N N 6 4 1
4、树的节点数
int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left)
+ TreeSize(root->root) + 1;
}
思路：将问题拆分为左子树节点个数+右子树节点个数+当前根节点
5、树的叶子节点个数
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);
}
思路：叶子节点就是左右子树都为空的节点，统计左右子树都为空的节点就行了
6、树的深度
int TreeHeight(BTNode* root)
{
if(root == NULL)
return 0;
//将较深的保存下来，逐层递归，左子树的深度和右子树的深度
int leftheight = TreeHight(root->left);
int rightheight = TreeHight(root->right);
//返回较大的
return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}
思路：空树深度为零，非空深度=左子树和右子树中深度较大的+1(当前节点贡献1层)
7、第k层节点数
int TreeKSize(BTNode* root, int k)
{
if(root == NULL)
return 0;
if(k == 1)
return 1;
return TreeKSize(root->left, k - 1) + TreeKSize(root->right, k - 1);
}
思路：k-1递归，当k = 1时，先进入左节点，如果左边不是空节点返回一，然后再看右边，最后加起来返回就行了
1 // Level 1
/ \
2 3 // Level 2
/ \ \
4 5 6 // Level 3
8、查找值为x的节点
BTNode* BTFind(BTNode* root)
{
if(root == NULL)
return NULL;
if(root->data == x)
return root;
//left和right只有两种值，一种是空，一种就是找到的与x值相等的节点
BTNode* left = BTFind(root->left);//保存下来，不然返回就会忘记，浪费时间
if(left)//只要不是空就是值为x的节点，一路返回就可以
return left;
BTNode* right = BTFind(root->right);
if(right)
return left;
}
9、层序遍历
队列
typedef struct BinaryTreeNode* QueueDatatype;
typedef struct QueueNode
{
QueueDatatype data;
struct QueueNode* next;
}QN;
typedef struct Queue
{
QN* phead;
QN* ptail;
}Queue;
void TreeLevelOrder(BTNode* root)
{
queue q;
QInit(&q);
if(root)
QPush(&q, root);//树不为空就让根节点入队
while(!QEmpty(&q))
{
BTNode* front = QFront(&q);//保存队头
Qpop(&q);//队头出队
printf("%d ,front->data);
//出一个就把它的非空左右节点带入队
if(front->left)
QPush(&q, front->left);
if(front->right);
QPush(&q, front->right);
}
QDestroy(&q);
}
步骤
-
创建一个空队列，并将根节点入队。
-
循环执行以下步骤直到队列为空：
-
出队一个节点，并访问该节点（如打印节点值）。
-
如果该节点有左子节点，将左子节点入队。
-
如果该节点有右子节点，将右子节点入队。
-
-
遍历结束。
10、判断是否为完全二叉树
思路：层序遍历，将二叉树中的节点连空一起推入队列，当推入第一个NULL节点时停止，开始判断,如果队列中还有非空节点，那他就不是完全二叉树
bool TreeComplete(BTNode* root)
{
queue q;
QInit(&q);
if(root)
QPush(&q,root);
while(!QEmpty(q))
{
BTNode* front = QFront(&q);
QPop(&q);
if(front == NULL)
break;
//无需判空，空也入队
QPush(&q, root->left);
QPush(&q, root->right);
}
//判断
while(!QEmpty(&q))
{
BTNode* front = QFront(&q);
QPop(&q);
if(front)
{
QDestroy(&q);
return false);
}
}
QDestroy(&q);
return true;
}
11、销毁
思路：递归到最下边的节点，释放掉然后返回，依次释放，二叉树的销毁就完成了
void TreeDestroy(BTNode* root)
{
if(root == NULL);
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
13
0- 0
已为社区贡献1条内容
所有评论(0)