【【异世界历险之数据结构世界（二叉树)】】
前言
介绍
二叉树的三种遍历：
- 前序遍历 Preorder Traversal
访问顺序： 根节点 → 左子树 → 右子树
✅ 根在最前- 中序遍历 Inorder Traversal
访问顺序： 左子树 → 根节点 → 右子树
✅ 根在中间- 后序遍历 Postorder Traversal
访问顺序： 左子树 → 右子树 → 根节点
✅ 根在最后假设二叉树结构如下：
A/ \B C/ \ \
D E F
🌼 前序遍历（Preorder）
顺序：A B D E C F
🌸 中序遍历（Inorder）
顺序：D B E A C F
🌷 后序遍历（Postorder）
顺序：D E B F C A
实现
前提
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;构建树
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->val = x;newnode->left = NULL;newnode->right = NULL;return newnode;}BTNode* CreateTree()
{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(7);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->left = node6;node3->right = node7;return node1;}
解析：
✅ BuyNode 函数解析：
作用：创建一个新的二叉树节点，值为 x。
✅ CreateTree 函数解析：
作用：构建一棵固定结构的完全二叉树，节点值为 1~7。
构建逻辑如下：
1/ \2 3/ \ / \
4 5 6 7
最终返回根节点 node1，可用于后续遍历或操作。
一、前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);
}
解析：
前序遍历顺序： 根节点 → 左子树→ 右子树
PreOrder(root) 展开步骤（根 → 左 → 右）如下：
第一次调用：PreOrder(1)
打印：1
调用左子树：PreOrder(2)
第二次调用：PreOrder(2)
打印：2
调用左子树：PreOrder(4)
第三次调用：PreOrder(4)
打印：4
调用左子树：PreOrder(NULL) → 打印：NULL
调用右子树：PreOrder(NULL) → 打印：NULL
（回到上一层）
回到：PreOrder(2)，接着调用右子树：PreOrder(5)
第四次调用：PreOrder(5)
打印：5
左：PreOrder(NULL) → 打印：NULL
右：PreOrder(NULL) → 打印：NULL
（回到上一层）
回到：PreOrder(1)，接着调用右子树：PreOrder(3)
第五次调用：PreOrder(3)
打印：3
调用左子树：PreOrder(6)
第六次调用：PreOrder(6)
打印：6
左：PreOrder(NULL) → 打印：NULL
右：PreOrder(NULL) → 打印：NULL
回到：PreOrder(3)，接着调用右子树：PreOrder(7)
第七次调用：PreOrder(7)
打印：7
左：PreOrder(NULL) → 打印：NULL
右：PreOrder(NULL) → 打印：NULL
二、中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}
解析：
中序遍历顺序：
左子树 → 根节点 → 右子树
三、后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("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;
}
解析：
➤ TreeSize(1)
= TreeSize(2) + TreeSize(3) + 1
➤ TreeSize(2)
= TreeSize(4) + TreeSize(5) + 1
TreeSize(4) → 左空 + 右空 + 1 = 0 + 0 + 1 = 1
TreeSize(5) → 左空 + 右空 + 1 = 0 + 0 + 1 = 1
→ 所以 TreeSize(2) = 1 + 1 + 1 = 3
➤ TreeSize(3)
= TreeSize(6) + TreeSize(7) + 1
TreeSize(6) → 左空 + 右空 + 1 = 0 + 0 + 1 = 1
TreeSize(7) → 左空 + 右空 + 1 = 0 + 0 + 1 = 1
→ 所以 TreeSize(3) = 1 + 1 + 1 = 3
🔚 回到 TreeSize(1)
= 左(3) + 右(3) + 1 = 7
五、树的高度
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);
}解析：
TreeHeight(1)
= max(TreeHeight(2), TreeHeight(3)) + 1
TreeHeight(2)
= max(TreeHeight(4), TreeHeight(5)) + 1
→ TreeHeight(4) = 1（左右都是 NULL）
→ TreeHeight(5) = 1
→ TreeHeight(2) = max(1, 1) + 1 = 2
TreeHeight(3)
= max(TreeHeight(6), TreeHeight(7)) + 1
→ TreeHeight(6) = 1
→ TreeHeight(7) = 1
→ TreeHeight(3) = max(1, 1) + 1 = 2
最终：
TreeHeight(1) = max(2, 2) + 1 = 3
六、树的第k层节点数
int TreeLevel(BTNode* root,int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}int leftLevel = TreeLevel(root->left, k - 1);int rightLevel = TreeLevel(root->right, k - 1);return leftLevel + rightLevel;
}
解析：以k=3为例子
TreeLevel(1, 3)
= TreeLevel(2, 2) + TreeLevel(3, 2)
TreeLevel(2, 2)
= TreeLevel(4,1) + TreeLevel(5,1)
→ 都是第 3 层节点，返回 1 + 1 = 2
TreeLevel(3, 2)
= TreeLevel(6,1) + TreeLevel(7,1)
→ 返回 1 + 1 = 2
最终：
TreeLevel(1,3) = 2 + 2 = 4
七、查找值为x的节点地址
BTNode* TreeFind(BTNode* root,BTDataType x)
{if (root == NULL){return NULL;}BTNode* left = TreeFind(root->left, x);if (left)return left;BTNode* right = TreeFind(root->right, x);if (right)return right;return NULL;
}
解析：
TreeFind(1, 6)
→ root->val != 6，查左子树
TreeFind(2, 6)
→ root->val != 6，查左子树
TreeFind(4, 6)
→ 不等，左右 NULL，返回 NULL
回到 TreeFind(2)，查右子树
TreeFind(5, 6)
→ 不等，左右 NULL，返回 NULL
回到 TreeFind(1)，查右子树
TreeFind(3, 6)
→ root->val != 6，查左子树
TreeFind(6, 6)
→ 匹配成功！返回该节点指针
最终一路上传返回到 TreeFind(1)
结果展示·：
总结
断更许久，抱歉各位。
堆与二叉树（复习）