• 雙親(Parent)

• 孩子(Child)

• 兄弟(Sibling)

• 度(Degree)：節點所擁有子樹的數量

• 深度(Depth)

• 高度(Height)：樹的最大階度

雙親標記法

// |data|parent|
typedef struct PTNode {
    ElemType data;
    int parent;
} PTNode;

// PTNode array
typedef struct PTree {
    PTNode node[MAX_TREE_SIZE];
    int root, n; // 根的位置和節點數
} PTree;

問題：找Child要找整棵樹

-> 加長子欄位

問題：如果Child > 1，想知道兄弟之間的關係

-> 加右兄弟欄位

孩子標記法

// |child|child|child||...|next| 孩子節點
typedef struct CTNode {
    int child;
    struct CTNode *next;
} *ChildPtr;

// 表頭結構
typedef struct CTBox {
    ElemType data;
    ChildPtr firstchild;
} CTBox;

// CTBox array 樹結構
typedef struct CTree {
    CTBox nodes[MAX_TREE_SIZE];
    int r, n; // 根的位置和節點數
} CTree;

問題：找Parent要整棵樹

(加雙親欄位)

孩子兄弟標記法

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild, *rightsib;
} CSNode, *CSTree;

孩子兄弟標記法(first child 和 right sibling 皆是唯一的) -> 會把一棵樹變成二元樹(Binary Tree)

二元樹(Binary Tree)

• 每個節點最多兩個子樹
• 左子樹和右子樹是有順序的，不可任意顛倒

特性：

1. 第i階上，至多有2^(i-1)個節點
2. 深度為k的二元樹，至多有(2^k)-1個節點
3. 若終端節點數為n0，度為2的節點數為n2，則n0=n2+1(n=n0+n1+n2又分支線總數=n-1=n1+2*n2)
4. 具有n個節點的完整二元樹的深度為高斯(log2為底的n)+1
5. 對一棵完整二元樹編號後
   1. 若i=1，則為根節點；若i>1雙親為高斯(i/2)
   2. 若2*i>n，則i無左孩子
   3. 若2*i+1>n，則i無右孩子

完滿二元樹(Fully Binary Tree)：樹的節點數為2^n -1

完整二元樹(Complete Binary Tree)：

歪斜樹(Skewed Binary Tree)：完全沒有左節點或右節點

嚴格二元樹(Strictly Binary Tree)：每個非終端節點均有非空的左右子樹

順序儲存二元樹：深度為k，卻需要(2^k)-1個節點 -> 浪費空間

鏈結串列儲存二元樹：

// |lchild|data|rchild|
typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

走訪二元樹：

      A
     / \
    B   C
   /   / \
  D   E   F
 / \   \
G   H   I

• 前序走訪：拜訪根節點->前序走訪左子樹->前序走訪右子樹(ABDGHCEIF)
• 中序走訪：中序走訪左子樹->拜訪根節點->中序拜訪右子樹(GDHBAEICF)
• 後序走訪：從左到右，並從葉子節點後序走訪左子樹和右子樹->拜訪根節點(GHDBIEFCA)
• 階序走訪：從上而下逐階走訪，同一階中由左至右(ABCDEFGHI)

// 前序走訪
void PreOrderTraverse(BiTree T) {
    if (T == NULL)
        return;
    printf("%c", T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

// 中序走訪
void InOrderTraverse(BiTree T) {
    if (T == NULL)
        return;
    InOrderTraverse(T->lchild);
    printf("%c", T->data);
    InOrderTraverse(T->rchild);
}

// 後序走訪
void PostOrderTraverse(BiTree T) {
    if (T == NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c", T->data);
}

一定要有中序走訪+(前序走訪 or 後序走訪)才能唯一確定一棵二元樹

// 輸入為一個前序走訪的結果，若為NULL則輸入#
void CreateBiTree(BiTree *T) {
    ElemType ch;
    scanf("%c", &ch);
    if (ch == '#')
        *T = NULL;
    else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!*T)
            exit(OVERFLOW);
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

class treeNode:
    def __init__(self, data):
        self.data = 0
        self.left = None
        self.right = None

def create_tree(root, val):
    new_node = treeNode(val)

    if root is None:
        root = new_node
        return new_node
    else:
        cur = root
        while cur is not None:
            tmp = cur
            if cur.data > new_node.data:
                cur = cur.left
            elif cur.data < new_node.data:
                cur = cur.right
            else:
                print('Exist')
                return root
        if tmp.data > new_node.data:
            tmp.left = new_node
        elif tmp.data < new_node.data:
            tmp.right = new_node
    return root

問題1：只存左孩子和右孩子浪費空間

問題2：只知道左孩子和右孩子是誰，不知道前驅和後繼節點是誰

引線二元樹(Threaded Binary Tree)

右孩子指針為空則指向該節點在中序序列中的後繼，左孩子指針為空則指向該節點在中序序列的前驅

typedef enum {
    Link,
    Thread
} PointerTag;

typedef struct BiThrNode {
    ElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag;
    PointerTag RTag;
} BiThrNode, *BiThrTree;

// 中序走訪進行中序引線化，其實就是走訪的過程中修改空指標
BiThrTree pre = NULL;
void InThreading(BiThrTree p) {
    if (p) {
        InThreading(p->lchild);
        // 如果左孩子為空
        if (!p->lchild) {
            p->LTag = Thread;
            p->lchild = pre;
        }

        // 如果前驅節點的右孩子為空
        if (pre && !pre->rchild) {
            p->RTag = Thread;
            p->rchild = p;
        }
        pre = p;
        InThreading(p->rchild);
    }
}

// 走訪
// 走到最左下，如果右為Thread繼續走訪;如果是Link走到右繼續
int InOrderTraverse_Thr(BiThrTree T) {
    BiThrTree p;
    p = T->lchild;
    while (p != T) {
        while (p->LTag == Link)
            p = p->lchild;
        printf("%c", p->data);
        while (p->RTag == Thread && p->rchild != T) {
            p = p->rchild;
            printf("%c", p->data);
        }
        p = p->rchild;
    }
    return 0;
}

將樹轉換為二元樹：

1. 加線：所有兄弟節點之間加入連接線
2. 去線：保留某節點與第一個孩子的連結線，刪除與其他孩子的連線
3. 調整：第一個孩子為左節點，兄弟為右節點

將森林轉換為二元樹：

1. 把每棵樹轉換成二元樹
2. 第一棵二元樹不動，把後面一棵樹的根結點當作前一棵樹的右節點

將二元樹轉換為樹：

1. 加線：把左孩子的n個右節點當作此節點的孩子
2. 去線：刪除所有節點與其右孩子的連線
3. 調整

將二元樹轉換為森林：

1. 刪除根節點與右孩子的連線、右孩子的右孩子的連線...
2. 把所有二元樹轉為森林

霍夫曼樹(Huffman Tree)

加權路徑長度最小的二元樹

1. 把所有節點的權值由小到大排列
2. 取最小兩個值作為N1的子節點，N1的值為兩個節點的總和
3. 用N1代替最小兩個值插入並重新排列
4. 重複步驟2-3

霍夫曼編碼：將霍夫曼樹的左分支取代成0，右分支取代成1

平衡樹(Balanced Binary Tree)

左子樹和右子樹皆為高度平衡樹
|左子樹高度和右子樹高度差| <= 1

AVL樹、B樹皆為平衡樹的一種