数据结构算法之二叉树

数据结构面试中经常会被问到篇二叉树相关的问题，那么这篇文章会研究下怎么用python来进行二叉树的构建和遍历。

注意：py2中

print root.elem,

在py3中要换成

print (root.elem,end="  ")

# coding:utf-8

# 定义节点类
class Node:
    def __init__(self,elem = -1,):
        self.elem = elem
        self.left = None
        self.right = None
        
# 定义二叉树
class Tree:
    def __init__(self):
        self.root = Node()
        self.myqu = []
    
    # 添加节点
    def add(self,elem):
        node = Node(elem)
        if self.root.elem == -1:         # 判断如果是根节点
            self.root  = node
            self.myqu.append(self.root)
        else:
            treenode = self.myqu[0]
            if treenode.left == None:
                treenode.left = node
                self.myqu.append(treenode.left)
            else:
                treenode.right = node
                self.myqu.append(treenode.right)
                self.myqu.pop(0)
        
    # 利用递归实现树的先序遍历
    def xianxu(self,root):
        if root == None:
            return
        print root.elem,
        self.xianxu(root.left)
        self.xianxu(root.right)
        
    # 利用递归实现树的中序遍历
    def zhongxu(self,root):
        if root == None:
            return 
        self.zhongxu(root.left)
        print root.elem,
        self.zhongxu(root.right)
        
    # 利用递归实现树的后序遍历
    def houxu(self,root):
        if root == None:
            return 
        self.houxu(root.left)
        self.houxu(root.right)
        print root.elem,
    
    # 利用队列实现层次遍历
    def cengci(self,root):
        if root == None:
            return
        myq = []
        node = root
        myq.append(node)
        while myq:
            node = myq.pop(0)
            print node.elem,
            if node.left != None:
                myq.append(node.left)
            if node.right != None:
                myq.append(node.right)
    
    # 求树的叶子节点
    def getYeJiedian(self,root):
        if root == None:
            return 0
        if root.left == None and root.right == None:
            return 1

        return self.getYeJiedian(root.left) + self.getYeJiedian(root.right)

    # 由先序和中序,还原二叉树
    def preMidToHou(self,pre,mid):
        if len(pre)==0:
            return None
        if len(pre)==1:
            Node(mid[0])
        root = Node(pre[0])
        root_index = mid.index(pre[0])
        root.left = self.preMidToHou(pre[1:root_index + 1],mid[:root_index])
        root.right = self.preMidToHou(pre[root_index + 1:],mid[root_index + 1:])
        return root

    # 由后序和中序,还原二叉树
    def preMidToHou(self,mid,hou):
        if len(hou)==0:
            return None
        if len(hou)==1:
            Node(mid[0])
        root = Node(hou[-1])
        root_index = mid.index(hou[-1])
        root.left = self.preMidToHou(mid[:root_index],hou[:root_index])
        root.right = self.preMidToHou(mid[root_index + 1:],mid[root_index + 1:])
        return root

# 创建一个树，添加节点
tree = Tree()
for i in range(10):
    tree.add(i)
    
print("二叉树的先序遍历:")
print(tree.xianxu(tree.root))

print("二叉树的中序遍历:")
print(tree.zhongxu(tree.root))

print("二叉树的后序遍历:")
print(tree.houxu(tree.root))

print("二叉树的层次遍历")
print(tree.cengci(tree.root))

print("\n二叉树的叶子节点为:")
print(tree.getYeJiedian(tree.root))

print("\n已知二叉树先序遍历和中序遍历，求后序:")
print("先序:")
print(tree.xianxu(tree.root))
print("中序:")
print(tree.zhongxu(tree.root))
print("后序:")
root = tree.preMidToHou([0,1,3,7,8,4,9,2,5,6],[7,3,8,1,9,4,0,5,2,6])
print(tree.houxu(root))

print("\n已知二叉树后序遍历和中序遍历，求前序:")
print("后序:")
print(tree.houxu(tree.root))
print("中序:")
print(tree.zhongxu(tree.root))
print("前序:")
root = tree.preMidToHou([7,3,8,1,9,4,0,5,2,6],[7,8,3,9,4,1,5,6,2,0])
print(tree.xianxu(root))

运行结果为：

二叉树的先序遍历:
0 1 3 7 8 4 9 2 5 6 None

二叉树的中序遍历:
7 3 8 1 9 4 0 5 2 6 None

二叉树的后序遍历:
7 8 3 9 4 1 5 6 2 0 None

二叉树的层次遍历
0 1 2 3 4 5 6 7 8 9 None

二叉树的叶子节点为:
5

已知二叉树先序遍历和中序遍历，求后序:
先序:
0  1  3  7  8  4  9  2  5  6  None
中序:
7  3  8  1  9  4  0  5  2  6  None
后序:
1  3  7  8  4  9  0  5  2  6  None

已知二叉树后序遍历和中序遍历，求前序:
后序:
7  8  3  9  4  1  5  6  2  0  None
中序:
7  3  8  1  9  4  0  5  2  6  None
前序:
0  1  3  7  8  4  9  6  2  5  None