迪三
0%

二叉树&相关算法

发表于 分类于 Valine：

python实战基础《数据结构和算法》

类实现

  • 定义类
1
2
3
4
5
6
7
8
9
10
11
class Node():
    def __init__(self,left=None,right=Node,data=0):
        self.left=left
        self.right=right
        self.data=data
        
class Tree():
    def __init__(self,root=0):
        self.root=root
  • 生产一个二叉树
1
2
3
4
5
6
7
8
9
10
11
n1=Node(data=1)
n2=Node(n1,None,2) //左儿子n1，右没有儿子n2
n3=Node(data=3)
n4=Node(data=4)
n5=Node(n3,n4,5)
n6=Node(n2,n5,6)
n7=Node(n6,None,7)
n8=Node(data=8)
root=Node(n7,n8,'root')

bt=Tree(root)
  • 生成二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class BTree():

    def __init__(self, root=0):
        self.root = root

    def is_empty(self):
        if self.root is None:
            return True
        else:
            return False

    def create(self):
        temp = input('enter a value:')
        if temp is '#':
            return 0
        treenode = Node(data=temp)
        if self.root is None:
            self.root = treenode

        treenode.left = self.create()
        treenode.right = self.create()

二叉树的遍历

  • 前序遍历（根-左-右）
    a.递归
    1
    2
    3
    4
    5
    6
    def pre_order(tree):
        if tree==None:
            return 0
        print(tree.data)
        pre_order(tree.left)
        pre_order(tree.right）
    b.用栈
1
2
3
4
5
6
7
8
9
10
11
12
13
def front_stack(tree):
       """利用堆栈实现树的先序遍历"""
       if tree == None:
           return
       myStack = []
       node = tree
       while node or myStack:
           while node:                     #从根节点开始，一直找它的左子树
               pre(node.date),
               myStack.append(node)
               node = node.lchild
           node = myStack.pop()            #while结束表示当前节点node为空，即前一个节点没有左子树了
           node = node.rchild