二叉树的链式结构

前言

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

结束语

好了，本节内容到此结束了，主要对二叉树的遍历有了新的认识理解，下一节小编将介绍二叉树的相关计算操作。

最后感谢友友们的支持，动下手指给小编点点赞，发个评论吧！！！