Python如何实现二叉树的层序建立-创新互联
这篇文章将为大家详细讲解有关Python如何实现二叉树的层序建立，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
树节点定义
代码来
class BSTreeNode(object): def __init__(self, data): self.val = data self.leftChild = None self.rightChild = None
这一段代码太好理解了好吧，就不BB了。
二叉树层序建立
不多说，先上代码
# 建立二叉树是以层序遍历方式输入，节点不存在时以 'None' 表示 def creatTree(nodeList): if nodeList[0] == None: return None head = BSTreeNode(nodeList[0]) Nodes = [head] j = 1 for node in Nodes: if node != None: node.leftChild = (BSTreeNode(nodeList[j]) if nodeList[j] != None else None) Nodes.append(node.leftChild) j += 1 if j == len(nodeList): return head node.rightChild = (BSTreeNode(nodeList[j])if nodeList[j] != None else None) j += 1 Nodes.append(node.rightChild) if j == len(nodeList): return head
creatTree即为层序建立二叉树的函数，传入的参数为一个层序遍历的数组，就是将树节点从左往右，从上往下一次放入数组中，如果某个节点不存在则用None来表示。
比如：
图所示的二叉树则需输入a = [1,2,3,4,5,None,6,None,None,7,8]，接下来将会以这个二叉树为例讲解代码。
第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行，为节点添加右节点，与添加左节点的逻辑是一样的，就不在赘述了
好了代码注释完毕，我们再通过结合实例来解释一下：
nodeList = [1,2,3,4,5,None,6,None,None,7,8],下面节点统一用n(值)来表示
建立根节点 head = n(1), j=1, len(nodeList) = 11
开始for循环：Nodes = [n(1)]
nodeList[j]=nodeList[9]=7 非空，所以新建节点n(7),n(5)的左节点即为n(7),新建节点放入Nodes, 则Nodes=[n(1),n(2)，n(3),n(4),n(5),None,n(6),None，None，n(9)] j+1=10, j未溢出
nodeList[j]=nodeList[10]=8 非空，所以新建节点n(8),n(5)的右节点即为n(8),新建节点放入Nodes, 则Nodes=[n(1),n(2)，n(3),n(4),n(5),None,n(6),None，None，n(9)，n(10)] j+1=11, j溢出
nodeList[j]=nodeList[7]=None 为空，所以n(4)的左节点直接等于None,同时将None也放入Nodes, 则Nodes=[n(1),n(2)，n(3),n(4),n(5),None,n(6),None], j+1=8, j未溢出
nodeList[j]=nodeList[8]=None 为空，所以n(4)的右节点直接等于None,同时将None也放入Nodes, 则Nodes=[n(1),n(2)，n(3),n(4),n(5),None,n(6),None，None], j+1=9, j未溢出
nodeList[j]=nodeList[5]=None 为空，所以n(3)的左节点直接等于None, 同时将None也放入Nodes, 则Nodes=[n(1),n(2)，n(3),n(4),n(5),None] j+1=6, j未溢出
nodeList[j]=nodeList[6]=6 非空，所以新建节点n(6),n(3)的右节点即为n(6),新建节点放入Nodes, 则Nodes=[n(1),n(2)，n(3),n(4),n(5),None,n(6)], j+1=7, j未溢出
nodeList[j]=nodeList[3]=4 非空，所以新建节点n(4),n(2)的左节点即为n(4),新建节点放入Nodes, 则Nodes=[n(1),n(2),n(3),n(4)], j+1=4, j未溢出
nodeList[j]=nodeList[4]=5 非空，所以新建节点n(5),n(2)的右节点即为n(5),新建节点放入Nodes, 则Nodes=[n(1),n(2)，n(3),n(4),n(5)], j+1=5, j未溢出
nodeList[j]=nodeList[1]=2 非空，所以新建节点n(2),n(1)的左节点即为n(2),新建节点放入Nodes, 则Nodes=[n(1),n(2)] j+1=2, j未溢出
nodeList[j]=nodeList[2]=3 非空，所以新建节点n(3),n(1)的右节点即为n(3),新建节点放入Nodes, 则Nodes=[n(1),n(2),n(3)], 然后j+1=3, j未溢出
node为n(1)，非空
node为n(2)，非空
node为n(3)，非空
node为n(4),非空
node为n(5), 非空
j溢出，则返回head根节点，结束二叉树的建立
PS：如果node为空节点的话，就会直接跳过空节点。
二叉树遍历（神用的递归）
1. 前序遍历
#head为二叉树的根节点 def PreorderTraverse(head): if head: print(head.val) PreorderTraverse(head.leftChild) PreorderTraverse(head.rightChild)
2. 中序遍历
#head为二叉树的根节点 def InorderTrverse(head): if head: InorderTrverse(head.leftChild) print(head.val) InorderTrverse(head.rightChild)
3. 后续遍历
#head为二叉树的根节点 def PostorderTraverse(head): if head: PostorderTraverse(head.leftChild) PostorderTraverse(head.rightChild) print(head.val)
对中序遍历，费了我九牛二虎之力画了一个程序执行的图，红色箭头代表程序执行的过程，依然以a = [1,2,3,4,5,None,6,None,None,7,8]为例
这个图看上去不是很清楚，右键保存到本地看会清楚很多的，我把每一步递归的树都画出来了，这样更加方便理解。
所以程序打印出来的顺序为：4 2 7 5 8 1 3 6
关于“Python如何实现二叉树的层序建立”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网站栏目：Python如何实现二叉树的层序建立-创新互联
文章路径：http://azwzsj.com/article/pogjd.html
