11-樹

一、樹

1.概念

• 樹是一種典型的非線性結構
• 特點：
  1. 每個節點都有零個或多個子節點
  2. 沒有父節點的節點稱為根節點
  3. 每一個非根節點都有且隻有一個父節點
  4. 除了根節點外，每個子節點都可以分為多個不相交的子樹

2.術語

• 節點的度：一個節點含有的子樹的個數稱為該節點的度；
• 樹的度：一棵樹中，最大的節點的度稱為樹的度；
• 葉節點或終端節點：度為零的節點；
• 父親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；
  • 孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；
• 兄弟節點：具有相同父節點的節點互稱為兄弟節點；
• 節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
• 樹的高度或深度：樹中節點的最大層次；
• 堂兄弟節點：父節點在同一層的節點互為堂兄弟；
• 節點的祖先：從根到該節點所經分支上的所有節點；
• 子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。
• 森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

3.樹的種類及存儲

1）樹的種類

• 無序樹：樹中任意節點的子節點之間沒有順序關系
• 有序樹：
  • 霍夫曼樹（用于資訊編碼）：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹
  • B樹：一種對讀寫操作進行優化的自平衡的二叉查找樹，能夠保持資料有序，擁有多于兩個的子樹

2）二叉樹

• 每個節點最多含有兩個子樹的樹稱為二叉樹
• 完全二叉樹：
  • 對于一顆二叉樹，假設其深度為d(d>1)。除了第d層外，其它各層的節點數目均已達最大值
  • 且第d層所有節點從左向右連續地緊密排列，這樣的二叉樹被稱為完全二叉樹
• 滿二叉樹的定義是所有葉節點都在最底層的完全二叉樹

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-4FgQ0Mnl-1604975476238)(C:\Users\lzq\AppData\Roaming\Typora\typora-user-images\image-20200908151247899.png)]

• 平衡二叉樹：當且僅當任意節點的子樹層數相差不大于1的二叉樹
• 排序二叉樹（二叉查找樹、有序二叉樹）：
  • 1.若左子樹不空，則左子樹上所有節點的值均小于它的根節點的值
  • 2.若右子樹不空，則右子樹上所有節點的值均大于它的根節點的值
  • 3.左、右子樹也分别為二叉排序樹

3）二叉樹的存儲

順序存儲：将資料結構存儲在固定的數組中

鍊式存儲：每個節點有一個元素域和兩個指針域

4.二叉樹的概念和性質

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-V6ZBT8Gg-1604975476239)(C:\Users\lzq\AppData\Roaming\Typora\typora-user-images\image-20200908155515486.png)]

二、二叉樹的周遊

1.二叉樹的代碼實作

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

        
class BinaryTree(object):
    """二叉樹類"""
    def __init__(self, node = None):
        self.root = node

    def add(self, item):
        """添加節點"""
        if self.root is None:
            self.root = None(item)
        # 定義對列
        queue = []
        # 從尾部添加資料
        queue.append(self.root)
        while True:
            node = queue.pop(0)
            # 判斷左節點是否為空
            if node.lchild is None:
                node.lchild = Node(item)
                return
            else:
                queue.append(node.lchild)
            # 判斷右節點是否為空
            if node.rchild is None:
                node.rchild = Node(item)
                return
            else:
                queue.append(node.rchild)

           

2.廣度優先周遊

def breadth_travel(self):
        """廣度優先周遊"""
        if self.root is None:
            return
        # 定義對列
        queue = []
        # 從尾部添加資料
        queue.append(self.root)
        while len(queue) > 0:
            node = queue.pop(0)
            print(node.item, end="")
            # 判斷左節點是否為空
            if node.lchild is not None:
                queue.append(node.lchild)
            # 判斷右節點是否為空
            if node.rchild is not None:
                queue.append(node.rchild)
           

3.深度優先周遊

先序：根 左 右

def preorder(self, root):
        """深度優先先序周遊"""
		if root is None:
			return
        print(root.item)
        self.preorder(root.lchild)
        self.preorder(root.rchild)
           

中序：左 根 右

def inorder(self, root):
        """深度優先中序周遊"""
        if root is None:
            return
        self.preorder(root.lchild)
        print(root.item)
        self.preorder(root.rchild)
           

後序：左 右 根

def postorder(self, root):
        """深度優先後序周遊"""
        if root is None:
            return
        self.preorder(root.lchild)
        self.preorder(root.rchild)
        print(root.item)
           

4.由周遊結果反推二叉樹

• 根據 中序周遊 和 先序周遊或後序周遊 來反推二叉樹

n

self.preorder(root.lchild)

self.preorder(root.rchild)

print(root.item)

## 4.由周遊結果反推二叉樹

- 根據 **中序周遊** 和 **先序周遊或後序周遊** 來反推二叉樹