数据结构-二叉树的遍历和线索二叉树

一、了解二叉树遍历

1. 先序遍历

定义：先序遍历是指在访问一个节点时，先访问该节点本身，然后再访问其左子树和右子树。

顺序：

访问根节点
先序遍历左子树
先序遍历右子树

示例：
假设有如下二叉树：

      A/ \B   C/ \D   E

先序遍历的结果为：A, B, D, E, C

应用：先序遍历通常用于复制树结构或生成树的前缀表达式。

2. 中序遍历

定义：中序遍历是指在访问一个节点时，先访问其左子树，然后访问该节点本身，最后访问其右子树。

顺序：

中序遍历左子树
访问根节点
中序遍历右子树

示例：
对于同样的二叉树：

      A/ \B   C/ \D   E

中序遍历的结果为：D, B, E, A, C

应用：中序遍历常用于生成树的中缀表达式，特别是在二叉搜索树中，中序遍历会得到一个有序的节点值列表。

3. 后序遍历

定义：后序遍历是指在访问一个节点时，先访问其左子树和右子树，最后访问该节点本身。

顺序：

后序遍历左子树
后序遍历右子树
访问根节点

示例：
对于同样的二叉树：

      A/ \B   C/ \D   E

后序遍历的结果为：D, E, B, C, A

应用：后序遍历通常用于删除树的节点或计算树的大小，也常用于生成树的后缀表达式。

总结:

先序遍历：根 -> 左 -> 右
中序遍历：左 -> 根 -> 右
后序遍历：左 -> 右 -> 根

二、二叉树遍历程序（C语言-先/中/后序遍历）

1. 链式存储结构

// 定义二叉树节点结构体
typedef struct TreeNode {int data;               // 节点存储的数据struct TreeNode* Left;  // 指向左子节点的指针struct TreeNode* Right; // 指向右子节点的指针
} TreeNode, * BiTree; // 定义BiTree为TreeNode的指针类型

2. 打印节点数据


// 打印节点数据的函数
void printf_BiTree(int data) {printf("%d ", data); // 打印数据并添加空格以便于输出格式
}

3. 先序遍历


// 先序遍历函数
void PreOrder(BiTree T) {if (T != NULL) { // 如果节点不为空printf_BiTree(T->data); // 打印当前节点数据PreOrder(T->Left);       // 递归遍历左子树PreOrder(T->Right);      // 递归遍历右子树}
}

4. 中序遍历


// 中序遍历函数
void InOrder(BiTree T) { // 修正函数名if (T != NULL) { // 如果节点不为空InOrder(T->Left);       // 递归遍历左子树printf_BiTree(T->data); // 打印当前节点数据InOrder(T->Right);      // 递归遍历右子树}
}

5. 后续遍历


// 后序遍历函数
void PostOrder(BiTree T) { // 修正函数名if (T != NULL) { // 如果节点不为空PostOrder(T->Left);       // 递归遍历左子树PostOrder(T->Right);      // 递归遍历右子树printf_BiTree(T->data);   // 打印当前节点数据}
}

6. 演示案例


// 主函数
int main() {// 创建树节点TreeNode n1 = { 1, NULL, NULL }; // 创建叶子节点1TreeNode n2 = { 2, NULL, NULL }; // 创建叶子节点2TreeNode n3 = { 3, &n1, &n2 };   // 创建根节点3，左子树为n1，右子树为n2// 打印先序遍历结果printf("PreOrder: ");PreOrder(&n3); // 调用先序遍历函数printf("\n");   // 换行// 打印中序遍历结果printf("InOrder: ");InOrder(&n3); // 调用中序遍历函数printf("\n");  // 换行// 打印后序遍历结果printf("PostOrder: ");PostOrder(&n3); // 调用后序遍历函数printf("\n");    // 换行return 0; // 程序结束
}

三、总代码

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>// 定义二叉树节点结构体
typedef struct TreeNode {int data;               // 节点存储的数据struct TreeNode* Left;  // 指向左子节点的指针struct TreeNode* Right; // 指向右子节点的指针
} TreeNode, * BiTree; // 定义BiTree为TreeNode的指针类型// 打印节点数据的函数
void printf_BiTree(int data) {printf("%d ", data); // 打印数据并添加空格以便于输出格式
}// 先序遍历函数
void PreOrder(BiTree T) {if (T != NULL) { // 如果节点不为空printf_BiTree(T->data); // 打印当前节点数据PreOrder(T->Left);       // 递归遍历左子树PreOrder(T->Right);      // 递归遍历右子树}
}// 中序遍历函数
void InOrder(BiTree T) { // 修正函数名if (T != NULL) { // 如果节点不为空InOrder(T->Left);       // 递归遍历左子树printf_BiTree(T->data); // 打印当前节点数据InOrder(T->Right);      // 递归遍历右子树}
}// 后序遍历函数
void PostOrder(BiTree T) { // 修正函数名if (T != NULL) { // 如果节点不为空PostOrder(T->Left);       // 递归遍历左子树PostOrder(T->Right);      // 递归遍历右子树printf_BiTree(T->data);   // 打印当前节点数据}
}// 主函数
int main() {// 创建树节点TreeNode n1 = { 1, NULL, NULL }; // 创建叶子节点1TreeNode n2 = { 2, NULL, NULL }; // 创建叶子节点2TreeNode n3 = { 3, &n1, &n2 };   // 创建根节点3，左子树为n1，右子树为n2// 打印先序遍历结果printf("PreOrder: ");PreOrder(&n3); // 调用先序遍历函数printf("\n");   // 换行// 打印中序遍历结果printf("InOrder: ");InOrder(&n3); // 调用中序遍历函数printf("\n");  // 换行// 打印后序遍历结果printf("PostOrder: ");PostOrder(&n3); // 调用后序遍历函数printf("\n");    // 换行return 0; // 程序结束
}