二叉树核心操作知识点整理

一、二叉树的创建

通过前序遍历序列构建二叉树，使用递归方式实现：

• 输入格式：以#表示空节点的前序序列（如 "ABD##E#H##CF##G##"）
• 实现逻辑：
  1. 遇到#则创建空节点，指针后移
  2. 否则创建当前节点，存储数据后指针后移
  3. 递归创建左子树和右子树

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi){
if (a == NULL || pi == NULL || *pi >= n) {return NULL;
}
if (a[*pi] == '#') {(*pi++);return NULL;
}
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->_data = a[*pi];
(*pi)++;
root->_left = BinaryTreeCreate(a, n, pi);
root->_right = BinaryTreeCreate(a, n, pi);
return root;
}

二、二叉树的销毁

采用后序遍历思想销毁二叉树（先销毁子树再销毁根节点）：

void BinaryTreeDestroy(BTNode** root) {if (root == NULL || *root == NULL) {return;BinaryTreeDestroy(&((*root)->_left));BinaryTreeDestroy(&((*root)->_right));free(*root);*root = NULL;
}

• 注意使用二级指针，确保销毁后根节点指针能被置空
• 递归销毁左子树→递归销毁右子树→释放当前节点→置空指针

三、节点统计相关操作

1. 总节点数计算

int BinaryTreeSize(BTNode* root){
return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);}

• 递归公式：1（当前节点）+ 左子树节点数 + 右子树节点数
• 空树返回 0

1. 叶子节点数计算

int BinaryTreeLeafSize(BTNode* root){
if (root == NULL) {return 0;
}
if (root->_left == NULL && root->_right == NULL) {return 1;
}
return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

• 叶子节点定义：左右子树均为空的节点
• 递归逻辑：若当前节点是叶子则返回 1，否则返回左右子树叶子数之和

1. 第 k 层节点数计算

int BinaryTreeLevelKSize(BTNode* root, int k){
if (root == NULL || k <= 0) {return 0;
}// 第1层只有根节点
if (k == 1) {return 1;
}// 第k层节点数 = 左子树第k-1层节点数 + 右子树第k-1层节点数
return BinaryTreeLevelKSize(root->_left, k - 1) +BinaryTreeLevelKSize(root->_right, k - 1);
}

• 递归逻辑：第 k 层节点数 = 左子树第 k-1 层节点数 + 右子树第 k-1 层节点数
• 边界条件：空树或 k≤0 返回 0；k=1 时返回 1（根节点所在层）

四、节点查找

BTNode* BinaryTreeFind(BTNode* root, BTDataType x){
if (root->_data == x) {return root;
}
if (root == NULL) {return NULL;
}
BTNode* leftResult = BinaryTreeFind(root->_left, x);
// 如果左子树中找到了，返回找到的节点
if (leftResult != NULL) {return leftResult;
}// 左子树没找到，再在右子树中查找
BTNode* rightResult = BinaryTreeFind(root->_right, x);
// 返回右子树的查找结果（找到或NULL）
return rightResult;}

• 查找逻辑：
  1. 先检查当前节点是否为目标节点
  2. 递归查找左子树，找到则返回
  3. 左子树未找到则递归查找右子树
  4. 均未找到返回 NULL

五、遍历操作

1. 前序遍历（根→左→右）

void BinaryTreePrevOrder(BTNode* root){
if (root == NULL) {printf("#");return;
}
else {printf("%c", root->_data);
} printf("%c", root->_data);
BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);}

• 操作：先访问根节点，再递归前序遍历左子树，最后递归前序遍历右子树
• 空节点输出#

1. 中序遍历（左→根→右）

void BinaryTreeInOrder(BTNode* root){if (root == NULL) {printf("#");return;}BinaryTreeInOrder(root->_left);printf("%c", root->_data);BinaryTreeInOrder(root->_right);
}

• 操作：先递归中序遍历左子树，再访问根节点，最后递归中序遍历右子树

1. 后序遍历（左→右→根）

void BinaryTreePostOrder(BTNode* root){if (root == NULL) {printf("#");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%c", root->_data);}
void QueueInit(Queue* q) {q->front = q->rear = NULL;
}

• 操作：先递归后序遍历左子树，再递归后序遍历右子树，最后访问根节点

1. 层序遍历（按层次从上到下、从左到右）

void BinaryTreeLevelOrder(BTNode* root){if (root == NULL) {return; }Queue q;QueueInit(&q);// 根节点入队QueuePush(&q, root);// 队列不为空则循环while (!QueueEmpty(&q)) {// 取出队头节点并访问BTNode* cur = QueueFront(&q);QueuePop(&q);printf("%c ", cur->_data);// 左孩子入队if (cur->_left != NULL) {QueuePush(&q, cur->_left);}// 右孩子入队if (cur->_right != NULL) {QueuePush(&q, cur->_right);}}// 销毁队列QueueDestroy(&q);}

• 实现方式：借助队列
  1. 根节点入队
  2. 队不为空时，出队一个节点并访问
  3. 将该节点的左右孩子依次入队
  4. 重复步骤 2-3 直至队空

六、队列辅助结构

层序遍历依赖队列实现，队列相关操作：

• 初始化：void QueueInit(Queue* q)
• 入队：void QueuePush(Queue* q, BTNode* x)
• 出队：void QueuePop(Queue* q)
• 获取队头：BTNode* QueueFront(Queue* q)
• 判空：int QueueEmpty(Queue* q)
• 销毁：void QueueDestroy(Queue* q)

七、补充说明

• 代码中定义的二叉树节点结构：

c

运行

typedef struct BinaryTreeNode {struct BinaryTreeNode* _left;  // 左孩子struct BinaryTreeNode* _right; // 右孩子BTDataType _data;              // 节点数据
} BTNode;

• 数据类型：采用char类型作为节点数据（BTDataType = char）
• 未实现的功能：int BinaryTreeComplete(BTNode* root)（判断是否为完全二叉树）