初阶数据结构【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 的位置
- 访问绿色左树 , 但绿色左树不为空 , 则继续向下访问 .
- 访问绿色部分的根 - 2 的位置
- 访问红色部分 , 但红色左树不为空 , 则继续向下访问 .
- 访问红色部分的根 - 3 的位置
- 访问蓝色部分 , 蓝色部分为空 , 则停止 ’ 递 ’ .
! 蓝色数字部分为优先访问的节点值 !
♦ 递过程的打印
因为此为前序遍历 , 故每一次递是先访问根的 , 根据以上代码 , 则 : 会优先打印出
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;
}
五、总结
以上是对二叉树的遍历的讲解 ,其实就是对递归的深入 ,相信大家通过学习会有所收获 !