一、二叉樹的基本概念

二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree） 和“右子樹”（right subtree）。

---

二、二叉樹的性質(特性)

性質 1: 在二叉樹的第 i 層上至多有 2^(i-1)個節點（i>0）

性質 2: 深度為 k 的二叉樹至多有 2^k - 1 個節點（k>0）

性質 3: 對于任意一棵二叉樹，如果其葉節點數為 N0，而度數為 2 的結點總數為 N2， 則 N0=N2+1;

性質 4:具有 n 個節點的完全二叉樹的深度必為 log2(n+1) (以2為底)

性質 5:對完全二叉樹，若從上至下、從左至右編號，則編號為 i 的結點，其左孩子編 號必為 2i，其右孩子編號必為 2i＋1；其雙親的編號必為 i/2（i＝1 時為根，除外）

---

三、二叉樹的節點及樹的創建

3.1、節點的創建

class Node(object): """節點類""" def __init__(self, elem=-1, lchild=None, rchild=None): self.elem = elem self.lchild = lchild self.rchild = rchild

---

3.2、樹的創建

class Tree(object):'''樹類'''def __init__(self):self.root = Nonedef add(self,elem):'''為樹添加結點'''node = Node(elem)if self.root is None:self.root = nodereturnqueue = [self.root]while queue:# 彈出隊列的第一個元素cur_node = queue.pop(0)if cur_node.lchild is None:cur_node.lchild = nodereturnelse:queue.append(cur_node.lchild)if cur_node.rchild is None:cur_node.rchild = Nonereturnelse:queue.append(cur_node.rchild)

---

四、二叉樹遍歷

樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結點的信息的訪問，即依次 對樹中每個結點訪問一次且僅訪問一次，我們把這種對所有節點的訪問稱為遍歷（traversal）。 那么樹的兩種重要的遍歷模式是深度優先遍歷和廣度優先遍歷，深度優先一般用遞歸，廣度優先一般用隊列。一般情況下能用遞歸實現的算法大部分也能用堆棧來實現。

4.1、廣度優先遍歷(層次遍歷)

從樹的 root 開始，從上到下從從左到右遍歷整個樹的節點。

代碼：

def breadth_travel(self):"""利用隊列實現樹的層次遍歷"""if self.root is None:returnqueue = [self.root]while queue:cur_node = queue.pop(0)print(cur_node.elem)if cur_node.lchild is not None:queue.append(cur_node.lchild)if cur_node.rchild is not None:queue.append(cur_node.rchild)

---

4.2、深度優先遍歷

對于一顆二叉樹，深度優先搜索(Depth First Search)是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。

那么深度遍歷有重要的三種方法。這三種方式常被用于訪問樹的節點，它們之間的不同 在于訪問每個節點的次序不同。這三種遍歷分別叫做先序遍歷（preorder），中序遍歷（inorder） 和后序遍歷（postorder）。我們來給出它們的詳細定義，然后舉例看看它們的應用。

補充小知識：
在已知中序遍歷和先序遍歷（或者中序遍歷和后序遍歷）結果時，我們可以推導出樹的結構（注意必須知道中序遍歷結果，否則是沒法推導的）

---

4.2.1、先序遍歷

在先序遍歷中，我們先訪問根節點，然后遞歸使用先序遍歷訪問左子樹，再遞歸使用先序遍歷訪問右子樹。

根節點 --> 左子樹 --> 右子樹

代碼：

def preorder(self,node):'''先序遍歷'''if node is None:returnprint(node.elem, end=' ')self.preorder(node.lchild)self.preorder(node.rchild)

---

4.2.2、中序遍歷

在中序遍歷中，我們遞歸使用中序遍歷訪問左子樹，然后訪問根節點，最后再遞 歸使用中序遍歷訪問右子樹。

左子樹 -->根節點 --> 右子樹

代碼：

def inorder(self,node):'''中序遍歷'''if node is None:returnself.inorder(node.lchild)print(node.elem, end=' ')self.inorder(node.rchild)

---

4.2.3、后序遍歷

在后序遍歷中，我們先遞歸使用后序遍歷訪問左子樹和右子樹，最后訪問根節點。

左子樹 --> 右子樹 --> 根節點

代碼：

def postorder(self,node):'''后序遍歷'''if node is None:returnself.postorder(node.lchild)self.postorder(node.rchild)print(node.elem, end=' ')

---

4.3、完整代碼遍歷測試

class Node(object):"""節點類"""def __init__(self, elem):self.elem = elemself.lchild = Noneself.rchild = Noneclass Tree(object):def __init__(self):self.root = Nonedef add(self,elem):'''為樹添加結點'''node = Node(elem)if self.root is None:self.root = nodereturnqueue = [self.root]while queue:# 彈出隊列的第一個元素cur_node = queue.pop(0)if cur_node.lchild is None:cur_node.lchild = nodereturnelse:queue.append(cur_node.lchild)if cur_node.rchild is None:cur_node.rchild = nodereturnelse:queue.append(cur_node.rchild)def preorder(self,node):'''先序遍歷'''if node is None:returnprint(node.elem, end=' ')self.preorder(node.lchild)self.preorder(node.rchild)def inorder(self,node):'''中序遍歷'''if node is None:returnself.inorder(node.lchild)print(node.elem, end=' ')self.inorder(node.rchild)def postorder(self,node):'''后序遍歷'''if node is None:returnself.postorder(node.lchild)self.postorder(node.rchild)print(node.elem, end=' ')def breadth_travel(self):"""利用隊列實現樹的層次遍歷"""if self.root is None:returnqueue = [self.root]while queue:cur_node = queue.pop(0)print(cur_node.elem,end=' ')if cur_node.lchild is not None:queue.append(cur_node.lchild)if cur_node.rchild is not None:queue.append(cur_node.rchild)if __name__ == '__main__':tree = Tree()for i in range(10):tree.add(i)tree.breadth_travel()print('')tree.preorder(tree.root)print('')tree.inorder(tree.root)print('')tree.postorder(tree.root)

遍歷結果：

層次：0 1 2 3 4 5 6 7 8 9 先序：0 1 3 7 8 4 9 2 5 6 中序：7 3 8 1 9 4 0 5 2 6 后序：7 8 3 9 4 1 5 6 2 0

總結

以上是生活随笔為你收集整理的数据结构与算法笔记（十四）—— 二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。