二叉樹二叉樹的性質存儲結構周遊二叉樹 C實作二叉樹的建立和周遊線索二叉樹

定義

二叉樹(binary tree)是n(n>=0)個結點的有限集合,該集合為空集合稱為空二叉樹,或者有一個根結點和兩棵互不相交的,分别稱為樹根結點的左孩子樹和右孩子樹組成.

二叉樹的特點

每個結點最多有兩棵子樹,是以二叉樹總沒有度大于2的結點

左子樹和右子樹是有順序的,次數不能任意颠倒

即使樹中某結點隻有一棵子樹,也要區分是左子樹還是右子樹

特殊的二叉樹

1. 斜樹

所有的結點都隻有左子樹的二叉樹稱為左斜樹;

所有的結點都隻有右子樹的二叉樹稱為右斜樹;

這兩者統稱為斜樹

2. 滿二叉樹

在一棵二叉樹中,如果所有的分支節點都存在左子樹和右子樹, 并且所有的葉子都在同一層上,這樣的二叉樹稱為滿二叉樹.

特點

葉子隻能出現在最下一層,出現在其它層就不可能達成平衡.

非葉子結點的度一定是2.

在同樣的深度的二叉樹中,滿二叉樹的結點個數最多,葉子數也最多.

3. 完全二叉樹

對一棵具有n個結點的二叉樹按層序編号,如果編号為i(1 <= i <= n)的結點與同樣深度的滿二叉樹中編号為i的結點在二叉樹中位置完全相同,則這棵二叉樹稱為完全二叉樹.

滿二叉樹一定是完全二叉樹, 但完全二叉樹不一定是滿二叉樹

特點

葉子結點隻能出現在最下兩層.

最下層的葉子一定集中在左部連續位置.

倒數二層,若有葉子節點,一定在右部連續位置

如果結點度為1,則結點隻有左孩子,即不存在隻有右子樹的情況

同樣結點數的二叉樹,完全二叉樹的深度最小

二叉樹的性質

性質1
在二叉樹的第i層上至多有 2^(i-1) 個結點(i>=1)
性質2
深度為k的二叉樹至多有 2^(k)-1 個結點(k>=1)
性質3

對任何一棵二叉樹T,如果其終端結點數的n0, 度為2的結點數為n2 則n0 = n2 + 1

樹T結點的總數為n=n0+n1+n2

分支結點數= n - 1 = n1 + 2*n2

性質4
具有n個結點的完全二叉樹的深度為└ log2^n ┘ + 1 (└ x ┘表示不大于x的最大整數)
性質5
如果對一棵有n個結點的完全二叉樹(其深度為 └ log2^n ┘ + 1 )結點按層序編号(從第1層到 └ log2^n ┘ + 1 層,每層從左到右)對任一結點i(1 <= i <=n)有

如果i=1,則結點i是二叉樹的根,無雙親;如果i>1,則其雙親結點是: └ i/2┘

如果2i>n,則結點i無左孩子(結點i為葉子結點);否則器左孩子是結點2i

如果2i+1>n,則結點i無右孩子,否則其右孩子是結點2i+1

二叉樹的存儲結構

1. 順序存儲結構

由于二叉樹的嚴格的定義可以采用一維數組存儲二叉樹中的結點,并且結點的存儲位置,也就是數組的下标要能提現結點之間的邏輯關系,比如雙親和孩子的關系,左右兄弟的關系等.

對于一般的二叉樹,盡管層序編号不能反映邏輯關系, 可把不存在的結點設定為^便可.

順序存儲結構一般隻用于完全二叉樹

2. 二叉連結清單

二叉樹每個結點做多有兩個孩子,是以他設計一個資料域和兩個指針域是比較自然的想法,我們稱這樣的連結清單為二叉連結清單.

左孩子指針域資料域右孩子指針域

lchild data rchild

左孩子指針域	資料域	右孩子指針域
lchild	data	rchild

周遊二叉樹

二叉樹的周遊是指(traversing binary tree): 從根結點出發,按照某種次序一次通路二叉樹中所有的結點,使得每個結點被通路一次且僅被通路一次.
1. 前序周遊

若二叉樹為空,則空操作傳回,否則先通路根結點,然後前序周遊左子樹,在前序周遊右子樹.

2. 中序周遊

若二叉樹為空,則空操作傳回,否則先從根結點開始(并不是先通路根結點),中序周遊根結點的左子樹,然後通路根結點,最後中序周遊右子樹.

3. 後序周遊

若二叉樹為空,則空操作傳回,否則先從左到右先葉子後結點的方式周遊通路左右子樹,最後是通路根結點.

4. 層序周遊

若二叉樹為空,則空操作傳回,否則先從樹的第一層,也就是從根結點開始通路,從上而下逐層通路,在同一層中,按從左到右的順序對結點逐個通路.
四種周遊方式,都是把樹中的結點變成某種意義的線性序列,給程式的實作帶來了好處

代碼實作二叉樹的建立和周遊

/*
    二叉樹(binary tree) - 鍊式存儲結構
    實作 二叉樹的建立和周遊
    周遊和建立分為三種 前序,中序,後序 
    輸入 資料參考 <AB D  C  > 空格是要輸入 的 
*/

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0;

typedef int Status;
typedef char TElemType;

//結點定義
typedef struct BiTNode {
    TElemType data;     //資料域 
    struct BiTNode *lchild, *rchild;    //左右孩子指針 
}BiTNode, *BiTree;

//前序周遊(previous order traverse)
void preOrderTraverse (BiTree T){
    if(T == NULL){
        return;
    } 
    printf("%c ", T->data);         //第一步 顯示結點資料
    preOrderTraverse(T->lchild);    //第二步 前序周遊左子樹 
    preOrderTraverse(T->rchild);        //第三步 前序周遊右子樹 
}

//中序周遊(intermediate order traverse)
void inOrderTraverse (BiTree T){
    if(T == NULL){
        return;
    } 
    inOrderTraverse(T->lchild); //第一步 中序周遊左子樹 
    printf("%c ", T->data);     //第二步 顯示結點資料
    inOrderTraverse(T->rchild); //第三步 中序周遊右子樹 
}

//後序周遊(post order traverse)
void postOrderTraverse(BiTree T){
    if(T == NULL){
        return;
    }
    postOrderTraverse(T->lchild);
    postOrderTraverse(T->rchild);
    printf("%c ", T->data);
} 

//二叉樹的建立  按前序輸入二叉樹中結點的值 (一個字元)
//' '表示空樹 讓每個結點确定是否有左右孩子,構造二叉連結清單表示二叉樹 
//如果輸入順序按中序或後序 , 代碼的66 67 68行順序要換一下 ,可以參照周遊的代碼這裡就不實作了. 
void createBiTree(BiTree *T){
    TElemType e;
    scanf("%c",&e);
    if(e == ' '){
        *T = NULL;
    } 
    else{
        *T = (BiTree)malloc(sizeof(BiTNode));   //生成結點 
        if(!(*T)){  //建立失敗 
            printf("結點申請失敗\n"); 
            return; 
        }
        (*T)->data = e; //給結點指派
        createBiTree(&(*T)->lchild); //構造左子樹
        createBiTree(&(*T)->rchild);    //構造右子樹 
    } 
}

int main(void){
    BiTree T;
    TElemType e;
    int option = ;
    printf("\n 1.前序建立二叉樹\n 2.前序周遊二叉樹\n 3.中序周遊二叉樹\n 4.後序周遊二叉樹\n 0.退出\n");
    while(option){
        scanf("%d", &option);
        fflush(stdin);  //重新整理緩沖區 這個是必須的 不然建立的時候輸入資料會讓你疑惑 
        switch(option){
            case :
                createBiTree(&T);
                printf("二叉樹建立成功\n");
                break;
            case :
                preOrderTraverse(T);
                break;
            case :
                inOrderTraverse(T);
                break;
            case :
                postOrderTraverse(T);
                break;
            case :
                return OK; 
        }
    } 
    return OK;
}

注意: 建立的時候 每個結點确定是否有左右孩子,如果沒有則用空格代替

缺點

浪費空間,有很多的空指針域 最多有n+1個空指針

二叉樹的建立和周遊都是遞歸的原理

建立是在原來的列印結點的地方,改成了生成節點,給結點指派的操作而已.

n個結點有2n個指針域,而n個結點的二叉樹一共有n-1條分支線,是以空指針域 = 2n-(n-1) = n+1

非遞歸周遊原理— 利用棧實作

1.前序

對于任一結點T：

1)通路結點T，并将結點T入棧;

2)判斷結點T的左孩子是否為空，若為空，則取棧頂結點并進行出棧操作，并将棧頂結點的右孩子置為目前的結點T，循環至1);若不為空，則将T的左孩子置為目前的結點T;

3)直到T為NULL并且棧為空，則周遊結束。

//前序周遊 -- 非遞歸實作 -- 利用棧實作 
void preOrderTraverse2 (BiTree T){
    stack<BiTree> s;    //初始化棧, 此時s 不為空的... 
    while(T != NULL || !s.empty()){ //棧為null并且目前結點也為null 退出循環 
        while(T != NULL){
            cout << T->data << " ";
            s.push(T);
            T = T->lchild;
        } 
        T = s.top();
        s.pop(); 
        T = T->rchild;
    }
}

2.中序

對于任一結點P，

1)若其左孩子不為空，則将T入棧并将P的左孩子置為目前的T，然後對目前結點T再進行相同的處理；

2)若其左孩子為空，則取棧頂元素并進行出棧操作，通路該棧頂結點，然後将目前的T置為棧頂結點的右孩子；

3)直到T為NULL并且棧為空則周遊結束

//中序周遊 -- 非遞歸周遊 -- 用棧實作 -- 和前序周遊的順序略有調整 
void inOrderTraverse2 (BiTree T){
    stack<BiTree> s;
    while(T != NULL || !s.empty()){ //目前結點為null 并且 棧為null時 退出循環 
        while(T != NULL) {
            s.push(T);
            T = T->lchild;
        }
        T = s.top();
        cout << T->data << " ";
        s.pop();
        T = T->rchild; 
    }
}

3.後序周遊

要保證根結點在左孩子和右孩子通路之後才能通路，是以對于任一結點T，先将其入棧。如果T不存在左孩子和右孩子，則可以直接通路它；或者T存在左孩子或者右孩子，但是其左孩子和右孩子都已被通路過了，則同樣可以直接通路該結點。若非上述兩種情況，則将T的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被通路，左孩子和右孩子都在根結點前面被通路。

//後序周遊(post order traverse) -- 先入右結點,後入左結點 
void postOrderTraverse2(BiTree T){
    stack<BiTree> s;
    s.push(T);
    BiTree cur; //目前通路的結點
    BiTree pre = NULL; //前一個通路的結點 
    while(!s.empty()){
        cur = s.top();
        //目前結點沒有左右結點 或者 孩子結點都已經被通路過了 -- 輸出目前的值 
        if((cur->lchild == NULL && cur->rchild == NULL)|| (pre != NULL && (pre == cur->lchild || pre == cur->rchild))) {
            cout << cur->data << " " ;
            s.pop();
            pre = cur;
        }else{
            //先入右結點
            if(cur->rchild != NULL){
                s.push(cur->rchild) ;
            } 
            if(cur->lchild != NULL){
                s.push(cur->lchild);
            }
        }
    }
}

全部代碼如下:

// 輸入 資料參考 <AB D  C  > 空格是要輸入 的 
//樹的非遞歸周遊 
#include <iostream>
#include <stack>
#include<stdlib.h>
using namespace std;

#define OK 1
#define ERROR 0;

typedef int Status;
typedef char TElemType;

//結點定義
typedef struct BiTNode {
    TElemType data;     //資料域 
    struct BiTNode *lchild, *rchild;    //左右孩子指針 
}BiTNode, *BiTree;

//前序周遊(previous order traverse) -- 遞歸實作 
void preOrderTraverse (BiTree T){
    if(T == NULL){
        return;
    } 
    cout << T->data << " ";          //第一步 顯示結點資料
    preOrderTraverse(T->lchild);    //第二步 前序周遊左子樹 
    preOrderTraverse(T->rchild);        //第三步 前序周遊右子樹 
}
//前序周遊 -- 非遞歸實作 -- 利用棧實作 
void preOrderTraverse2 (BiTree T){
    stack<BiTree> s;    //初始化棧, 此時s 不為空的... 
    while(T != NULL || !s.empty()){ //棧為null并且目前結點也為null 退出循環 
        while(T != NULL){
            cout << T->data << " ";
            s.push(T);
            T = T->lchild;
        } 
        T = s.top();
        s.pop(); 
        T = T->rchild;
    }
}
//中序周遊(intermediate order traverse)
void inOrderTraverse (BiTree T){
    if(T == NULL){
        return;
    } 
    inOrderTraverse(T->lchild); //第一步 中序周遊左子樹 
    cout << T->data << " ";     //第二步 顯示結點資料
    inOrderTraverse(T->rchild); //第三步 中序周遊右子樹 
}

//中序周遊 -- 非遞歸周遊 -- 用棧實作 -- 和前序周遊的順序略有調整 
void inOrderTraverse2 (BiTree T){
    stack<BiTree> s;
    while(T != NULL || !s.empty()){ //目前結點為null 并且 棧為null時 退出循環 
        while(T != NULL) {
            s.push(T);
            T = T->lchild;
        }
        T = s.top();
        cout << T->data << " ";
        s.pop();
        T = T->rchild; 
    }
}
//後序周遊(post order traverse)
void postOrderTraverse(BiTree T){
    if(T == NULL){
        return;
    }
    postOrderTraverse(T->lchild);
    postOrderTraverse(T->rchild);
    cout << T->data << " ";
} 

//後序周遊(post order traverse) -- 先入右結點,後入左結點 
void postOrderTraverse2(BiTree T){
    stack<BiTree> s;
    s.push(T);
    BiTree cur; //目前通路的結點
    BiTree pre = NULL; //前一個通路的結點 
    while(!s.empty()){
        cur = s.top();
        //目前結點沒有左右結點 或者 孩子結點都已經被通路過了 -- 輸出目前的值 
        if((cur->lchild == NULL && cur->rchild == NULL)|| (pre != NULL && (pre == cur->lchild || pre == cur->rchild))) {
            cout << cur->data << " " ;
            s.pop();
            pre = cur;
        }else{
            //先入右結點
            if(cur->rchild != NULL){
                s.push(cur->rchild) ;
            } 
            if(cur->lchild != NULL){
                s.push(cur->lchild);
            }
        }
    }
}

//二叉樹的建立  按前序輸入二叉樹中結點的值 (一個字元)
//' '表示空樹 讓每個結點确定是否有左右孩子,構造二叉連結清單表示二叉樹 
//如果輸入順序按中序或後序 , 代碼的66 67 68行順序要換一下 ,可以參照周遊的代碼這裡就不實作了. 
void createBiTree(BiTree *T){
    TElemType e;
    scanf("%c",&e);
    if(e == ' '){
        *T = NULL;
    } 
    else{
        *T = (BiTree)malloc(sizeof(BiTNode));   //生成結點 
        if(!(*T)){  //建立失敗 
            printf("結點申請失敗\n"); 
            return; 
        }
        (*T)->data = e; //給結點指派
        createBiTree(&(*T)->lchild); //構造左子樹
        createBiTree(&(*T)->rchild);    //構造右子樹 
    } 
}

int main(void){
    BiTree T = NULL;
    TElemType e;
    int option = ;
    cout << endl << "1.前序建立二叉樹" << endl << "2.前序周遊二叉樹" << endl << "3.中序周遊二叉樹" << endl << "4.後序周遊二叉樹";
    cout << endl << "0.退出" << endl;
    while(option){
        cin >> option;
        fflush(stdin);  //重新整理緩沖區 這個是必須的 不然建立的時候輸入資料會讓你疑惑 
        switch(option){
            case :
                createBiTree(&T);
                cout << "二叉樹建立成功" << endl;
                break;
            case :
                cout << endl << "遞歸周遊-- 前序周遊  的結果是:" << endl; 
                preOrderTraverse(T);
                cout << endl << "非遞歸周遊-- 前序周遊  的結果是:" << endl;
                preOrderTraverse2(T);
                cout<< endl; 
                break;
            case :
                cout << endl <<  "遞歸周遊-- 中序周遊  的結果是:" << endl; 
                inOrderTraverse(T);
                cout << endl <<  "非遞歸周遊-- 中序周遊  的結果是:" << endl;
                inOrderTraverse2(T);
                cout<< endl;
                break;
            case :
                cout << endl <<  "遞歸周遊-- 後序周遊  的結果是:" << endl; 
                postOrderTraverse(T);
                cout << endl <<  "非遞歸周遊-- 後序周遊  的結果是:" << endl;
                postOrderTraverse2(T);
                cout<< endl;
                break;
            case :
                return OK; 
            default:
                cout << endl << "1.前序建立二叉樹" << endl << "2.前序周遊二叉樹" << endl << "3.中序周遊二叉樹" << endl << "4.後序周遊二叉樹";
                cout << endl << "0.退出" << endl;
        }
    } 
    return OK;
}

線索二叉樹

指向前驅和後繼的指針稱為線索,加上線索的二叉連結清單稱為線索連結清單,相應的二叉樹就稱為線索二叉樹

為了解決二叉樹中空指針域浪費的問題将空指針利用起來,指向前驅和後繼這種思想稱為線索二叉樹

優點

便于查找結點

周遊二叉樹效率高

便于超找結點的前驅和後繼.

二叉樹二叉樹的性質存儲結構周遊二叉樹 C實作二叉樹的建立和周遊線索二叉樹

定義

二叉樹的特點

特殊的二叉樹

1. 斜樹

2. 滿二叉樹

3. 完全二叉樹

二叉樹的性質

二叉樹的存儲結構

1. 順序存儲結構

2. 二叉連結清單

周遊二叉樹

1. 前序周遊

2. 中序周遊

3. 後序周遊

4. 層序周遊

代碼實作二叉樹的建立和周遊

非遞歸周遊原理— 利用棧實作

線索二叉樹

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

二叉樹 二叉樹的性質 存儲結構 周遊二叉樹 C實作二叉樹的建立和周遊 線索二叉樹

定義

二叉樹的特點

特殊的二叉樹

1. 斜樹

2. 滿二叉樹

3. 完全二叉樹

二叉樹的性質

二叉樹的存儲結構

1. 順序存儲結構

2. 二叉連結清單

周遊二叉樹

1. 前序周遊

2. 中序周遊

3. 後序周遊

4. 層序周遊

代碼實作二叉樹的建立和周遊

非遞歸周遊原理— 利用棧實作

線索二叉樹

繼續閱讀

二叉樹二叉樹的性質存儲結構周遊二叉樹 C實作二叉樹的建立和周遊線索二叉樹