python表示二叉树题目跪求大神帮忙

来源：蜘蛛抓取(WebSpider) 时间：2022-06-08 09:32 标签： 二叉树算法题汇总

二叉树(Binary Tree)时数据结构中一个非常重要的结构，其具有。。。。(此处省略好多字)。。。。等的优良特点。

之前在刷LeetCode的时候把有关树的题目全部跳过了，(ORZ：我这种连数据结构都不会的人刷j8Leetcode啊！！！)

所以 ！！！敲黑板了！！！今天我就在B站看了数据结构中关于树的内容后，又用我浅薄的Python大法来实现一些树的建立和遍历。

关于树的建立我觉得层序建立对于使用者来说最为直观，输入很好写。(好吧，我是看LeetCode中的树输入都是采用层序输入觉得非常好)

这一段代码太好理解了好吧，就不BB了。

1 #建立二叉树是以层序遍历方式输入，节点不存在时以 'None' 表示

creatTree即为层序建立二叉树的函数，传入的参数为一个层序遍历的数组，就是将树节点从左往右，从上往下一次放入数组中，如果某个节点不存在则用None来表示。

第3-4行，判断根节点是否为空。 如果根节点都为空，那树(shuo)就(ge)不(j)存(8)在了，直接返回就好了。

第5行，将元素列表中的第一个元素取出新建根节点，最后返回的即为根节点

第6行，创建了一个Nodes列表中，用于存放树中的节点，每生成一个节点就将其放入该列表中，可以看成是一个队列(这么说好像也不是特别规范，因为后面只是取列表中的元素，没有弹出首元素)，此处将根节点存入。

第7行，创建变量j用于nodeList中元素的索引，初始为1.因为第0个元素已经创建根节点了。

第8行，依次取出Nodes列表中的节点，对其创建左子节点和右子节点

第9行，首先判断取出的Nodes是否为空，如果为空，说明此处没有节点，就无需创建子节点，否则进行子节点的创建

第10行，为该节点创建左节点，其值就是索引j的所对应的值，如果nodeLists[j] == None 说明没有该子节点，就不用创建了，即Child = None

第11行，将新建的节点加入Nodes数组，使其在for循环中可以继续为其添加子节点

第12行，j加1，这样刚好使每一个nodeList的元素对应一个节点了

第13行，判断j的值，如果与nodeList值相等说明全部节点已经添加完毕了，直接返回head根节点就完成了树的建立

第15-19行，为节点添加右节点，与添加左节点的逻辑是一样的，就不在赘述了

好了代码注释完毕，我们再通过结合实例来解释一下：

j溢出，则返回head根节点，结束二叉树的建立

PS：如果node为空节点的话，就会直接跳过空节点。

二叉树遍历(神用的递归)

#head为二叉树的根节点

#head为二叉树的根节点

#head为二叉树的根节点

对中序遍历，费了我九牛二虎之力画了一个程序执行的图，红色箭头代表程序执行的过程，依然以a = [1,2,3,4,5,None,6,None,None,7,8]为例

这个图看上去不是很清楚，右键保存到本地看会清楚很多的，我把每一步递归的树都画出来了，这样更加方便理解。

最后，致敬大佬，祝各位学有所成。

【转载表明出处，谢谢】

我要回帖

更多关于 二叉树算法题汇总 的文章

 

随机推荐