昆山公司网站制作/天津百度推广代理商

二叉树:

　   根节点

　　左叶子节点

　　右叶子节点

　　子树

二叉树的遍历:

　　广度遍历(层级)    插入到第一次出现的空节点上面  

　　深度遍历:

　　　　前序(根左右)

　　　　中序(左根右)

　　　　后序(左右根)

# 广度遍历  
class Node():def __init__(self,item):self.item = itemself.left = Noneself.right = None
class Tree():def __init__(self):self.root = Nonedef add(self,item): node = Node(item)if self.root is None:self.root = nodereturn       queue = [self.root]  #列表  根节点 [1] while queue: cur = queue.pop(0)  #根节点    pop 1了if cur.left is None:  #子树左叶子空之后的赋值cur.left = nodereturnelse:queue.append(cur.left)  #不为空 就追加   [2]if cur.right is None:  #子树右叶子空之后的赋值cur.right = nodereturnelse:queue.append(cur.right)   #[2,3]def travel(self):   #遍历if self.root is None:returnqueue = [self.root]while queue:cur = queue.pop(0)print(cur.item)if cur.left is not None:queue.append(cur.left)if cur.right is not None:queue.append(cur.right)

tree = Tree()
for i in range(10):
tree.add(i)
tree.travel()

 

实现排序二叉树
class Node():def __init__(self,item):self.item = itemself.left = Noneself.right = None
class Tree():def __init__(self):self.root = Nonedef insertByOder(self,item):node = Node(item)if self.root is None:self.root = nodereturncur = self.rootwhile True:if item < cur.item:if cur.left is None:cur.left = nodereturnelse:cur = cur.leftelse:if cur.right is None:cur.right = nodereturnelse:cur = cur.rightdef forward(self,root):if root is None:return# 根 左 右print(root.item,end=' ')self.forward(root.left)self.forward(root.right)def mid(self,root):if root is None:return#左根右
        self.mid(root.left)print(root.item,end=' ')self.mid(root.right)def back(self,root):if root is None:return#左右根
        self.back(root.left)self.back(root.right)print(root.item,end=' ')t = Tree()
alist = [10,7,12,55,33,20,4]
for i in alist:t.insertByOder(i)t.forward(t.root)
print('\n')
t.mid(t.root)
print('\n')
t.back(t.root)
print('\n')