本篇的主要内容：
- Python实现二叉树的建立与遍历
- 如何判断完全二叉树
最近遇到这个问题，要使用Python实现二叉树的一些操作，在网上这部分的资源不是很多，也没有找好很好的，只好按照自己的思路简单写了一下，本来算法是不局限于语言的，说是这么说，但是还是遇到了一些问题，在此梳理记录一下。
二叉树建立
首先定义二叉树的先序字符串，并使用#表示某个节点的子树为空的情况：
二叉树类的定义为：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
创建二叉树：
pos = 0
def create(seq):
global pos
ch = seq[pos]
pos += 1
if ch == '#':
return None
else:
temp = TreeNode(ch)
temp.left = create(seq)
temp.right = create(seq)
return temp
seq = "abd###ce###"
root = create(seq)
这里创建的二叉树形状为：
a
/ \
b c
/ /
d e
不过这里还要注意一个问题，在这里记录下来，提醒自己以后不要犯相同的错误，一开始我的创建树的代码是这样的：
def create(root):
global pos
if(seq[pos]=='#'):
root = None
pos += 1
return
root = TreeNode(seq[pos])
pos += 1
root.left = None
root.right = None
create(root.left)
create(root.right)
这个创建的思路是我在C++写树的时候也经常用的方式，这里与上面的方式有点不同，上面对于创建的树节点全都是return回去的，而这里则没有，在C++中，这样创建也是可以的，因为使用引用作为参数的时候，所有的操作都是在一块内存上进行的，但是Python中却不是，改变了对象，那么这个引用指向的地址也会改变，这样上面的函数中所有的操作相当于只是在函数内有效，而外层是记录不到这一系列创建树的操作的，这里请看（我的理解）。
主要的几种遍历方式
- 先序遍历、中序遍历以及后序遍历（这里使用递归方式，差别不大）
def pre_travel(root):
if root:
print(root.val, end=" ")
pre_travel(root.left)
pre_travel(root.right)
def in_travel(root):
if root:
in_travel(root.left)
print(root.val, end=" ")
in_travel(root.right)
def last_travel(root):
if root:
last_travel(root.left)
last_travel(root.right)
print(root.val, end=" ")
- 层次遍历（在C++中，实现层次遍历一般都会使用队列，在Python中队列这一数据结构直接使用列表就好了，pop对应的就是del(index)， push对应的就是append方法）
def level_travel(root):
que = []
if root is None:
print("None.")
return
else:
que.append(root)
while len(que) != 0:
temp = que[0]
print(temp.val, end=" ")
del(que[0])
if temp.left:
que.append(temp.left)
if temp.right:
que.append(temp.right)
关于判断一棵树是否为完全二叉树
这也是最近遇到的一个问题，在这里一块整理了：
首先要明确完全二叉树的概念，简单来说，就是二叉树的叶节点只出现在最下层和次下层，并且最下层的叶节点必须从左边依次出现，如果按照定义来进行判断，其实写起来还是有些麻烦的，主要是一些比较特殊的情况，判定条件不容易写，例如：
a
/ \
b c
/ /
d e
我是觉得这种类似的树不是很好加判断，所以不如直接不使用这些条件，换种角度，如果将树进行遍历，那么完全二叉树的所有结非空结点都会是相邻的，所以我们不如直接将所有的结点遍历出来，如果出现了空结点，但是空结点之后还有非空结点，那么就不是完全二叉树了，当然这个过程要在层次遍历中进行，代码如下：
def judge(root):
que = []
que.append(root)
while que[0] is not None: # 整体就是层次遍历，不同之处是要保存空结点 这里结束的时候说明遇到了空结点
que.append(que[0].left)
que.append(que[0].right)
del(que[0])
while len(que)!=0:
if que[0] is not None: # 既然之前遇到了空结点，说明下面所有的也必须都是空结点 如果遇到非空结点
return False #也就不是完全二叉树了
del(que[0])
return True
想到别的再进行补充。
以上~
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116713.html
