大家好，欢迎来到IT知识分享网。
一、几个概念
二叉树（binary tree）：是 n（n >= 0）个结点（每个结点最多只有2棵子树）的有限集合，该集合可为空集（称为空二叉树），或由一个根节点和两颗互不相交的，称为根节点的左子树和右子树的二叉树组成。
如下图中
图1是一棵二叉树。
图2是非二叉树，因为 A 结点有3棵子树，其次 E 结点和 F 结点相交了
二叉链表：是二叉树的一种链式存储结构，其中每个结点包含三个字段：一个数据字段(data)和两个指针字段(*lchild、*rchild)，分别指向该结点的左孩子和右孩子。如果某个结点没有左孩子或右孩子，那么对应的指针字段为NULL。
用 C 语言可以表述为：
typedef struct binary_node { char data; struct binary_node *lchild, *rchild; }binary_tree;二、前序遍历二叉树（Pre-order Traversal）
前序遍历二叉树（Pre-order Traversal）的规则为：从根结点出发，先访问该结点，然后前序遍历该结点的左子树，再然后前序遍历该结点的右子树
所以，前序遍历图1这棵二叉树的步骤如图4所示
所以，图1这颗二叉树的前序遍历顺序为：ABDECF
1、算法思路
（1）从根结点 A 出发，A 结点入栈，先访问 A 结点，然后前序遍历 A 结点的左子树
（2）A 结点的左子树的根结点为 B，B 结点入栈，先访问 B 结点，然后前序遍历 B 结点的左子树
（3）B 结点的左子树的根结点为 D，D 结点入栈，先访问 D 结点，然后前序遍历 D 结点的左子树
（4）D 结点的左子树为空，则返回
（5）逻辑返回到 D 结点，然后前序遍历 D 结点的右子树
（6）D 结点的右子树为空，则返回
（7）逻辑返回到 D 结点，此时访问 D 结点，前序遍历 D 结点的左右子树的逻辑都已完成，则返回，D 结点出栈。
（8）逻辑返回到 B 结点，然后前序遍历 B 结点的右子树
（9）B 结点的右子树的根结点为 E，E 结点入栈，先访问 E 结点，然后前序遍历 E 结点的左子树
（10）E 结点的左子树为空，则返回
（11）逻辑返回到 E 结点，然后前序遍历 E 结点的右子树
（12）E 结点的右子树为空，则返回
（13）逻辑返回到 E 结点，此时访问 E 结点，前序遍历 E 结点的左右子树的逻辑都已完成，则返回，E 结点出栈。
（14）逻辑返回到 B 结点，此时访问 B 结点，前序遍历 B 结点的左右子树的逻辑都已完成，则函数返回，B 结点出栈。
（15）逻辑返回到 A 结点，然后前序遍历 A 结点的右子树
（16）A 结点的右子树的根结点为 C，C 结点入栈，先访问 C 结点，然后前序遍历 C 结点的左子树
（17）C 结点的左子树的根结点为 F，F 结点入栈，先访问 F 结点，然后前序遍历 F 结点的左子树
（18）F 结点的左子树为空，则返回
（19）逻辑返回到 F 结点，然后前序遍历 F 结点的右子树
（20）F 结点的右子树为空，则返回
（21）逻辑返回到 F 结点，此时访问 F 结点，前序遍历 F 结点的左右子树的逻辑都已完成，则返回，F 结点出栈。
（22）逻辑返回到 C 结点，然后前序遍历 C 结点的右子树
（23）C 结点的右子树为空，则返回
（24）逻辑返回到 C 结点，此时访问 C 结点，前序遍历 C 结点的左右子树的逻辑都已完成，则返回，C 结点出栈。
（25）逻辑返回到 A 结点，此时访问 A 结点，前序遍历 A 结点的左右子树的逻辑都已完成，则返回，A 结点出栈。
（26）前序遍历二叉树已完成， 所以，前序遍历顺序为：ABDECF
2、实现代码
#include <stdio.h> #include <string.h> #include <stdlib.h> char *g_str = "ABDECF"; // 扩展二叉树前序序列 int g_index = 0; typedef struct binary_node { char data; struct binary_node *lchild, *rchild; }binary_tree; void create_binary_tree(binary_tree T) { if (strlen(g_str) == 0) return; if (g_str[g_index] == '#') { *T = NULL; g_index++; } else { *T = malloc(sizeof(T)); (*T)->data = g_str[g_index]; g_index++; create_binary_tree(&(*T)->lchild); create_binary_tree(&(*T)->rchild); } } void visit_node(binary_tree *T) { printf("%c\n", T->data); } void pre_order_tree(binary_tree *T) { if (!T) return; visit_node(T); pre_order_tree(T->lchild); pre_order_tree(T->rchild); } /*销毁用后序遍历*/ void destroy_binary_tree(binary_tree *T) { if (!T) return; destroy_binary_tree(T->lchild); destroy_binary_tree(T->rchild); printf("%c\n", T->data); free(T); } int main(int argc, char *argv[]) { binary_tree *T; create_binary_tree(&T); printf("------前序遍历-------\n"); pre_order_tree(T); printf("------销毁二叉树------\n"); destroy_binary_tree(T); return 0; }
三、中序遍历二叉树（In-order Traversal）
中序遍历二叉树（In-order Traversal）的规则为：从根结点出发，先中序遍历该结点的左子树，然后访问该结点，再然后中序遍历该结点的右子树
所以，中序遍历图1这棵二叉树的步骤如下图所示
所以，图1这颗二叉树中序遍历顺序为：DBEAFC
1、算法思路
（1）从根结点 A 出发，A 结点入栈，先中序遍历 A 结点的左子树
（2）A 结点的左子树的根结点为 B，B 结点入栈，先中序遍历 B 结点的左子树
（3）B 结点的左子树的根结点为 D，D 结点入栈，先中序遍历 D 结点的左子树
（4）D 结点的左子树为空，则返回
（5）逻辑返回到 D 结点，然后访问 D 结点，再然后中序遍历 D 结点的右子树
（6）D 结点的右子树为空，则返回
（7）逻辑返回到 D 结点，此时中序遍历 D 结点的左子树，访问 D 结点，中序遍历 D 结点的右子树的逻辑都已完成，则返回，D 结点出栈。
（8）逻辑返回到 B 结点，然后访问 B 结点，再然后中序遍历 B 结点的右子树
（9）B 结点的右子树的根结点为 E，E 结点入栈，先中序遍历 E 结点的左子树
（10）E 结点的左子树为空，则返回
（11）逻辑返回到 E 结点，然后访问 E 结点，再然后中序遍历 E 结点的右子树
（12）E 结点的右子树为空，则返回
（13）逻辑返回到 E 结点，此时中序遍历 E 结点的左子树，访问 E 结点，中序遍历 E 结点的右子树的逻辑都已完成，则返回，E 结点出栈。
（14）逻辑返回到 B 结点，此时中序遍历 B 结点的左子树，访问 B 结点，中序遍历 B 结点的右子树的逻辑都已完成，则返回，B 结点出栈。
（15）逻辑返回到 A 结点，然后访问 A 结点，再然后中序遍历 A 结点的右子树
（16）A 结点的右子树的根结点为 C，C 结点入栈，先中序遍历 C 结点的左子树
（17）C 结点的左子树的根结点为 F，F 结点入栈，先中序遍历 F 结点的左子树
（18）F 结点的左子树为空，则返回
（19）逻辑返回到 F 结点，然后访问 F 结点，再然后中序遍历 F 结点的右子树
（20）F 结点的右子树为空，则返回
（21）逻辑返回到 F 结点，此时中序遍历 F 结点的左子树，访问 F 结点，中序遍历 F 结点的右子树的逻辑都已完成，则返回，F 结点出栈。
（22）逻辑返回到 C 结点，然后访问 C 结点，再然后中序遍历 C 结点的右子树
（23）C 结点的右子树为空，则返回
（24）逻辑返回到 C 结点，此时中序遍历 C 结点的左子树，访问 C 结点，中序遍历 C 结点的右子树的逻辑都已完成，则返回，C 结点出栈。
（25）逻辑返回到 A 结点，此时中序遍历 A 结点的左子树，访问 A 结点，中序遍历 A 结点的右子树的逻辑都已完成，则返回，A 结点出栈。
（26）中序遍历二叉树已完成， 所以，中序遍历顺序为：DBEAFC
2、实现代码
#include <stdio.h> #include <string.h> #include <stdlib.h> char *g_str = "ABDECF"; // 扩展二叉树前序序列 int g_index = 0; typedef struct binary_node { char data; struct binary_node *lchild, *rchild; }binary_tree; void create_binary_tree(binary_tree T) { if (strlen(g_str) == 0) return; if (g_str[g_index] == '#') { *T = NULL; g_index++; } else { *T = malloc(sizeof(T)); (*T)->data = g_str[g_index]; g_index++; create_binary_tree(&(*T)->lchild); create_binary_tree(&(*T)->rchild); } } void visit_node(binary_tree *T) { printf("%c\n", T->data); } void pre_order_tree(binary_tree *T) { if (!T) return; visit_node(T); pre_order_tree(T->lchild); pre_order_tree(T->rchild); } void in_order_tree(binary_tree *T) { if (!T) return; in_order_tree(T->lchild); visit_node(T); in_order_tree(T->rchild); } /*销毁用后序遍历*/ void destroy_binary_tree(binary_tree *T) { if (!T) return; destroy_binary_tree(T->lchild); destroy_binary_tree(T->rchild); printf("%c\n", T->data); free(T); } int main(int argc, char *argv[]) { binary_tree *T; create_binary_tree(&T); printf("------中序遍历-------\n"); in_order_tree(T); printf("------销毁二叉树------\n"); destroy_binary_tree(T); return 0; }
四、后序遍历二叉树（Post-order Traversal）
后序遍历二叉树（Post-order Traversal）的规则为：从根结点出发，先后序遍历该结点的左子树，然后后序遍历该结点的右子树，再然后访问该结点
所以，后序遍历图1这棵二叉树的步骤如下图所示
所以，图1这颗二叉树后序遍历顺序为：DEBFCA
1、算法思路
（1）从根结点 A 出发，A 结点入栈，先后序遍历 A 结点的左子树
（2）A 结点的左子树的根结点为 B，B 结点入栈，先后序遍历 B 结点的左子树
（3）B 结点的左子树的根结点为 D，D 结点入栈，先后序遍历 D 结点的左子树
（4）D 结点的左子树为空，则返回
（5）逻辑返回到 D 结点，然后后序遍历 D 结点的右子树
（6）D 结点的右子树为空，则返回
（7）逻辑返回到 D 结点，然后访问 D 结点，此时后序遍历 D 结点的左子树，后序遍历 D 结点的右子树，访问 D 结点的逻辑都已完成，则返回，D 结点出栈。
（8）逻辑返回到 B 结点，然后后序遍历 B 结点的右子树
（9）B 结点的右子树的根结点为 E，E 结点入栈，先后序遍历 E 结点的左子树
（10）E 结点的左子树为空，则返回
（11）逻辑返回到 E 结点，然后后序遍历 E 结点的右子树
（12）E 结点的右子树为空，则返回
（13）逻辑返回到 E 结点，然后访问 E 结点，此时后序遍历 E 结点的左子树，后序遍历 E 结点的右子树，访问 E 结点的逻辑都已完成，则返回，E 结点出栈。
（14）逻辑返回到 B 结点，然后访问 B 结点，此时后序遍历 B 结点的左子树，后序遍历 B 结点的右子树，访问 B 结点的逻辑都已完成，则返回，B 结点出栈。
（15）逻辑返回到 A 结点，然后后序遍历 A 结点的右子树
（16）A 结点的右子树的根结点为 C，C 结点入栈，先后序遍历 C 结点的左子树
（17）C 结点的左子树的根结点为 F，F 结点入栈，先后序遍历 F 结点的左子树
（18）F 结点的左子树为空，则返回
（19）逻辑返回到 F 结点，然后后序遍历 F 结点的右子树
（20）F 结点的右子树为空，则返回
（21）逻辑返回到 F 结点，然后访问 F 结点，此时后序遍历 F 结点的左子树，后序遍历 F 结点的右子树，访问 F 结点的逻辑都已完成，则返回，F 结点出栈。
（22）逻辑返回到 C 结点，然后后序遍历 C 结点的右子树
（23）C 结点的右子树为空，则返回
（24）逻辑返回到 C 结点，然后访问 C 结点，此时后序遍历 C 结点的左子树，后序遍历 C 结点的右子树，访问 C 结点的逻辑都已完成，则返回，C 结点出栈。
（25）逻辑返回到 A 结点，然后访问 A 结点，此时后序遍历 A 结点的左子树，后序遍历 A 结点的右子树，访问 A 结点的逻辑都已完成，则返回，A 结点出栈。
（26）后序遍历二叉树已完成， 所以，后序遍历顺序为：DEBFCA
2、实现代码
#include <stdio.h> #include <string.h> #include <stdlib.h> char *g_str = "ABDECF"; // 扩展二叉树前序序列 int g_index = 0; typedef struct binary_node { char data; struct binary_node *lchild, *rchild; }binary_tree; void create_binary_tree(binary_tree T) { if (strlen(g_str) == 0) return; if (g_str[g_index] == '#') { *T = NULL; g_index++; } else { *T = malloc(sizeof(T)); (*T)->data = g_str[g_index]; g_index++; create_binary_tree(&(*T)->lchild); create_binary_tree(&(*T)->rchild); } } void visit_node(binary_tree *T) { printf("%c\n", T->data); } void pre_order_tree(binary_tree *T) { if (!T) return; visit_node(T); pre_order_tree(T->lchild); pre_order_tree(T->rchild); } void in_order_tree(binary_tree *T) { if (!T) return; in_order_tree(T->lchild); visit_node(T); in_order_tree(T->rchild); } void post_order_tree(binary_tree *T) { if (!T) return; post_order_tree(T->lchild); post_order_tree(T->rchild); visit_node(T); } /*销毁用后序遍历*/ void destroy_binary_tree(binary_tree *T) { if (!T) return; destroy_binary_tree(T->lchild); destroy_binary_tree(T->rchild); printf("%c\n", T->data); free(T); } int main(int argc, char *argv[]) { binary_tree *T; create_binary_tree(&T); printf("------后序遍历-------\n"); post_order_tree(T); printf("------销毁二叉树------\n"); destroy_binary_tree(T); return 0; }
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/125943.html
