标准物质网站建设网站开发时间一般是

当前位置： 首页 > news >正文

标准物质网站建设,网站开发时间一般是,设计网站公司只找亿企邦,网站设计注意因素普通二叉树的操作1. 前情说明2. 二叉树的遍历2.1 前序、中序以及后序遍历2.1.1 前序遍历2.1.2 中序遍历、后序遍历2.2 题目练习2.2.1 求一棵二叉树的节点个数2.2.2 求一棵二叉树的叶节点个数2.2.3 求一棵二叉树第k层节点的个数2.2.4 求一棵二叉树的深度2.2.5 在一棵二叉树中查找… 普通二叉树的操作1. 前情说明2. 二叉树的遍历2.1 前序、中序以及后序遍历2.1.1 前序遍历2.1.2 中序遍历、后序遍历2.2 题目练习2.2.1 求一棵二叉树的节点个数2.2.2 求一棵二叉树的叶节点个数2.2.3 求一棵二叉树第k层节点的个数2.2.4 求一棵二叉树的深度2.2.5 在一棵二叉树中查找值为x的节点2.2.6 销毁一棵二叉树2.3 二叉树的层序遍历2.4 题目练习2.4.1 判断一棵二叉树是否是完全二叉树1. 前情说明 本文主要是针对二叉树的链式结构操作进行讲解。 对于普通二叉树的学习已经不能像之前学线性表堆等数据结构那样围绕增删查改来进行操作学习。说到底对于普通二叉树的增删查改是没有意义的。树形结构本身相对线性结构就更复杂而且普通二叉树对于数据的操作又不能达到一些规律性的性质种种原因都限制了普通二叉树的增删改查操作。如果非要进行数据的增删改查不如去选择操作更方便的结构。比如在数据存储上与普通二叉树复杂的存储结构相比不如去选择顺序表链表等更简单的结构进行数据的存储这类数据结构对数据的维护也会更容易。 既然如此那我们学习普通二叉树的意义何在呢 为学习更复杂更有意义的二叉树做储备。很多二叉树的OJ算法题目都是出在普通二叉树上的。 所以对于普通二叉树的操作本文会涉及几道题目的练习方便大家认识理解。 说到这里既然不学增删查改那还学什么呢 那当然需要学习的是对普通二叉树的遍历和结构控制了。

1. 二叉树的遍历 学习二叉树的结构最简单的方式就是遍历。所谓二叉树的遍历是指按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。而访问节点所做的操作就依赖于具体的应用问题了。 遍历是二叉树最重要的操作之一也是在二叉树上进行其它操作的基础。 在进行遍历之前还是再来看一下二叉树的概念吧。 二叉树是 空树非空由根节点根节点的左子树根节点的右子树组成
   从概念中可以看出二叉树的定义是递归式的因此要注意的是后续各种操作中基本都是按照该递归概念实现的。 同时据此可以给出二叉树节点的定义如下 typedef int BTDataType; typedef struct BinaryTreeNode {struct BinaryTreeNode* left;//存放左子树的根节点地址struct BinaryTreeNode* right;//存放右子树的根节点地址BTDataType data;//根节点的数据域 }BTNode;2.1 前序、中序以及后序遍历 按照规则二叉树的遍历有三种递归结构的遍历 前序遍历(也叫先序遍历先根遍历) —— 访问根节点的操作发生在遍历其左右子树之前。中序遍历(也叫中根遍历) —— 访问根节点的操作发生在遍历其左右子树之中(间)。后序遍历(也叫后根遍历) —— 访问根节点的操作发生在遍历其左右子树之后。 2.1.1 前序遍历 根据先根节点再左子树再右子树的顺序走一遍大致可以得到如下图所示的遍历轨迹。 先从根节点1开始遍历根节点1遍历之后就开始遍历左子树 再从左子树的根节点2开始遍历根节点2遍历之后又开始遍历根节点2的左子树 再从左子树的根节点3开始遍历跟节点3遍历之后又开始遍历跟节点3的左子树 但是根节点3的左子树为空于是路线直接返回到根节点3开始遍历根节点3的右子树 但是根节点3的右子树为空于是路线直接返回到根节点3此时根节点3所在的子树前序遍历已经完成所以路线直接返回到根节点2开始遍历跟节点2的右子树 但是根节点2的右子树为空于是路线直接返回到根节点2此时根节点2所在的子树前序遍历已经完成所以路线直接返回到根节点1开始遍历跟节点1的右子树 再从右子树的根节点4开始遍历根节点4遍历之后又开始遍历根节点4的左子树 再从左子树的根节点5开始遍历根节点5遍历之后又开始遍历根节点5的左子树 但是根节点5的左子树为空于是路线直接返回到根节点5开始遍历根节点5的右子树 但是根节点5的右子树为空于是路线直接返回到根节点5此时根节点5所在的子树前序遍历已经完成所以路线直接返回到根节点4开始遍历跟节点4的右子树 再从右子树的根节点6开始遍历根节点6遍历之后又开始遍历根节点6的左子树 但是根节点6的左子树为空于是路线直接返回到根节点6开始遍历根节点6的右子树 但是根节点6的右子树为空于是路线直接返回到根节点6此时根节点6所在的子树前序遍历已经完成所以路线直接返回到根节点4此时根节点4所在的子树前序遍历已经完成所以路线直接返回到根节点1此时根节点1所在的子树前序遍历已经完成也就是整棵树的前序遍历已经完成了。 根据上述遍历过程当遍历时遇到空时过程会返回子树的前序遍历完成之后过程会返回。根据此思路将其实现可得如下递归代码 void PreOrderTraversal(BTNode* root) {if (NULL root){printf(# );//打印“#”代表节点为空return;}printf(%d , root-data);PreOrderTraversal(root-left);PreOrderTraversal(root-right); }根据函数调用的次序过程尝试画出其调用路线如下(红色代表递归调用绿色代表调用返回“#”代表子树为空)
   2.1.2 中序遍历、后序遍历 同理 根据中序遍历先左子树再根节点再右子树 和后序遍历先左子树再右子树在根节点 的遍历过程(不再赘述文字) 将其实现可分别得到如下递归代码和调用路线图 //中序遍历 void InOrderTraversal(BTNode* root) {if (NULL root){printf(# );return;}InOrderTraversal(root-left);//先左子树printf(%d , root-data);//再根节点InOrderTraversal(root-right);//再右子树 }//后序遍历 void PostOrderTraversal(BTNode* root) {if (NULL root){printf(# );return;}PostOrderTraversal(root-left);//先左子树PostOrderTraversal(root-right);//再右子树printf(%d , root-data);//再根节点 }根据以上对于前中后序的递归遍历我们可以打印出遍历结果分别如下 前序遍历1 2 3 # # # 4 5 # # 6 # # 中序遍历# 3 # 2 # 1 # 5 # 4 # 6 # 后序遍历# # 3 # 2 # # 5 # # 6 4 1 这里可以告诉大家一种取巧的方法来判断给定一棵树的前中后序遍历结果 如图所示 先画图将空节点补全再从根节点左边开始沿着树的结构画出如图所示的蓝色路线图。 前序遍历的结果就是沿着路线图标记的红色结果每一个标记都在节点的左边 中序遍历的结果就是沿着路线图标记的绿色结果每一个标记都在节点的下边 前序遍历的结果就是沿着路线图标记的黄色结果每一个标记都在节点的右边。 2.2 题目练习 了解了这些遍历方式之后我们可以来看几个题。 2.2.1 求一棵二叉树的节点个数 首先要从二叉树的概念入手。要求一棵二叉树的节点个数无非就是求二叉树的根节点个数左子树的节点个数右子树的节点个数。如果遇到空树就不是真的节点返回0即可。但是根节点的话不能直接返回要先求出左子树的节点个数右子树的节点个数然后再加上根节点的一个数量一齐返回才行。所以可以考虑到用后序遍历完成。 参考代码如下 int TreeSize(BTNode* root) {return NULL root ? 0 : TreeSize(root-left) TreeSize(root-right) 1; }其实也可以使用树的其它遍历方式来完成节点个数的统计。本思想就是额外定义一个计数的变量如count先初始化为0在遍历过程中每遍历到一个节点如果节点为空就返回不为空count就加1。遍历完成之后count中存放的数据就是该树的节点个数了。 这里给出前序遍历作为参考。 void TreeSize(BTNode* root) {if (NULL root){return;}count;TreeSize(root-left);TreeSize(root-right); }2.2.2 求一棵二叉树的叶节点个数 首先要知道的是叶节点就是指左右子树都为空的节点。还是从二叉树的概念入手要求一棵二叉树的叶节点个数可以分三种情况考虑。 如果根节点为空就是该树没有节点也就是没有叶节点返回0即可。 如果根节点是叶节点就是该树只有一个叶节点返回1即可。 如果根节点不是叶节点那叶节点就只存在于根节点的左右子树中那就去对根节点的左右子树去进行叶节点的计算然后返回左右子树中的叶节点的加和即可。 根据上述思路可以给出参考代码如下 int TreeLeafSize(BTNode* root) {if (NULL root){return 0;}return NULL root-left NULL root-right ? 1 : TreeLeafSize(root-left) TreeLeafSize(root-right); }对于叶节点个数的统计也可以像树的节点数的统计那样定义一个计数的变量count来完成思路和上述类似就不再赘述。 直接上代码 void TreeLeafSize2(BTNode* root) {if (NULL root){return;}if (NULL root-left NULL root-right){count;return;}TreeLeafSize(root-left);TreeLeafSize(root-right);}2.2.3 求一棵二叉树第k层节点的个数 前请说明这里以根节点的层数为第1层来考虑。 要求第k层的节点个数要知道这个k是相对于整棵树的根节点(也就是第1层)而言的。言外之意就是如果是相对第2层而言那要求的就变成了第k-1层的节点个数。如此递推下去就可以看做是求第1层的节点个数那第1层的节点个数自然是只有一个了(这也是函数递归的出口所在)。 根据上述思路可以给出如下参考代码 int TreeKLevel(BTNode* root, int k) {assert(k 1);//k要大于等于1才合法if (NULL root){//如果根节点为空整棵树中都没有节点第k层节点数自然为0return 0;}if (1 k){//递归出口return 1;}return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);}2.2.4 求一棵二叉树的深度 前请说明这里以根节点的层数为第1层来考虑。 从二叉树的概念入手。一棵二叉树的深度无非是根节点的深度加上左右子树深度更大者的深度。 鉴于此可以给出如下参考代码 int TreeDepth(BTNode* root) {if (NULL root){//如果根节点为空深度为0return 0;}int leftDepth TreeDepth(root-left);//左子树的深度计算int rightDepth TreeDepth(root-right);//右子树的深度计算//取深度较大者 根节点的深度(1)if (leftDepth rightDepth){return leftDepth 1;}else{return rightDepth 1;} }2.2.5 在一棵二叉树中查找值为x的节点 假设二叉树中每个节点的值都不一样找到了返回节点地址找不到返回NULL。 这一题还是从二叉树的概念入手要在一棵二叉树中寻找值为x的节点。那这个节点如果存在的话无非是存在于三个地方根节点中左子树中右子树中。这三个地方都没找到的话就返回NULL。 根据上述思路可以给出如下参考代码 BTNode* TreeFind(BTNode* root, BTDataType x) {if (NULL root){//根节点为空整棵树为空自然没有要找的节点。return NULL;}//先找根节点if (x root-data){return root;}//再找左子树BTNode* retLeft TreeFind(root-left, x);if (retLeft ! NULL){return retLeft;}//再找右子树BTNode* retRight TreeFind(root-right, x);if (retRight ! NULL){return retRight;}//都没找到返回NULLreturn NULL; }2.2.6 销毁一棵二叉树 从二叉树的概念入手。销毁一棵二叉树无非是销毁这棵二叉树的三个部分即根节点根节点的左子树根节点的右子树。但这里的销毁必须要遵循一定的顺序是不能先销毁根节点的。因为根节点如果首先被销毁了那根节点中所存储的左右子树中的根节点的地址就也被销毁了就无法找到左右子树所在的空间不能将其进行释放了。所以根节点的销毁需要在左右子树之后这正是所谓的后序遍历了。 鉴于此可以给出如下参考代码 void TreeDestroy(BTNode* root) {if (NULL root){return;}TreeDestroy(root-left);TreeDestroy(root-right);free(root); }对于以上题目的函数递归调用流程大家可以像二叉树的遍历一样多画图去分析调用和返回的执行路线那样可以帮助大家更好地理解和掌握。 2.3 二叉树的层序遍历 二叉树的前中后序遍历是属于深度优先方向上的遍历。而层序遍历是属于广度优先方向上的遍历。那下面就一起来看看层序遍历和之前的遍历有什么不同吧。 层序遍历 设二叉树的根节点所在层数为1。层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第3层上的节点以此类推自上而下自左至右逐层访问树的节点的过程就是层序遍历了。 广度优先搜索一般都会借助队列数据结构来完成这里下面也是使用队列来完成操作的。 但因为这里使用的是C语言所以还需要自己写一个队列做准备(如果使用的语言本身有符合队列性质的结构可以忽略)需要的小伙伴也可以从阿顺的这篇博文链式队列(C语言实现)获取。 好了既然有了队列该如何利用队列的各种性质操作来完成层序遍历呢 我们可以利用队列先进先出的性质来完成层序遍历的过程。 首先当树的根节点存在时层序遍历第一个遍历的肯定是根节点。将根节点的数据进行入队此时根节点的数据就入队完成了。 接下来该入树的第二层的数据了也就是2和4。那该如何将他们入队呢 可以知道的是他们是根节点的左右子树中的根节点所以根节点1中的左右指针域存放的有它们的地址可以通过根节点找到它们。然后将他们进行入队。但是要遵循先左子树后右子树的顺序进行入队。
   到第三层的数据入队了它们分别来自节点2为根的子节点和结点4为根的子节点。同样是通过上一层的节点中的指针域来找到它们进行入队并且要遵循先左子树后右子树的顺序。 好了到此树中的所有数据都入队了再将他们顺序出队就得到了层序遍历的结果了。 根据此思想可以给出如下参考代码 void LevelOrderTraversal(BTNode* root) {Queue q;QueueInit(q);//初始化队列//根节点存在就直接入队列//入的是结点的地址因为这样才能在后续通过指针域将其它节点入队if (NULL ! root){QueuePush(q, root);}while (!QueueEmpty(q)){//如果队列不为空执行以下操作//取队头元素BTNode* front QueueFront(q);//这里将队头元素交给front后直接出队头数据了和上面的图画的有出入//真实的过程在下图中QueuePop(q);printf(%d , front-data);if (NULL ! front-left){QueuePush(q, front-left);}if (NULL ! front-right){QueuePush(q, front-right);}}printf(\n);QueueDestroy(q); }在理解了上述层序遍历的过程下面趁热打铁就来看一道题。 2.4 题目练习 2.4.1 判断一棵二叉树是否是完全二叉树 是返回true不是返回false。 完全二叉树的概念这里就不在赘述需要的小伙伴可以参考阿顺的这篇博文树与二叉树(概念篇)进行学习。 大家可以尝试画一画在将一棵二叉树的空节点也考虑入队的情况下一棵完全二叉树在入队后队列中的数据形态是什么样子的一棵非完全二叉树在入队后队列中的数据形态又是什么样子的。画过之后相信大家很快就会明白其中的意思了。 下面以该图为例带大家一起看看。 完全二叉树入队
   普通二叉树入队 可以发现完全二叉树入队后树的非空节点和空节点是“泾渭分明”的而普通二叉树的非空节点和空节点是“鱼龙混杂”的。 这就为我们判断一棵二叉树是完全二叉树还是普通二叉树提供了思路。 bool TreeComplete(BTNode* root) {Queue q;QueueInit(q);if (NULL ! root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front ! NULL){QueuePush(q, front-left);QueuePush(q, front-right);}else//forntNULL循环结束{break;}}while (!QueueEmpty(q)){//如果NULL后面还有非空节点就返回falseif (QueueFront(q) ! NULL){//队列销毁防止内存泄漏QueueDestroy(q);return false;}QueuePop(q);}//NULL后面不存在非空节点返回trueQueueDestroy(q);return true; }好了本文对于普通二叉树的讲解算是完结了。虽然费劲心机想写得大家能一遍看懂但感觉还是很难真的是写得有些精疲力尽了但最后还是希望能对大家的学习有一点点帮助吧。