数据结构 | 二叉树的概念及前中后序遍历（一）:https://developer.aliyun.com/article/1426944
五、二叉树的性质
- 每个节点最多有两个子节点： 每个节点最多有两个子节点，左子节点和右子节点。
- 每个节点有零个、一个或两个子节点： 这意味着一个节点可以是叶节点（没有子节点）、有一个子节点，或者有两个子节点。
- 左子树和右子树是有序的： 对于二叉搜索树（BST），左子树中的每个节点的值都小于该节点的值，右子树中的每个节点的值都大于该节点的值。
- 树的高度： 树的高度是从根节点到最深叶节点的最长路径。一棵有n个节点的二叉树的高度最多为n，最少为log₂(n+1)。
- 最后一层节点集中在左侧： 在完全二叉树中，最后一层的节点从左到右排列，缺失的位置只会出现在最右边。
- 满二叉树： 一棵高度为h且有2^h - 1个节点的二叉树被称为满二叉树。
- 最后一层节点集中在左侧： 在完全二叉树中，最后一层的节点从左到右排列，缺失的位置只会出现在最右边。
- 满二叉树： 一棵高度为h且有2^h - 1个节点的二叉树被称为满二叉树。
六、二叉树的存储结构
6.1 顺序存储结构
- 在顺序存储结构中，使用数组来表示二叉树。具体的方式是按照从上到下、从左到右的顺序将二叉树的节点依次存储在数组中。如果一个节点的编号为i，则其左子节点的编号为2i，右子节点的编号为2i+1。
例如：
1 / \ 2 3 / \ / \ 4 5 6 7
- 对应的顺序存储结构为：
[1, 2, 3, 4, 5, 6, 7]
- 这里数组的索引从1开始，根节点对应索引1，而左子节点和右子节点的关系则按照 2i 和 2i+1 的规则排列。
6.2 链式存储结构
- 在链式存储结构中，每个节点通过指针或引用指向其左子节点和右子节点。这样的存储结构更加直观，也更容易实现。节点的定义如下：
struct TreeNode { int data; // 节点的数据 TreeNode* left; // 指向左子节点的指针 TreeNode* right; // 指向右子节点的指针 };
1 / \ 2 3 / \ / \ 4 5 6 7
每个节点的 left 和 right 指针分别指向其左子节点和右子节点。这种存储结构更直观，但相对于顺序存储结构，可能会占用更多的内存空间。
typedef int BTDataType; // 二叉链 struct BinaryTreeNode { struct BinTreeNode* _pLeft; // 指向当前节点左孩子 struct BinTreeNode* _pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 } // 三叉链 struct BinaryTreeNode { struct BinTreeNode* _pParent; // 指向当前节点的双亲 struct BinTreeNode* _pLeft; // 指向当前节点左孩子 struct BinTreeNode* _pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 }；
6.3 二叉树的顺序结构及实现
- 普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
七、二叉树链式结构的实现
- 在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
- 我们先回顾一下二叉树的概念：
- 空树
- 非空：根节点，根节点的左子树、根节点的右子树组成的。
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
八、二叉树的遍历【重点】
8.1 前序、中序以及后序遍历
- 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。简单来说就是访问顺序就是根 左子树 右子树
- 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。简单来说就是访问顺序就是 左子树 根 右子树
- 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。简单来说就是访问顺序就是 左子树 右子树 根
构建一棵树
BTNode* BuyTreeNode(int x) { BTNode*node = (BTNode*)malloc(sizeof(BTNode)); assert(node); node->data = x; node->left = NULL; node->right = NULL; return node; } BTNode* CreateTree() { BTNode* node1 = BuyTreeNode(1); BTNode* node2 = BuyTreeNode(2); BTNode* node3 = BuyTreeNode(3); BTNode* node4 = BuyTreeNode(4); BTNode* node5 = BuyTreeNode(5); BTNode* node6 = BuyTreeNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; }
二叉树的前序遍历
void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); }
二叉树中序遍历
void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } BinaryTreeInOrder(root->left); printf("%d ", root->data); BinaryTreeInOrder(root->right); }
二叉树后序遍历
void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } BinaryTreePostOrder(root->left); BinaryTreePostOrder(root->right); printf("%d ", root->data); }
测试
int main() { BTNode* root = CreateTree(); printf("二叉树前序遍历:\n"); BinaryTreePrevOrder(root); printf("\n"); printf("二叉树中序遍历:\n"); BinaryTreeInOrder(root); printf("\n"); printf("二叉树后序遍历:\n"); BinaryTreePostOrder(root); printf("\n"); return 0; } {
