python数据结构-树

树是数据结构中常用到的一种结构，其实现较栈和队稍为复杂一些。若树中的所有节点的孩子节点数量不超过2个，则该为一个二叉树。

树

“嵌套列表”表示树

2017080815021788582607.png 20170808150217857149175.png

myTree = ['a',   #root
      ['b',  #left subtree
       ['d' [], []],
       ['e' [], []] ],
      ['c',  #right subtree
       ['f' [], []],
       [] ]
     ]

myTree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]
print(myTree)
print('left subtree = ', myTree[1])
print('root = ', myTree[0])
print('right subtree = ', myTree[2])

树的根是myTree[0]，根的左子树是myTree[1]，和右子树是myTree[2]

二叉树

20170808150217865294242.png 20170808150217881617379.png 20170808150217917424511.png

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Created by xuehz on 2017/8/8

#二叉树

class Tree():
    def __init__(self, leftjd=0, rightjd=0, data =0):
        self.leftjd = leftjd
        self.rightjd = rightjd
        self.data = data

class Btree():
    def __init__(self, base = 0):
        self.base = base
    def empty(self):
        if self.base is 0:
            return True
        else:
            return False
    def qout(self, jd):
        """
        前序遍历 NLR 根左右
        :param jd:
        :return:
        """
        if jd == 0:
            return
        print jd.data
        self.qout(jd.leftjd) #递归调用
        self.qout(jd.rightjd)
    def mout(self,jd):
        """
        中序遍历 LNR 左根右
        :param jd:
        :return:
        """
        if jd == 0:
            return
        self.qout(jd.leftjd)
        print jd.data
        self.qout(jd.rightjd)

    def hout(self,jd):
        """
        后序遍历 LRN 左右根
        :param jd:
        :return:
        """
        if jd ==0:
            return
        self.qout(jd.leftjd)  # 递归调用
        self.qout(jd.rightjd)
        print jd.data

if __name__ == '__main__':
    dj1 = Tree(data=8)
    dj2 = Tree(data=9)
    base = Tree(dj1, dj2, 7)# 根节点
    x = Btree(base)
    x.qout(x.base)
    print '========'
    x.mout(x.base)
    print '========'
    x.hout(x.base)