本章重点
- 二叉树的链式存储
- 二叉树链式结构的实现
- 二叉树的遍历
- 二叉树的节点个数以及高度
- 二叉树的创建和销毁
- 二叉树的优先遍历和广度优先遍历
- 二叉树基础oj练习
1.二叉树的链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面学到高阶数据结构如红黑树等会用到三叉链。
typedef int BTDataType; // 二叉链 struct BinaryTreeNode { struct BinTreeNode* left; // 指向当前节点左孩子 struct BinTreeNode* right; // 指向当前节点右孩子 BTDataType data; // 当前节点值域 }; // 三叉链 struct BinaryTreeNode { struct BinTreeNode* parent; // 指向当前节点的双亲 struct BinTreeNode* left; // 指向当前节点左孩子 struct BinTreeNode* right; // 指向当前节点右孩子 BTDataType data; // 当前节点值域 };
2.二叉树链式结构的实现
这里我们就不讲解二叉树链式结构的增删查改，因为二叉树链式结构的增删查改没有意义，其链式二叉树形式复杂，数据增删查改消耗较大。
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在对二叉树结构掌握还不够深入，为了降低学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
下面我们根据上图手动去构建一个二叉树链式的结构。
#include <stdio.h> #include <stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }BTNode; BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->left = node->right = NULL; return node; } int main() { //手动构建二叉树 BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return 0; }
3.二叉树的遍历
3.1前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉 树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
- 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前（依次访问：跟 左子树 右子树）。
- 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）（依次访问：左子树 跟 右子树）。
- 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后（依次访问：左子树 右子树 跟）。
根据上面的图得出：
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：
- 空树
- 非空：根节点，根节点的左子树、根节点的右子树组成的。
- 前序遍历结果：1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
- 中序遍历结果： NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL
- 后序遍历结果： NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
// 二叉树前序遍历 void PreOrder(BTNode* root); // 二叉树中序遍历 void InOrder(BTNode* root); // 二叉树后序遍历 void PostOrder(BTNode* root);
3.1.1、二叉树前序遍历：void PreOrder(BTNode * root);
// 二叉树前序遍历 void PreOrder(BTNode* root) { if (root == NULL) { printf("NULL"); return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); }
运行结果：
递归图：
3.1.2、二叉树中序遍历：void InOrder(BTNode* root);
// 二叉树中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL"); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }
运行结果：
3.1.3、二叉树后序遍历：void PostOrder(BTNode* root);
// 二叉树后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL"); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
运行结果：
3.2层序遍历
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
我们该如何层序遍历一颗树呢？这里我们还能用递归嘛？不行，层序遍历没有先访问左子树和右子树的关系，层序遍历是一层一层访问的，递归的思想不符合层序遍历，这里我们可以使用队列，先把根节点入队列，然后当根节点出队列的时候，再把根节点的左右孩子入队列，特点是上一层带下一层，由于队列是先进先出的特点，刚好符合层序遍历。
这里需要注意一个问题，我们存储队列的数据是链式树中的data嘛，这样并不行，我们如果存放值进去，就找不到左右孩子的值了，所以我们需要存储结构体，但是二叉树结构体所占空间大，因此我们传入二叉树结构体的地址进去。
//Queue.h中需要修改QDataType typedef struct BinaryTreeNode* QDataType; #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }BTNode; #include "Queue.h" // 层序遍历 void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if(root != NULL) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); printf("%d ", front->data); if(front->left) QueuePush(&q, front->left); if (front->right) QueuePush(&q, front->right); QueuePop(&q); } QueueDestroy(&q); } BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->left = node->right = NULL; return node; } int main() { //手动构建二叉树 BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; LevelOrder(node1); return 0; }
运行结果：
【二叉树魔法：链式结构与递归的纠缠】(中)：https://developer.aliyun.com/article/1425246
