简述网站规划的主要任务,百度一下全知道,河源市网站建设公司,肇庆seo霸屏文章目录 前言一、普通二叉树的链式结构二、 造树三、普通二叉树的遍历四、遍历完整代码五、总结 前言
本篇文章笔者将会对普通二叉树部分进行细致的讲解 , 本篇主要包括以下内容: 二叉树链式结构的介绍 ,二叉树的遍历. 笔者会一步一步分析带学者领略递归的美好~~ 一、普通二叉… 文章目录 前言一、普通二叉树的链式结构二、 造树三、普通二叉树的遍历四、遍历完整代码五、总结 前言
本篇文章笔者将会对普通二叉树部分进行细致的讲解 , 本篇主要包括以下内容: 二叉树链式结构的介绍 ,二叉树的遍历. 笔者会一步一步分析带学者领略递归的美好~~ 一、普通二叉树的链式结构
在前面章节中 , 笔者对特殊二叉树部分进行了讲解, 特殊二叉树是基于数组实现的 ,但对于普通二叉树来说就要使用链式结构来实现了 ,以下将具体介绍 !
那么什么是链式结构呢 ? 这里就好比如链表 , 是一个一个节点组成. 这里笔者推荐一种特殊方法 : 左孩子 , 右兄弟表示法 .
● 左孩子右兄弟表示法
顾名思义: 我们要定义两个指针 , 一个指向左孩子 , 一个指向右孩子(左孩子的右兄弟). ● 链式结构表示法
// 普通二叉树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;}五、总结
以上是对二叉树的遍历的讲解 ,其实就是对递归的深入 ,相信大家通过学习会有所收获 !
