二叉树的链式结构
前言
Hello,友友们，小编将继续重新开始数据结构的学习，前面讲解了堆的部分知识，今天将讲解二叉树的链式结构的部分内容。
1.概念回顾与新增
二叉树是一种数据结构，其中每个节点最多有两个子节点，分别是左子节点和右子节点。二叉树的链式结构表示是使用指针（或引用）来连接节点，形成树形结构。每个节点包含一个数据元素和两个指向子节点的指针。
2.简单创建二叉树
分为节点的定义，创建节点，创建树
下面我们将简单的手撕一个二叉树：
typedef struct BTnode {int val;struct BTnode* left;struct BTnode* right;
}Node;//节点创建
Node* BuyNode(int x) {Node* node = (Node*)malloc(sizeof(Node));if (node == NULL) {perror("node fail");return NULL;}node->val = x;node->left = NULL;node->right = NULL;return node;
}
//树的创建
Node* CreatTree() {Node* node1 = BuyNode(1);Node* node2 = BuyNode(2);Node* node3 = BuyNode(3);Node* node4 = BuyNode(4);Node* node5 = BuyNode(5);Node* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
} 注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。
二叉树建立过后，接下来我们要进行二叉树的遍历操作
3.二叉树的遍历
所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有： 前序 / 中序 / 后序的递归结构遍历 ：
1. 前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历 (Inorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历 (Postorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根， 所以 N(Node ）、 L(Left subtree ）和 R(Right subtree ）又可解释为， 根的左子树和根的右子树 。 NLR 、 LNR 和 LRN 分别又称为先根遍历、中根遍历和后根遍历。
注意：为了方便理解，我们将空节点都视作为NULL
3.1前序遍历
代码：
void PreOrder(Node* root) {if (root == NULL) {printf("N ");return;}printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);} 递归图解：
代码递归理解：
运行结果：1 2 3 N N N 4 5 N N 6 N N
注意：中序和后序与前序的递归展开图类似，小编就不在展示了。
3.2中序遍历
void InOrder(Node* root) {if (root == NULL) {printf("N ");return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);}运行结果：N 3 N 2 N 1 N 5 N 4 N 6 N
3.3后序遍历
void PostOrder(Node* root) {if (root == NULL) {printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);}运行结果:N N 3 N 2 N N 5 N N 6 4 1
3.4层序遍历
层序遍历 ：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1 ，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第 2 层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
层序遍历较为复杂，这里我们采用队列的方式来实现层序遍历。
这里我们简单的用动态数组实现队列，包括了队列的初始化，入队出队判空的操作。
3.4.1队列的实现
// 队列结构
typedef struct Queue {Node* data[MAX];int front;int rear;
} Queue;// 初始化队列
void initQueue(Queue* q) {q->front = 0;q->rear = 0;
}// 入队
void enqueue(Queue* q, Node* node) {if ((q->rear + 1) % MAX == q->front) {printf("Queue is full\n");return;}q->data[q->rear] = node;q->rear = (q->rear + 1) % MAX;
}// 出队
Node* dequeue(Queue* q) {if (q->front == q->rear) {printf("Queue is empty\n");return NULL;}Node* node = q->data[q->front];q->front = (q->front + 1) % MAX;return node;
}// 判断队列是否为空
int isEmpty(Queue* q) {return q->front == q->rear;
}3.4.2层序遍历实现
从根节点开始，将每个节点的值打印出来，并依次将其左子节点和右子节点加入队列。
// 层序遍历函数
void levelOrder(Node* root) {if (root == NULL) {return;}Queue q;initQueue(&q);enqueue(&q, root);while (!isEmpty(&q)) {Node* node = dequeue(&q);printf("%d ", node->val);if (node->left) {enqueue(&q, node->left);}if (node->right) {enqueue(&q, node->right);}}
}3.5主函数测试代码
int main() {Node* root = CreatTree();PreOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");levelOrder(root);return 0;
}运行结果展示：
4.遍历相关选择练习
1. 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ A）
A . ABDHECFG
B. ABCDEFGH
C. HDBEAFCG
D. HDEBFGCA
2. 二叉树的先序遍历和中序遍历如下：先序遍历： EFHIGJK; 中序遍历： HFIEJKG. 则二叉树根结点为（A）
A . E B. F C. G D. H
3. 设一课二叉树的中序遍历序列： badce ，后序遍历序列： bdeca ，则二叉树前序遍历序列为(D)
A. adbce B. decab C. debac D. abcde
4. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列 为(A)
A. FEDCBA
B. CBAFED
C. DEFCBA
D. ABCDEF
结束语
好了，本节内容到此结束了，主要对二叉树的遍历有了新的认识理解，下一节小编将介绍二叉树的相关计算操作。最后感谢友友们的支持，动下手指给小编点点赞，发个评论吧！！！