做网站域名和空间费,跨境电商的现状及前景,建筑产业大数据综合服务平台,做网站怎么偷源码做网站目录
#x1f31e;0.前言
#x1f688;1.二叉树链式结构的代码是实现
#x1f688;2.二叉树的遍历及代码实现和深度刨析代码
#x1f69d;2.1前序遍历
✈️2.1.1前序遍历的理解
✈️2.1.2前序代码的实现
✈️2.1.3前序代码的深度解剖
#x1f69d;2.2中序遍历
✈…
目录
0.前言
1.二叉树链式结构的代码是实现
2.二叉树的遍历及代码实现和深度刨析代码
2.1前序遍历
✈️2.1.1前序遍历的理解
✈️2.1.2前序代码的实现
✈️2.1.3前序代码的深度解剖
2.2中序遍历
✈️2.2.1中序遍历的理解
✈️2.2.中序代码的实现
2.3后序遍历
✈️2.3.1后序遍历的理解
✈️2.3.2后序代码的实现
3.层序遍历 3.1层序遍历的代码实现
4.二叉树学习的相关建议和方法
✍5.结束语 0.前言
言C之言聊C之识以C会友共向远方。各位博友的各位你们好啊这里是持续分享数据结构知识的小赵同学今天要分享的数据结构知识是二叉树的前中后序和层序在这一章小赵将会向大家展开聊聊二叉树的前中后序和层序的相关知识。✊
1.二叉树链式结构的代码是实现
有了前面几篇博客的加持我们也算是对于二叉树有了清晰的认识在这样的情况下我们就可以尝试用链表去实现我们的二叉树了。
如这样一棵二叉树 我们该如何实现呢其实实现起来也容易就是创建每一个节点然后用手动把他们连起来其的操作方法和我们之前的链表很像。
typedef int treenode;
typedef struct BTNode
{int x;//本身存储的数据struct BTNode*left;//左孩子struct BTNode* right;//右孩子
}BTNode;BTNode* BuyNode(int a)//生成一个节点
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));//申请一个空间if (newnode NULL){perror(malloc failed);return;}newnode-left NULL;//先默认左右孩子为空newnode-right NULL;newnode-x a;return newnode;//返回节点
}
BTNode* CreateBT()
{BTNode* node1 BuyNode(5);//生成需要的节点BTNode* node2 BuyNode(6);BTNode* node3 BuyNode(7);BTNode* node4 BuyNode(1);BTNode* node5 BuyNode(3);BTNode* node6 BuyNode(8);BTNode* node7 BuyNode(5);node1-left node2;//将节点连起来node1-right node3;node2-left node4;node2-right node5;node3-left node6;node3-right node7;return node1;
}
int main()
{BTNode* phead CreateBT();}
这样我们就可以建立我们的链表了。 2.二叉树的遍历及代码实现和深度刨析代码
那我们有了一棵树现在我想遍历这个树的数据怎么办呢这个时候我们就提出了三种遍历方式叫前中后序遍历。
2.1前序遍历
✈️2.1.1前序遍历的理解
那么前序是怎么遍历的呢叫根左右什么叫做根左右呢就是先遍历一棵树的根部再遍历这棵树的左子树左子树遍历完了再遍历这棵树的右子树。 那么对于像我们这棵树的遍历顺序是什么呢如果用前序遍历的话是5613785
相信这个答案很多人会很惊讶为什么会是这样呢其实小赵一开始也是这样但只要一步步弄懂了就会觉得不难了。
首先我们遍历这棵树的根部就是5这个大家应该都没问题。 那么接下来我们要干嘛要遍历左子树对不对那我们就进入左子树进行遍历。这个时候的遍历方法其实就是把它的左子树单独看。 好了那么我们怎么遍历左子树呢还是那个方法啊先遍历根根是谁6那么5之后就是6。然后我们接着遍历这颗树的左子树又是根开始就是1那么6之后就是1。下面遍历1的左子树我们发现1的左子树没了那接着遍历右子数我们发现1的右子树也没了这个时候我们1这棵子树已经遍历完成了。我们发现对于6来说1的这棵左子树已经遍历完成了那就遍历6的右子数也就是3等到3也遍历完了那么6的左右子数就遍历完了对于最上面的5的根来说它的左子树就遍历完成了接着去遍历右子数还是按照我们遍历左子树的方法去进行遍历。 ✈️2.1.2前序代码的实现
void PreOrder(BTNode* root)
{if (rootNULL)//看这个节点是否是空节点{return;//是返回}printf(%d, root-x);//遇到根打印PreOrder(root-left);//遍历左子树PreOrder(root-right);//遍历右子树
} 看到这个代码的我的头一阵晕因为我怎么都无法想象一个这么大的遍历最后实现的代码会这么短。我也很难去进入到这个递归代码的里面去找寻原因后来我发现一个方面是我的对于深层次的递归可能脑子有点记不住前面的递归还有一个方面就是我不知道这个函数的返回问题。最终我也是在b站百度上找到了解决这个问题的办法这个办法就是递归展开图。
✈️2.1.3前序代码的深度解剖
什么叫递归展开图呢其实就是把隐藏的代码表示出来因为我们要无数次的重新进入这个函数那不如就把每一次的递归场景画出来。 这里呢小赵就演示了一下左子树的递归展开图的方式下面的中序后序也是一样的
所以下面小赵可能就不再进行这样的演示大家可以自行操作这个的操作软件就是我们电脑上都有的画图软件。 大家可以先将我们的代码截屏一下然后在画图软件里面用ctrlv就可以出现很多一样的图了。然后自己用上面的工具去操作还是非常好用的。
2.2中序遍历
✈️2.2.1中序遍历的理解
那么中序是怎么遍历的呢叫左根右什么叫做左根右呢相信大家也都猜出来了就是先遍历一棵树的左子树遍历完了左子树再遍历这棵树的根最后遍历右子树。
其实如果前序能理解这个也大差不差但是这里有一个点要注意其实和上面的前序遍历一样只有访问根才能接触到数据遍历其实是接触不到的。 例如这个图如果按中序先遍历左树5就不是第一个。而要遍历5的左子树。 那么其的访问方式其实和我们之前遍历是很像的我们一直遍历一棵树的左子树知道其中一棵的左子树遍历没了我们就开始访问这棵树的根节点这个时候对我们这个图来说就是1作为第一个数据 那么我们最后中序遍历的结果其实是1635875
✈️2.2.中序代码的实现
中序代码的实现
void InOrder(BTNode* root)
{if (root NULL)//看看这个节点是不是空节点{return;}InOrder(root-left);//遍历左子树printf(%d, root-x);//访问根节点InOrder(root-right);//遍历右子树
}
然后这个代码小赵也是非常推荐大家去按照小赵上面的方法去画递归展开图虽然初期递归展开图很费时间和经历但对于你去理解二叉树的前中后序是绝对非常有帮助的。
2.3后序遍历
✈️2.3.1后序遍历的理解
后序遍历就是左右根其实这个时候我们发现记忆前序中序和后序不难只需要想根节点的位置就行。 然后按这种方式遍历我们会发现最上面的5是最后遍历的其实相对于任何一棵树都是根是最后遍历的因为它必须先遍历左子树和右子树才能访问到根节点。’
然后后序遍历的结果是1368575
✈️2.3.2后序代码的实现
void PostOrder(BTNode* root)
{if (root NULL)//看看这个节点是不是空节点{return;}PostOrder(root-left);//遍历左子树PostOrder(root-right);//遍历右子树printf(%d, root-x);//访问根节点
}
这个也是一样要画画递归展开图。
3.层序遍历
之所以把层序遍历拿出来聊是因为我感觉这个东西和前面的前中后序还是不大一样正如它的名字所言它是一层一层遍历的在实现的方法上也不是我们之前的递归。
层序遍历的具体方式如下 ✈️✈️ 3.1层序遍历的代码实现 那么层序遍历主要使用的是什么方法呢其实是我们的队列为什么使用队列呢因为使用队列有一个好处就是先进先出我们可以让我们的根节点先进去然后根据根节点插入我们的左子树和右子树然后把根节点数据打印出来然后在进入下一个阶段左子树把下面两个带入自己出去。 那么按这样的顺序5出来后67就会进入6出去后13就会进入然后是7进入就可以完美的完成我们的遍历任务了。
因为这里要用到队列所以小赵就先把前面的代码拷了过来各位想要实现列表可以看看前面的文章数据结构c队列 http://t.csdnimg.cn/Px3yF 小赵在里面已经非常详细地说明了其的实现方法这里唯一要注意的是要把里面存的数据改成我们的节点。
typedef BTNode* QDataType;
void LevelOrder(Queue* Qphead, BTNode* BTphead)
{QueuePush(Qphead, BTphead);//将根节插入队列中while (!QueueEmpty(Qphead)){if (BTphead NULL){return;}QueuePush(Qphead, BTphead-left);//将根节点的左右子数插入队列QueuePush(Qphead, BTphead-right);int data BTphead-x;//拿到该节点的数据QueuePop(Qphead);//在队列中删除该节点printf(%d, data);//打印节点BTphead QueueFront(Qphead);//拿到下一个节点}
}
int main()
{BTNode* phead CreateBT();Queue* head (Queue*)malloc(sizeof(Queue));QueueInit(head);//初始化队列LevelOrder(head, phead);
}
层序遍历的代码会相对好懂一些。各位也可以进入代码中去研究想每一步是如何走的。 这里用我们的调试功能就能很清晰的知道自己的代码是如何运行的了。
4.二叉树学习的相关建议和方法
二叉树的学习对于整个编程的学习非常重要它联系着后面的红黑二叉树等相关知识也联系着我们的重要算法dfs,bfs在这一阶段我们要不断地去画递归展开图才能真正理解透彻这一段代码小赵在后面也会出一些与其相关的联系题帮助大家去理解。
这里小赵也是从网上找来了相关的动态图片去帮助大家理解。 ✍5.结束语
好了小赵今天的分享就到这里了如果大家有什么不明白的地方可以在小赵的下方留言哦同时如果小赵的博客中有什么地方不对也希望得到大家的指点谢谢各位家人们的支持。你们的支持是小赵创作的动力加油。 如果觉得文章对你有帮助的话还请点赞关注收藏支持小赵如有不足还请指点方便小赵及时改正感谢大家支持
