二叉树关键在构建和遍历，python实现相对简单，我们在实现需要用到类，分别设置爱左右子树，根节点，然后从根进行遍历，进行判断，若为空进行树的构建，非空则返回到列表中即可,我在进行遍历时产生了一个错误思想：把根放到树中遍历，这样发现遍历时会产生一个属性缺失的错误，后来浏览数次代码没有发现这个问题，查找了一些资料才意识到，短板：类运用的不熟练。
class Node(object):
def __init__(self, elem=-1, lchild=None, rchild=None):
self.elem=elem
self.lchild=lchild
self.rchild=rchild class Tree(object):
def __init__(self, root=None):
self.root = root
def add(self, elem):
node = Node(elem)
if self.root == None:
self.root=node
else:
queue=[]
queue.append(self.root)
while queue:
cur = queue.pop(0)
if cur.lchild == None:
cur.lchild=node
return
elif cur.rchild == None:
cur.rchild = node
return
else:
queue.append(cur.lchild)
queue.append(cur.rchild) #深度遍历进行三种三种遍历
def preorder(self, root):
"""递归实现先序遍历"""
if root == None:
return
print(root.elem)
self.preorder(root.lchild)
self.preorder(root.rchild) def inorder(self, root):
"""递归实现中序遍历"""
if root == None:
return
self.inorder(root.lchild)
print(root.elem)
self.inorder(root.rchild) def end(self, root):
""""""
if root == None:
return
self.end(root.lchild)
self.end(root.rchild)
print(root.elem)
#广度遍历
def rnf(self,root):
if self.root == None:
return
queue=[]
queue.append(root)
while queue:
cur_node=queue.pop(0)
print(cur_node.elem)
if cur_node.lchild != None:
queue.append(cur_node.lchild)
if cur_node.rchild != None:
queue.append(cur_node.rchild) if __name__ == '__main__':
tree=Tree()
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)
tree.add(7)
tree.add(8)
tree.add(9)
tree.rnf(tree.root)
tree.preorder(tree.root)
tree.inorder(tree.root)
tree.end(tree.root)