python二叉樹

1. 樹的特征和定義

樹是一種重要的非線性資料結構，直覺地看，它是資料元素（在樹中稱為結點）按分支關系組織起來的結構，很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用，如在編譯源程式時，可用樹表示源程式的文法結構。又如在資料庫系統中，樹型結構也是資訊的重要組織形式之一。一切具有層次關系的問題都可用樹來描述。

樹(Tree)是元素的集合。我們先以比較直覺的方式介紹樹。下面的資料結構是一個樹：

樹有多個節點(node)，用以儲存元素。某些節點之間存在一定的關系，用連線表示，連線稱為邊(edge)。邊的上端節點稱為父節點，下端稱為子節點。樹像是一個不斷分叉的樹根。

每個節點可以有多個子節點(children)，而該節點是相應子節點的父節點(parent)。比如說，3,5是6的子節點，6是3,5的父節點；1,8,7是3的子節點,

3是1,8,7的父節點。樹有一個沒有父節點的節點，稱為根節點(root)，如圖中的6。沒有子節點的節點稱為葉節點(leaf)，比如圖中的1,8,9,5節點。從圖中還可以看到，上面的樹總共有4個層次，6位于第一層，9位于第四層。樹中節點的最大層次被稱為深度。也就是說，該樹的深度(depth)為4。

如果我們從節點3開始向下看，而忽略其它部分。那麼我們看到的是一個以節點3為根節點的樹：

三角形代表一棵樹

再進一步，如果我們定義孤立的一個節點也是一棵樹的話，原來的樹就可以表示為根節點和子樹(subtree)的關系:

上述觀察實際上給了我們一種嚴格的定義樹的方法：

1. 樹是元素的集合。
2. 該集合可以為空。這時樹中沒有元素，我們稱樹為空樹 (empty tree)。
3. 如果該集合不為空，那麼該集合有一個根節點，以及0個或者多個子樹。根節點與它的子樹的根節點用一個邊(edge)相連。

上面的第三點是以遞歸的方式來定義樹，也就是在定義樹的過程中使用了樹自身(子樹)。由于樹的遞歸特征，許多樹相關的操作也可以友善的使用遞歸實作。我們将在後面看到。

2. 樹的實作

樹的示意圖已經給出了樹的一種記憶體實作方式:

每個節點儲存元素和多個指向子節點的指針。然而，子節點數目是不确定的。一個父節點可能有大量的子節點，而另一個父節點可能隻有一個子節點，而樹的增删節點操作會讓子節點的數目發生進一步的變化。這種不确定性就可能帶來大量的記憶體相關操作，并且容易造成記憶體的浪費。

一種經典的實作方式如下:

3. 樹的記憶體實作

擁有同一父節點的兩個節點互為兄弟節點(sibling)。上圖的實作方式中，每個節點包含有一個指針指向第一個子節點，并有另一個指針指向它的下一個兄弟節點。這樣，我們就可以用統一的、确定的結構來表示每個節點。

計算機的檔案系統是樹的結構，比如Linux檔案管理背景知識中所介紹的。在UNIX的檔案系統中，每個檔案(檔案夾同樣是一種檔案)，都可以看做是一個節點。非檔案夾的檔案被儲存在葉節點。檔案夾中有指向父節點和子節點的指針(在UNIX中，檔案夾還包含一個指向自身的指針，這與我們上面見到的樹有所差別)。在git中，也有類似的樹狀結構，用以表達整個檔案系統的版本變化

4. 二叉樹：　

二叉樹是由n（n≥0）個結點組成的有限集合、每個結點最多有兩個子樹的有序樹。它或者是空集，或者是由一個根和稱為左、右子樹的兩個不相交的二叉樹組成。

特點：

（1）二叉樹是有序樹，即使隻有一個子樹，也必須區分左、右子樹；

（2）二叉樹的每個結點的度不能大于2，隻能取0、1、2三者之一；

（3）二叉樹中所有結點的形态有5種：空結點、無左右子樹的結點、隻有左子樹的結點、隻有右子樹的結點和具有左右子樹的結點。

二叉樹(binary)是一種特殊的樹。二叉樹的每個節點最多隻能有2個子節點：

由于二叉樹的子節點數目确定，是以可以直接采用上圖方式在記憶體中實作。每個節點有一個左子節點(left children)和右子節點(right children)。左子節點是左子樹的根節點，右子節點是右子樹的根節點。

如果我們給二叉樹加一個額外的條件，就可以得到一種被稱作二叉搜尋樹(binary search tree)的特殊二叉樹。二叉搜尋樹要求：每個節點都不比它左子樹的任意元素小，而且不比它的右子樹的任意元素大。

(如果我們假設樹中沒有重複的元素，那麼上述要求可以寫成：每個節點比它左子樹的任意節點大，而且比它右子樹的任意節點小)

二叉搜尋樹，注意樹中元素的大小

二叉搜尋樹可以友善的實作搜尋算法。在搜尋元素x的時候，我們可以将x和根節點比較:

1. 如果x等于根節點，那麼找到x，停止搜尋 (終止條件)
2. 如果x小于根節點，那麼搜尋左子樹
3. 如果x大于根節點，那麼搜尋右子樹

二叉搜尋樹所需要進行的操作次數最多與樹的深度相等。n個節點的二叉搜尋樹的深度最多為n，最少為log(n)。

5. 二叉樹的周遊

周遊即将樹的所有結點通路且僅通路一次。按照根節點位置的不同分為前序周遊，中序周遊，後序周遊。

前序周遊：根節點->左子樹->右子樹

中序周遊：左子樹->根節點->右子樹

後序周遊：左子樹->右子樹->根節點

例如：求下面樹的三種周遊

前序周遊：abdefgc

中序周遊：debgfac

後序周遊：edgfbca

6. 二叉樹的類型

二叉樹類型

(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，并且葉子結點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。

(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（差別于AVL算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹

如何判斷一棵樹是完全二叉樹？按照定義，

教材上的說法：一個深度為k，節點個數為 2^k - 1 的二叉樹為滿二叉樹。這個概念很好了解，

就是一棵樹，深度為k，并且沒有空位。

首先對滿二叉樹按照廣度優先周遊（從左到右）的順序進行編号。

一顆深度為k二叉樹，有n個節點，然後，也對這棵樹進行編号，如果所有的編号都和滿二叉樹對應，那麼這棵樹是完全二叉樹。

（b）左邊的圖 左子數的高度為3，右子樹的高度為1，相差超過1

（b）右邊的圖 -2的左子樹高度為0 右子樹的高度為2，相差超過1

7. 二叉樹周遊實作

class TreeNode(object):
    def __init__(self,data=0,left=0,right=0):
        self.data = data
        self.left = left
        self.right = right

class BTree(object):
    def __init__(self,root=0):
        self.root = root


    def preOrder(self,treenode):
        if treenode is 0:
            return
        print(treenode.data)
        self.preOrder(treenode.left)
        self.preOrder(treenode.right)
    def inOrder(self,treenode):
        if treenode is 0:
            return
        self.inOrder(treenode.left)
        print(treenode.data)
        self.inOrder(treenode.right)

    def postOrder(self,treenode):
        if treenode is 0:
            return
        self.postOrder(treenode.left)
        self.postOrder(treenode.right)
        print(treenode.data)
if __name__ == '__main__':
    n1  = TreeNode(data=1)
    n2 = TreeNode(2,n1,0)
    n3 = TreeNode(3)
    n4 = TreeNode(4)
    n5 = TreeNode(5,n3,n4)
    n6 = TreeNode(6,n2,n5)
    n7 = TreeNode(7,n6,0)
    n8 = TreeNode(8)
    root = TreeNode('root',n7,n8)

    bt = BTree(root)
    print("preOrder".center(50,'-'))
    print(bt.preOrder(bt.root))

    print("inOrder".center(50,'-'))
    print (bt.inOrder(bt.root))

    print("postOrder".center(50,'-'))
    print (bt.postOrder(bt.root))