二叉树链式结构的实现
在学习二叉树的基本操作前，需要先搭建一棵二叉树，才能学习其相关的基本操作。为了降低大家学习成本，此处我们暴力建立一棵简单的二叉树，快速进入二叉树操作学习。等后面我们在研究二叉树真正的创建方式。
BTNode* CreateBinaryTree() { // 创建根节点1 BTNode* root = (BTNode*)malloc(sizeof(BTNode)); root->data = 1; // 创建左子树2 BTNode* node2 = (BTNode*)malloc(sizeof(BTNode)); node2->data = 2; root->left = node2; // 创建右子树4 BTNode* node4 = (BTNode*)malloc(sizeof(BTNode)); node4->data = 4; root->right = node4; // 创建2的左子节点3 BTNode* node3 = (BTNode*)malloc(sizeof(BTNode)); node3->data = 3; node2->left = node3; node2->right = NULL; // 创建2的右子节点5 BTNode* node5 = (BTNode*)malloc(sizeof(BTNode)); node5->data = 5; node4->left = NULL; node4->right = node5; node5->left = NULL; node5->right = NULL; node3->left = NULL; node3->right = NULL; return root; // 返回根节点 }
该二叉树是这样子的.
二叉树的遍历方式
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
- 关于二叉树的遍历方式，要知道二叉树遍历的基本方式都有哪些。
我这里把二叉树的几种遍历方式列出来，大家就可以一一串起来了。
- 二叉树主要有两种遍历方式
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 广度优先遍历：一层一层的去遍历。
- 深度优先遍历
前序遍历（递归法，迭代法）
中序遍历（递归法，迭代法）
后序遍历（递归法，迭代法）
递归法:
1.前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2.中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3.后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
- 广度优先遍历
层次遍历（迭代法）
层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层
上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
- 在深度优先遍历中：有三个遍历顺序，前中后序遍历， 有的朋友在这里总分不清这三个顺
序，经常搞混，我这里教大家一个技巧。
这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式
- 前序遍历：中左右
- 中序遍历：左中右
- 后序遍历：左右中
大家可以对着如下图，看看自己理解的前后中序有没有问题。
- 而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决
定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。
二叉树的基本操作
- 其实这些都是二叉树基本的操作，如有不懂画上递归展开图和代码调式即可一目了然.
二叉树前序遍历
- 二叉树前序遍历是一种深度优先遍历算法，也叫先序遍历。具体过程如下：
1 . 访问根节点。
2 . 遍历左子树。
3 . 遍历右子树。
void PrevOrder(BTNode* root) // 二叉树先序遍历，接收一个二叉树根节点指针 { if (root == NULL) // 终止条件：如果当前节点为空，则输出"N"，并返回上一层递归 { printf("N "); return; } printf("%d ", root->data); // 输出当前节点的值 PrevOrder(root->left); // 递归遍历左子树 PrevOrder(root->right); // 递归遍历右子树 }
二叉树中序遍历
- 中序遍历跟前序差不多，只是访问顺序变了
1 . 遍历左子树。
2 . 访问根节点。
3 . 遍历右子树。
void InOrder(BTNode* root) // 二叉树中序遍历，接收一个二叉树根节点指针 { if (root == NULL) //终止条件: 如果当前节点为空，则输出"N"，并返回上一层递归 { printf("N "); return; } InOrder(root->left); //递归遍历左子树 printf("%d ", root->data); //输出当前节点的值 InOrder(root->right); //递归遍历右子树 }
二叉树后序遍历
1 . 遍历左子树。 2 . 遍历右子树。 3 . 访问根节点。
void PostOrder(BTNode* root) // 二叉树后序遍历，接收一个二叉树根节点指针 { if (root == NULL) // 终止条件：如果当前节点为空，则输出"N"，并返回上一层递归 { printf("N "); return; } PostOrder(root->left); // 递归遍历左子树 PostOrder(root->right); // 递归遍历右子树 printf("%d ", root->data); // 输出当前节点的值 }
二叉树节点个数
- 采用后续遍历，先访问他的左右子树然后回到跟节点+1返回，这样就可以把字点个数返
回.
如果当前节点为空（即二叉树为空），返回0。
递归计算左子树的节点数量，并赋值给leftSize。
递归计算右子树的节点数量，并赋值给rightSize。
返回左子树和右子树节点数量之和再加1（1表示根节点）。
int TreeSize(BTNode* root) { // 如果二叉树为空，返回0 if (root == NULL) { return 0; } // 递归计算左子树和右子树的节点数量 int leftSize = TreeSize(root->left); int rightSize = TreeSize(root->right); // 返回左子树节点数量、右子树节点数量和根节点数量之和 再加1 return leftSize + rightSize + 1; }
叶子节点的个数
- 大体逻辑已写再注释.
int BTreeLeafSize(BTNode* root) // 二叉树叶子节点个数，接收一个二叉树根节点指针 { if (root == NULL) // 终止条件：如果当前节点为空，则叶子节点个数为 0，返回 0 { return 0; } if (root->left == NULL && root->right == NULL) // 如果当前节点左右子树都为空，则说明它是一个叶子节点，返回 1 { return 1; } // 递归计算其左右子树中叶子节点的个数，将它们相加即为二叉树中叶子节点的个数 return BTreeLeafSize(root->left) + BTreeLeafSize(root->right); }
二叉树的高度
- 大体逻辑已写再代码逻辑了，还是那句号，自己画上递归展开图更能了解递归与代码的意
义.
int BTreeHeight(BTNode* root) // 二叉树高度，接收一个二叉树根节点指针 { if (root == NULL) // 终止条件：如果当前节点为空，则高度为 0，返回 0 return 0; // 递归计算其左右子树的高度，将左右子树中高度较大的值加 1 即为该二叉树的高度 int leftHeight = BTreeHeight(root->left); int rightHeight = BTreeHeight(root->right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; }
二叉树第k层结点个数
- 在递归过程中，我们需要判断当前节点的情况。如果当前节点为空，则说明已经遍历到了
二叉树的底部，可以直接返回 0。如果 k 的值为 1，则说明当前节点就是第 k 层节点，此时第 k 层节点个数为 1，可以直接返回 1
int BTreeLevelKSize(BTNode* root, int k) // 计算二叉树第 k 层节点个数，接收一个二叉树根节点指针和层数 k { assert(k > 0); // 判断 k 是否大于 0，如果小于等于 0，表示该树不存在，因为树跟节点就是第一层 if (root == NULL) // 终止条件：如果当前节点为空，返回 0 return 0; if (k == 1) // 如果 k 为 1，则说明当前节点为第 k 层节点，返回 1 return 1; // 递归地计算当前节点的左子树中第 k - 1 层节点的个数和右子树中第 k - 1 层节点的个数， //将它们相加即为当前二叉树中第 k 层节点的个数。 return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1); }
二叉树的层序遍历
- 层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
- 假设二叉树是这样的
- 利用队列实现了二叉树的层序遍历，首先将根节点入队，然后循环取出队首元素，输出其
值，并将其左右子树入队。这样可以保证每一层的节点都按从左到右的顺序输出，实现了层序遍历的效果。这样就实现了层序从左到右遍历二叉树。
void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); // 初始化队列 if (root) QueuePush(&q, root); // 将根节点入队 while (!QueueEmpty(&q)) // 当队列不为空时循环 { BTNode* front = QueueFront(&q); // 取出队首元素 QueuePop(&q); // 将队首元素出队 printf("%d ", front->data); // 输出队首元素的值 if(front->left) QueuePush(&q, front->left); // 如果左子树不为空，将左子树入队 if (front->right) QueuePush(&q, front->right); // 如果右子树不为空，将右子树入队 } printf("\n"); QueueDestroy(&q); // 销毁队列 }
- 递归法 (较复杂如看不懂，只需掌握上面那种方法即可)
// 定义二维数组类型 typedef struct { int **data; // 指向二维数组的指针 int size; // 二维数组的行数 int *colSize; // 二维数组每行的列数 } Result; // 定义递归函数 void order(struct TreeNode* cur, Result* result, int depth) { if (cur == NULL) return; if (result->size == depth) { // 如果当前行还没有被创建，就创建一个新的行 result->data[depth] = (int *)malloc(sizeof(int) * 1000); // 每行最多存放 1000 个节点的值 result->colSize[depth] = 0; // 初始化该行的节点数为 0 result->size++; // 行数加 1 } result->data[depth][result->colSize[depth]] = cur->val; // 将当前节点的值存放在当前行的末尾 result->colSize[depth]++; // 该行的节点数加 1 order(cur->left, result, depth + 1); // 递归遍历左子树 order(cur->right, result, depth + 1); // 递归遍历右子树 } // 层序遍历 int **levelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes) { Result result; result.data = (int **)malloc(sizeof(int *) * 1000); // 初始化二维数组 result.size = 0; // 初始化行数为 0 result.colSize = (int *)malloc(sizeof(int) * 1000); // 初始化每行的节点数为 0 order(root, &result, 0); // 从根节点开始递归遍历二叉树 *returnSize = result.size; // 将行数赋值给返回值中的 returnSize *returnColumnSizes = result.colSize; // 将每行的节点数赋值给返回值中的 returnColumnSizes return result.data; // 返回存放节点值的二维数组 }
