初阶数据结构【TOP】- 11.普通二叉树的介绍 - 1. (细致,保姆~~!)

---

前言

本篇文章笔者将会对普通二叉树部分进行细致的讲解 , 本篇主要包括以下内容: 二叉树链式结构的介绍 ,二叉树的遍历. 笔者会一步一步分析带学者领略递归的美好~~

---

一、普通二叉树的链式结构

在前面章节中 , 笔者对特殊二叉树部分进行了讲解, 特殊二叉树是基于数组实现的 ,但对于普通二叉树来说就要使用链式结构来实现了 ,以下将具体介绍 !

那么什么是链式结构呢 ? 这里就好比如链表 , 是一个一个节点组成. 这里笔者推荐一种特殊方法 : 左孩子 , 右兄弟表示法 .

● 左孩子右兄弟表示法

顾名思义: 我们要定义两个指针 , 一个指向左孩子 , 一个指向右孩子(左孩子的右兄弟).

● 链式结构表示法

// 普通二叉树typedef int OrdBinTreeDataType;// 普通二叉树的链式声明
typedef struct OrdBinTree
{OrdBinTreeDataType data;struct OrdBinTree* Left;struct OrdBinTree* Right;
}OBTree;

---

二、 造树

在当前阶段 , 笔者建议学者采用 " 手动造树 " 的方法 , 这种方法同样也是我们在遇到一些相关OJ问题时可以采用的一种寻找问题的方法 .

● 手动造树

typedef int OrdBinTreeDataType;// 普通二叉树的链式声明
typedef struct OrdBinTree
{OrdBinTreeDataType data;struct OrdBinTree* Left;struct OrdBinTree* Right;
}OBTree;//手动造树
OBTree* ByNode(int x)
{OBTree* node = (OBTree*)malloc(sizeof(OBTree));if (node == NULL){perror("malloc fail! ");return NULL;}node->data = x;node->Left = node->Right = NULL;return node;
}OBTree* CreatTree()
{OBTree* node1 = ByNode(1);OBTree* node2 = ByNode(2);OBTree* node3 = ByNode(3);OBTree* node4 = ByNode(4);OBTree* node5 = ByNode(5);OBTree* node6 = ByNode(6);//连接node1->Left = node2;node1->Right = node4;node2->Left = node3;node4->Left = node5;node4->Right = node6;return node1;}

当树造好了以后就可以开始学习 , 树的遍历相关知识了 .

---

三、普通二叉树的遍历

● 分类

这里讨论 : 前序遍历 , 中序遍历 , 后序遍历 , 层序遍历 .
这里笔者介绍前三种~

首先 , 这里的 前 , 中 , 后 , 指的是根的位置是 : 前 , 中 , 后.

在实现这些变量之前 , 笔者介绍一种方法 , 分支递归

● 实现思想

首选 , 对于二叉树我们知道二叉树是由递归定义的 , 所以在普通二叉树中可以采用递归的思想来进行, 递归 : 大问题化小问题 ,直至问题解决 .

其次, 任何一颗树都是由根节点和子树构成 , 这是分支递归的核心 !

这里 , 理解递归的概念 : 递则往下一层一层递 , 归则往回一层一层归. 也就是说 : 每次的归只能归回该函数的上一层. (这是极其重要的 !)

★ 递归解释图:

那么什么是分支递归, 其实就是逐渐拆解成小问题得递归 , 以下将会有所体会 ~~

● 实现

◐ 前序遍历

形式: 根 , 左节点 , 右节点 . (遍历顺序) . 遇到空树才停止 " 递 ".

这里笔者先给出前序遍历代码 ,以便学者理解 !

★ 代码

//前序遍历
void PreOrder(OBTree* tree)
{if (tree == NULL){printf("NULL ");return;}printf("%d ", tree->data); // 根PreOrder(tree->Left); //左孩子PreOrder(tree->Right); //右孩子}

访问顺序 :

★ 递

1. 访问到根 - 1 的位置
2. 访问绿色左树 , 但绿色左树不为空 , 则继续向下访问 .
3. 访问绿色部分的根 - 2 的位置
4. 访问红色部分 , 但红色左树不为空 , 则继续向下访问 .
5. 访问红色部分的根 - 3 的位置
6. 访问蓝色部分 , 蓝色部分为空 , 则停止 ’ 递 ’ .

! 蓝色数字部分为优先访问的节点值 !

♦ 递过程的打印

因为此为前序遍历 , 故每一次递是先访问根的 , 根据以上代码 , 则 : 会优先打印出
1 2 3

那么右边分析同上即可.

★ 归

★ 详细流程

每一个节点的递归与其一样 , 同样分析即可 !

★ 递归展开图

执行完以上过程 , 则最终打印结果为 :

◐ 中序遍历

经过以上细致的分析 ,相信学者对遍历有所认识 , 那么中序 , 后序就显得特别简单了, 无非就是根的位置不同的区别

★ 代码

//中序遍历
void InOrder(OBTree* tree)
{if (tree == NULL){printf("NULL ");return;}InOrder(tree->Left);printf("%d ", tree->data); InOrder(tree->Right);
}

★ 结果

◐ 后序遍历

//后序遍历
void AfterOrder(OBTree* tree)
{if (tree == NULL){printf("NULL ");return;}AfterOrder(tree->Left);AfterOrder(tree->Right);printf("%d ", tree->data);}

★ 结果

---

四、遍历完整代码

#define  _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <stdlib.h>
//树的遍历
typedef int OrdBinTreeDataType;// 普通二叉树的链式声明
typedef struct OrdBinTree
{OrdBinTreeDataType data;struct OrdBinTree* Left;struct OrdBinTree* Right;
}OBTree;//手动造树
OBTree* ByNode(int x)
{OBTree* node = (OBTree*)malloc(sizeof(OBTree));if (node == NULL){perror("malloc fail! ");return NULL;}node->data = x;node->Left = node->Right = NULL;return node;
}OBTree* CreatTree()
{OBTree* node1 = ByNode(1);OBTree* node2 = ByNode(2);OBTree* node3 = ByNode(3);OBTree* node4 = ByNode(4);OBTree* node5 = ByNode(5);OBTree* node6 = ByNode(6);//连接node1->Left = node2;node1->Right = node4;node2->Left = node3;node4->Left = node5;node4->Right = node6;return node1;}//前序遍历
void PreOrder(OBTree* tree)
{if (tree == NULL){printf("NULL ");return;}printf("%d ", tree->data); // 根PreOrder(tree->Left); //左孩子PreOrder(tree->Right); //右孩子}//中序遍历
void InOrder(OBTree* tree)
{if (tree == NULL){printf("NULL ");return;}InOrder(tree->Left);printf("%d ", tree->data); InOrder(tree->Right);
}//后序遍历
void AfterOrder(OBTree* tree)
{if (tree == NULL){printf("NULL ");return;}AfterOrder(tree->Left);AfterOrder(tree->Right);printf("%d ", tree->data);}
int main()
{OBTree* tree = CreatTree();printf("前序: \n");PreOrder(tree);printf("\n");printf("中序: \n");InOrder(tree);printf("\n");printf("后序: \n");AfterOrder(tree);printf("\n");return 0;}

---

五、总结

以上是对二叉树的遍历的讲解 ,其实就是对递归的深入 ,相信大家通过学习会有所收获 !