二叉树的Python实现

发布于 | 分类： .
字数统计

学了这么长时间的Python，可以尝试下二叉树的构建，作为练习。
树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前驱。

树的递归定义如下：

  • （1）至少有一个结点（称为根）
  • （2）其它是互不相交的子树

二叉树：

二叉树是由n（n≥0）个结点组成的有限集合、每个结点最多有两个子树的有序树。它或者是空集，或者是由一个根和称为左、右子树的两个不相交的二叉树组成。

特点：

  • （1）二叉树是有序树，即使只有一个子树，也必须区分左、右子树；
  • （2）二叉树的每个结点的度不能大于2，只能取0、1、2三者之一；
  • （3）二叉树中所有结点的形态有5种：空结点、无左右子树的结点、只有左子树的结点、只有右子树的结点和具有左右子树的结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
# coding:utf-8
"二叉树的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):
        self.root = Node()
        self.myQueue = []
    def addnodes(self,elem):
        """为树添加节点"""
        node = Node(elem)
        # 如果树是空的，就对根节点赋值
        if self.root.elem == -1:
            self.root = node
            self.myQueue.append(self.root)
        else:
            # 此时节点的子树还没有齐
            treeNode = self.myQueue[0]
            if treeNode.lchild == None:
                treeNode.lchild = node
                self.myQueue.append(treeNode.lchild)
            else:
                # 如果该节点存在右子树，将此节点丢弃
                treeNode.rchild = node
                self.myQueue.append(treeNode.rchild)
                self.myQueue.pop(0)
    # 接下来利用递归实现二叉树的先序遍历
    def front_digui(self, root):
        if root == None:
            return
        print(root.elem)
        # 递归遍历左子树
        self.front_digui(root.lchild)
        # 递归遍历右子树
        self.front_digui(root.rchild)
    #接下来递归方式实现二叉树的中序遍历，也就是按照左子树-根节点-右子树的顺序遍历 
    def middle_digui(self, root):
    	if root == None:
    		return
        # 遍历左子树
    	self.middle_digui(root.lchild)
        # 遍历根节点
    	print(root.elem)
        # 遍历右子树
    	self.middle_digui(root.rchild)
    #递归实现二叉树的后序遍历，按照左子树-右子树-根节点的顺序来遍历
    def postorder_digui(self,root):
    	if root == None:
    		return
        # 遍历左子树 
    	self.postorder_digui(root.lchild)
        # 遍历右子树
    	self.postorder_digui(root.rchild)
        # 遍历根节点
    	print(root.elem)
    # 用堆栈来实现二叉树的先序遍历
    def front_stack(self,root):
    	if root == None:
    		return 
    	myStack = []
    	node = root
    	while node or myStack:
    		while node:
    			print(node.elem)
    			myStack.append(node)
    			node = node.lchild
    		node = myStack.pop()
    		node = node.rchild
    # 用栈实现二叉树的中序遍历
    def middle_stack(self,root):
    	if root == None:
    		return 
    	myStack = []
    	node = root
    	while node or myStack:
    		while node:
    			myStack.append(node)
    			node = node.lchild
    		node = myStack.pop()
    		print(node.elem)
    		node = node.rchild
    # 用栈实现二叉树的后序遍历,这里用到了两个栈，mystack1先弹出根节点，再按照右子树-左子树的顺序存储，弹出的顺序就是根节点-右子树-左子树，所以mystack2的存入顺序也是根节点-右子树-左子树，弹出顺序就是左子树-右子树-根节点，实现了后序遍历。
    def postorder_stack(self,root):
    	if root == None:
    		return
    	myStack1 = []
    	myStack2 = []
    	node = root
    	myStack1.append(node)
    	while myStack1:
    		node = myStack1.pop()
    		if node.lchild:
    			myStack1.append(node.lchild)
    		if node.rchild:
    			myStack1.append(node.rchild)
    		myStack2.append(node)
    	while myStack2:
    		print(myStack2.pop().elem)
    # 用队列的形式实现二叉树的层次遍历，这个做法好聪明啊，每次只是pop(0)，就能按照层次一层一层地遍历。
    def level_queue(self,root):
    	if root == None:
    		return
    	myQueue = []
    	node = root
    	myQueue.append(node)
    	while myQueue:
    		node = myQueue.pop(0)
    		print(node.elem)
    		if node.lchild != None:
    			myQueue.append(node.lchild)
    		if node.rchild != None:
    			myQueue.append(node.rchild)
    			
if __name__ == '__main__':
    """主函数"""
    elems = range(10)
    tree = Tree()
    for elem in elems:
        tree.addnodes(elem)
    
    print("递归方式实现的二叉树的先序遍历")
    print(tree.front_digui(tree.root))
    print("递归方式实现二叉树的中序遍历")
    print(tree.middle_digui(tree.root))
    print("递归方式实现二叉树的后续遍历")
    print(tree.postorder_digui(tree.root))
    print("用栈实现二叉树的先序遍历")
    print(tree.front_stack(tree.root))
    print("用栈实现二叉树的中序遍历")
    print(tree.middle_stack(tree.root))
    print("用栈实现二叉树的后续遍历")
    print(tree.postorder_stack(tree.root))
    print("用队列实现二叉树的层次遍历")
    print(tree.level_queue(tree.root))

在python中有一对很神奇的函数，就是append和pop()，append的作用就是每次在列表后面添加进来一个值，而pop()函数可以指定列表的任何一个位置的元素弹出来，默认的是从后往前弹出，这样就相当于数据结构中的栈，还可以写个循环，指定每次都从列表最前面弹出元素，这样就相当于队。