什么是樹（Tree）

只有一個根節(jié)點，每個父節(jié)點下有一個或多個子節(jié)點，每個子節(jié)點之間(兄弟節(jié)點)不相連

 

 關于樹， 有三個概念：

高度（height）

節(jié)點的高度 = 節(jié)點到葉子節(jié)點的最長路徑（邊數(shù)）

數(shù)的高度 = 根節(jié)點的高度

深度（depth）

節(jié)點的深度 = 根節(jié)點到這個節(jié)點所經(jīng)歷的邊的個數(shù)

層（level）

節(jié)點的層數(shù) = 節(jié)點的深度 + 1

 

 

高度是從下往上度量，計數(shù)起點是0

深度是從上往下度量，計數(shù)起點是0

層數(shù)也是從上往下度量，計數(shù)起始點為1，也就是根節(jié)點的層數(shù)是1

 

二叉樹

二叉樹的每個節(jié)點最多有兩個子節(jié)點，分別是左子節(jié)點和右子節(jié)點。

滿二叉樹 除了葉子節(jié)點，每個節(jié)點都有兩個子節(jié)點

完全二叉樹 最后一層子節(jié)點靠左排列的叫做完全二叉樹，（要么左子節(jié)點和右子節(jié)點都有，要么只有左子節(jié)點并且左子節(jié)點后沒有葉子節(jié)點了）

 

 如何存儲二叉樹

二叉樹有兩種存方法。

 

 

 基于指針或引用的的二叉鏈式存儲??

每個節(jié)點有三個字段，分別保存節(jié)點數(shù)據(jù)和左右子節(jié)點的地址，只要得到根節(jié)點，就可以通過左右子節(jié)點的指針把整棵樹串聯(lián)起來

 

 

 

 基于數(shù)組的順序存儲??

把根節(jié)點存儲在下標i=1的位置上，左子節(jié)點存儲在2*i=2的位置，右子節(jié)點在2*i+1的位置。以此類推

也就是父節(jié)點 = i 左子節(jié)點 = i*2 右子節(jié)點 = i *2 +1

完全二叉樹是最省空間的一種二叉樹，用數(shù)組存儲只浪費一個頭結點0

 

二叉樹的遍歷

前序遍歷： 對于節(jié)點A，先打印A->再打印A的左子樹->再打印A的右子樹

中序遍歷：對于節(jié)點A，先打印節(jié)點A的左子樹->再打印A->再打印A的右子樹

后續(xù)遍歷：對于節(jié)點A，先打印節(jié)點A的左子樹->再打印A的右子樹->再打印A

也就是說，A節(jié)點在什么位置（前中后）它就是什么順序

實際上，前中后續(xù)遍歷二叉樹就是一個遞歸的過程

class TraversalBinaryTree:
    """
    前中后續(xù)遍歷二叉樹
    :return:
    """
    def __init__(self, tree):
        """
        tree 是以數(shù)組存儲的二叉樹
        """
        self.tree = tree

    def pre_order(self, n_index):
        """
        n: int 需要遍歷的節(jié)點位置
        前序遍歷
        :return:
        """
        if n_index < 0 or n_index > len(self.tree):
            print "over"
            return
        print self.tree[n_index]
        print self.pre_order(n_index*2)
        print self.pre_order(n_index*2 + 1)

    def in_order(self, n_index):
        """
        中序遍歷
        :param n_index:
        :return:
        """
        if n_index < 0 or n_index > len(self.tree):
            print "over"
            return
        print self.in_order(n_index*2)
        print self.tree[n_index]
        print self.in_order(n_index*2 + 1)

    def post_order(self, n_index):
        """
        后序遍歷
        :param n_index:
        :return:
        """
        if n_index < 0 or n_index > len(self.tree):
            print "over"
            return
        print self.post_order(n_index*2)
        print self.post_order(n_index*2 + 1)
        print self.post_order(n_index)