二叉树的构建与遍历——python

二叉树的遍历与构建

• 二叉树的构建
• 二叉树的遍历

二叉树的构建

class BiTreeNode():  
    def __init__(self,data):  
        self.data = data  
        self.lchild = None  
 		self.rchild = None  
  
  
e = BiTreeNode('E')  
a = BiTreeNode('A')  
c = BiTreeNode('C')  
b = BiTreeNode('B')  
d = BiTreeNode('D')  
g = BiTreeNode('G')  
f = BiTreeNode('F')  
  
e.lchild = a  
e.rchild = g  
a.rchild = c  
c.lchild = b  
c.rchild = d  
g.rchild = f  
  
root = e  
  
# 打印C——root的左孩子的右孩子  
print(root.lchild.rchild.data)

二叉树的遍历

前序遍历

def pre_order(root):        # root为根节点  
 	if root:        		# 如果root不是空  
 		print(root.data,end=' ')  
        pre_order(root.lchild)  
        pre_order(root.rchild)  
  
  
pre_order(root)

中序遍历

def in_order(root):  
    if root:  
        in_order(root.lchild)  
        print(root.data, end=' ')  
        in_order(root.rchild)  
  
  
in_order(root)

后续遍历

def post_order(root):  
    if root:  
        post_order(root.lchild)  
        post_order(root.rchild)  
        print(root.data, end=' ')  
  
  
post_order(root)

层次遍历

from collections import deque  
  
  
def level_order(root):  
    queue = deque()  
    queue.append(root)  
    while len(queue) != 0:  
        x = queue.popleft()  
        print(x.data, end=' ')  
        if x.lchild:        # 一定要判断是否有，否则会将None也加入队  
 			queue.append(x.lchild)  
        if x.rchild:  
            queue.append(x.rchild)  
  
  
level_order(root)