1. 樹的定義

特點(diǎn)： ① 層次化② 葉節(jié)點(diǎn)獨(dú)一性③ 不同節(jié)點(diǎn)的子節(jié)點(diǎn)相互獨(dú)立

2. 結(jié)構(gòu)：

1. 節(jié)點(diǎn)Node：節(jié)點(diǎn)具有名稱，也可以存儲數(shù)據(jù)
2. 邊Edge： 連接兩個節(jié)點(diǎn)，具有出入方向，表示節(jié)點(diǎn)之間的關(guān)系
3. Root根：沒有入邊的節(jié)點(diǎn)
4. Path路徑： 由邊連接的節(jié)點(diǎn)的有序列表
5. 子節(jié)點(diǎn)Childern、父節(jié)點(diǎn)、葉節(jié)點(diǎn)、兄弟節(jié)點(diǎn)、子樹
6. 層級： 從根節(jié)點(diǎn)到達(dá)一個節(jié)點(diǎn)路徑包括的邊的數(shù)量
7. 高度：所有節(jié)點(diǎn)的最大層級，根節(jié)點(diǎn)高度從0開始

3. 二叉樹

每個節(jié)點(diǎn)最多有兩個子節(jié)點(diǎn)

代碼實(shí)現(xiàn)：

# ————————樹的嵌套列表法————————
def BinaryTree(r):
    return [r, [], []]


def insertLeft(root, newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1, [newBranch, t, []])
        # 若存在左節(jié)點(diǎn)，則新插入左節(jié)點(diǎn)介于root與左節(jié)點(diǎn)中，原先的左節(jié)點(diǎn)為現(xiàn)在新插入節(jié)點(diǎn)的左節(jié)點(diǎn)
    else:
        root.insert(1, [newBranch, [], []])
    return root


def insertRight(root, newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2, [newBranch, [], t])
    else:
        root.insert(2, [newBranch, [], []])
    return root


def getRootVal(root):
    return root[0]


def setRootVal(root, new_val):
    root[0] = new_val


def getleftChildren(root):
    return root[1]


def getrightChildren(root):
    return root[2]


# ————————樹的節(jié)點(diǎn)鏈表法————————
class BinaryTree:
    def __init__(self,rootObj):
        self.val = rootObj
        self.left = None
        self.right = None

    def insertLeft(self, newNode):
        if self.left is None:
            self.left = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.left = self.left
            self.left = t

    def rightRight(self, newNode):
        if self.right is None:
            self.right = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.right = self.right
            self.right = t

    def getRight(self):
        return self.right

    def getLeft(self):
        return self.left

    def setRootVal(self, newval):
        self.val = newval

    def getRootVal(self):
        return self.val

附：大家可能都知道二叉樹中葉子節(jié)點(diǎn)（度為0）與度為2的節(jié)點(diǎn)數(shù)的關(guān)系為

度為2節(jié)點(diǎn)數(shù) = 葉子節(jié)點(diǎn)數(shù) - 1

但是知道為什么的人卻不多，下面就是這個定理的證明

樹（不僅僅是二叉樹）中每個節(jié)點(diǎn)頭上都有一個支路，但唯獨(dú)有一個是例外——根節(jié)點(diǎn)

所以我們可以得到樹的一個重要結(jié)論①：

樹支路總數(shù) = 樹節(jié)點(diǎn)總數(shù) - 1
支路總數(shù)怎么計算？

設(shè)度為 i 的節(jié)點(diǎn)有 xi 個，所以支路總數(shù)等于 Σ i * xi

二叉樹的度只有0，1，2

帶入重要結(jié)論①所以有：

0x0 + 1x1 + 2*x2 = x0 + x1 + x2 - 1

兩邊稍微計算一下得出：

x2 = x0 - 1