python 实现数据结构 lesson 4 二叉树

一、二叉树的定义不再赘述，这里主要讨论的是生成二叉树的步骤和集中遍历方式。在这里，借鉴了几位大牛的遍历图形，

非常的深入简出，容易理解。

A. 前序遍历

B.中序遍历

python 实现数据结构 lesson 4 二叉树

C.后序遍历

python 实现数据结构 lesson 4 二叉树

以上三种方式，达成以下效果：

python 实现数据结构 lesson 4 二叉树

具体代码实现：

class Node(object):
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

class BinaryTree(object):
    def __init__(self):
        self.root = None

    def insert(self,data):
        node = Node(data)
        if self.root is None:
            self.root = node
        else:
            temp = [self.root]
            while True:#while temp行不行?
                p = temp.pop(0)
                if p.lchild is None:
                    p.lchild = node
                    return
                if p.rchild is None:
                    p.rchild = node
                    return
                temp.append(p.lchild)
                temp.append(p.rchild)

    def traverse(self):
        if self.root is None:
            return None
        temp = [self.root]
        data_list = []
        while len(temp)>0:#while len(tem) > 0: s
            cur = temp.pop(0)
            data_list.append(cur.data)
            if cur.lchild is not None:
                temp.append(cur.lchild)

            if cur.rchild is not None:
                temp.append(cur.rchild)

        print(data_list)

    def height(self,root):
        if self.root is None:
            return 0
        ldepth = self.height(root.lchild)
        rdepth = self.height(root.rchild)
        return max(ldepth,rdepth) + 1
    def depth(self,root):
        return self.height(root)-1

    def preorder(self,root):
        temp = []
        if root is None:
            return []
        temp.append(root.data)
        llist = self.preorder(root.lchild)
        rlist = self.preorder(root.rchild)
        return temp + llist + rlist

    def inorder(self,root):
        temp = []
        if root is None:
            return []
        llist = self.inorder(root.lchild)
        temp.append(root.data)
        rlist = self.inorder(root.rchild)
        return llist + temp + rlist

    def postorder(self,root):
        temp = []
        if root is None:
            return []
        llist = self.postorder(root.lchild)
        rlist = self.postorder(root.rchild)
        temp.append(root.data)
        return llist + rlist + temp

binary_tree = BinaryTree()
for i in range(1, 11):
    binary_tree.insert(i)
binary_tree.traverse()
print('*****preorder result*****')
print(binary_tree.preorder(binary_tree.root))

print('*****inorder result*****')
print(binary_tree.inorder(binary_tree.root))

print('*****postorder result*****')
print(binary_tree.postorder(binary_tree.root))

结论如下：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
*****preorder result*****
[1, 2, 4, 8, 9, 5, 10, 3, 6, 7]
*****inorder result*****
[8, 4, 9, 2, 10, 5, 1, 6, 3, 7]
*****postorder result*****
[8, 9, 4, 10, 5, 2, 6, 7, 3, 1]

Process finished with exit code 0

python 实现数据结构 lesson 4 二叉树

相关推荐