文章目錄

1.查找
- 1.1 靜態查找
- - 順序查找
  - 二分查找
  - - 二分查找演算法
2.樹的定義
3.樹的基本術語
4.樹的表示
5.二叉樹
- 二叉樹的定義
- 二叉樹的幾個重要性質
- 二叉樹基本操作
- 二叉樹的存盤結構
- - 順序存盤結構
  - 鏈式存盤
- 二叉樹遍歷
- - 先序遍歷
  - 中序遍歷
  - 后序遍歷
- 二叉樹的遞回遍歷
- 二叉樹的非遞回遍歷
- - 中序遍歷非遞回演算法
  - 先序遍歷非遞回演算法
  - 層序遍歷
- 遍歷二叉樹的應用
- - 由兩種遍歷序列確定二叉樹

1.查找

1.1 靜態查找

順序查找

順序查找演算法的時間復雜度為O(n)

二分查找

要查找的元素是存在的

要查找的元素是不存在的

二分查找演算法

2.樹的定義

怎么判定樹與非樹呢？

3.樹的基本術語

4.樹的表示

兒子-兄弟表示法

旋轉45度，就可以變成二叉樹了

5.二叉樹

二叉樹的定義

怎么判斷完美二叉樹和完全二叉樹呢？

一棵深度為k且有 2^k - 1 個結點的二叉樹稱為滿二叉樹(完美二叉樹)

分析：上圖中樹的深度是4，結點個數是 2^4 - 1 = 15

那么，將編號為15, 14, …, 9的葉子結點從右到左依次拿掉或者拿掉部分，則是一棵完全二叉樹,例如，將上圖中的編號為15, 14, 13, 12, 11葉子結點都拿掉(從右到左的順序)

下圖就不是一棵完全二叉樹

分析：如果將編號11(K)結點從編號6(E)的左兒子位置移動到編號5(E)的右兒子位置，則變成一棵完全二叉樹，

二叉樹的幾個重要性質

思考題：

有一顆二叉樹，其兩個兒子的結點個數為15個，一個兒子的結點個數為32個，問該二叉樹的葉結點個數是多少？

n2 = 15；n1 = 32;

n0 = n2 - 1 = 16

所以該二叉樹的葉結點個數是16

該二叉樹總共有 n0 + n1 + 2 * n2 = 0 + 32 + 30 = 62 條邊

也可以用 n0 + n1 + n2 = 63 表示該二叉樹的總結點樹，總邊數 = 總結點數 - 1 = 62

二叉樹基本操作

思考題

1、如果一個完全二叉樹最底下一層為第六層（根為第一層）且該層共有8個葉結點，那么該完全二叉樹共有多少個結點？

決議：

完全二叉樹，除最后一層可以不滿外，其他各層都必須是滿的

前五層的結點個數是：2^5 - 1 = 31

加上最后一層 8 個結點

總共是 31 + 8 = 39

2、若有一二叉樹的總結點數為98，只有一個兒子的結點數為48，則該樹的葉結點數是多少？

決議：這樣的樹是不存在的，二叉樹的總結點樹是n0 + n1 + n2 = 98，又因為n1 = 48，

所以n0 + n2 = 50，n0 = n2 - 1，代入得n2 = 51/2，故這樣的樹是不存在的

3、設深度為d（只有一個根結點時，d為1）的二叉樹只有度為0和2的結點，則此類二叉樹的結點數至少為2d-1？

決議：正確，考慮結點最少的情況：

可以看到，該樹每一級都只有一個節點有兩個子節點，深度為d，即除了第一級，其余每一級都有2個節點，故總共2d-1個節點，

二叉樹的存盤結構

順序存盤結構

鏈式存盤

二叉樹遍歷

先序遍歷

中序遍歷

后序遍歷

總結

二叉樹的遞回遍歷

void InorderTraversal( BinTree BT ) //中序遍歷
{
    if( BT ) {
        InorderTraversal( BT->Left );
        /* 此處假設對BT結點的訪問就是列印資料 */
        printf("%d ", BT->Data); /* 假設資料為整型 */
        InorderTraversal( BT->Right );
    }
}

void PreorderTraversal( BinTree BT ) //前序遍歷
{
    if( BT ) {
        printf("%d ", BT->Data );
        PreorderTraversal( BT->Left );
        PreorderTraversal( BT->Right );
    }
}

void PostorderTraversal( BinTree BT ) //后序遍歷
{
    if( BT ) {
        PostorderTraversal( BT->Left );
        PostorderTraversal( BT->Right );
        printf("%d ", BT->Data);
    }
}

void LevelorderTraversal ( BinTree BT )
{ 
    Queue Q; 
    BinTree T;

    if ( !BT ) return; /* 若是空樹則直接回傳 */
    
    Q = CreatQueue(); /* 創建空佇列Q */
    AddQ( Q, BT );
    while ( !IsEmpty(Q) ) {
        T = DeleteQ( Q );
        printf("%d ", T->Data); /* 訪問取出佇列的結點 */
        if ( T->Left )   AddQ( Q, T->Left );
        if ( T->Right )  AddQ( Q, T->Right );
    }
}

二叉樹的非遞回遍歷

基本思路：使用堆疊

中序遍歷非遞回演算法

先序遍歷非遞回演算法

無圖，直接上代碼

void InOrderTraversal(BinTree BT) {
    BinTree T = BT;
    Stack S = CreateStack(MaxSize);
    while (T || !IsEmpty(S)) { //如果二叉樹存在，并且堆疊不為空
        while (T) { //先列印該結點，并壓入堆疊，再向左一直遍歷
            printf("%5d", T->Data);
            Push(S, T);
            T = T->Left;
        }
        if (!IsEmpty(S)) {
            T = Pop(S); //將結點彈出堆疊
            T = T->Right; //將該結點向右遍歷
        }
    }
}

層序遍歷

遍歷二叉樹的應用

由兩種遍歷序列確定二叉樹

注意：必須要有中序遍歷，才能確定二叉樹

先由先序序列的第一個元素，確定根結點

再把根結點放到中序序列，確定左子樹有哪些元素

思考題

1、假定只有四個結點A、B、C、D的二叉樹，其前序遍歷序列為ABCD，則下面哪個序列是不可能的中序遍歷序列？

A、ABCD

B、ACDB

C、DCBA

D、DABC

決議：

選項A有可能：

選項B有可能：

選項C有可能：

選項D：首先根據中序，A在中間，所以左子樹的節點只有一個D，而右子樹節點是B和C，但問題是根據前序遍歷的規則，列印出A以后應該接著列印B，但是若D在左子樹，B在右子樹，則前序遍歷不可能先列印出B再列印出D，所以這種情況不可能，

2、對于二叉樹，如果其中序遍歷結果與前序遍歷結果一樣，那么可以斷定該二叉樹

決議：所有結點都沒有左兒子

3、已知一二叉樹的后序和中序遍歷的結果分別是FDEBGCA 和FDBEACG,那么該二叉樹的前序遍歷結果是什么？