【我的算法筆記】二叉樹的創(chuàng)建、二叉樹的遍歷（遞歸、非遞歸）-創(chuàng)新互聯(lián)

創(chuàng)新互聯(lián)建站于2013年創(chuàng)立，先為肅北等服務(wù)建站，肅北等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為肅北企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

• 目錄

  文章目錄

  前言

  樹的結(jié)構(gòu)體定義

  二叉樹的創(chuàng)建（先序遞歸）?

  二叉樹的先序遍歷（遞歸）

  二叉樹的中序遍歷（遞歸）?

  二叉樹的后序遍歷（遞歸）

  二叉樹的先序非遞歸遍歷算法1

  二叉樹的先序非遞歸遍歷算法2

  二叉樹的中序非遞歸算法

  二叉樹的后序非遞歸算法1

  二叉樹的非遞歸后序遍歷算法2

  二叉樹的層次遍歷算法

  主函數(shù)?

本篇文章主要包括二叉樹的創(chuàng)建以及二叉樹的前序、中序、后序遍歷的遞歸算法以及前序、中序、后序、層次遍歷的非遞歸算法

• 樹的結(jié)構(gòu)體定義

typedef struct node{
    char data;
    struct node *lchild,*rchild;
}*BiTree;

• 二叉樹的創(chuàng)建（先序遞歸）?

//遞歸建立二叉樹（先序遍歷）
void CreatBiTree(BiTree &T){
    char c;
    cin>>c;
    if(c=='0'){
        T=NULL;
    }else{
        T=new node;
        T->data=c;
        CreatBiTree(T->lchild);
        CreatBiTree(T->rchild);
    }
}

• 二叉樹的先序遍歷（遞歸）

//先序遍歷遞歸
void PreOrder(BiTree T){
    if(T!=NULL){
        cout<data<<' ';
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

• 二叉樹的中序遍歷（遞歸）?

//遞歸中序遍歷
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        cout<data<<' ';
        InOrder(T->rchild);
    }
}

• 二叉樹的后序遍歷（遞歸）

//遞歸后序遍歷算法
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout<data<<' ';
    }
}

• 二叉樹的先序非遞歸遍歷算法1

頭文件中要包含#include

//非遞歸先序遍歷算法1
void PreOrder1(BiTree T){
    if(T!=NULL){
        stackSt;
        BiTree p;
        St.push(T);
        while(!St.empty()){
            p=St.top();
            St.pop();
            cout<data<<' ';
            if(p->rchild!=NULL){
                St.push(p->rchild);
            }
            if(p->lchild!=NULL){
                St.push(p->lchild);
            }
        }
    }
}

• 二叉樹的先序非遞歸遍歷算法2

//非遞歸先序遍歷2
void PreOrder2(BiTree T){
    if(T!=NULL){
        stackSt;
        BiTree p=T;
        while(!St.empty()||p!=NULL){
            while(p!=NULL){
                cout<data<<' ';
                St.push(p);
                p=p->lchild;
            }
            if(!St.empty()){
                p=St.top();
                St.pop();
                p=p->rchild;
            }
        }
    }
}

• 二叉樹的中序非遞歸算法

與先序非遞歸遍歷算法2的區(qū)別僅在于節(jié)點(diǎn)值輸出的位置不同

//非遞歸中序遍歷
void InOrder1(BiTree T){
    if(T!=NULL){
        stackSt;
        BiTree p=T;
        while(!St.empty()||p!=NULL){
            while(p!=NULL){
                St.push(p);
                p=p->lchild;
            }
            if(!St.empty()){
                p=St.top();
                St.pop();
                cout<data<<' ';
                p=p->rchild;
            }
        }
    }
}

• 二叉樹的后序非遞歸算法1

需要用到兩個(gè)棧

//非遞歸后序遍歷算法1
void PostOrder1(BiTree T){
    if(T!=NULL){
        stackSt1;
        stackSt2;
        BiTree p=NULL;
        St1.push(T);
        while(!St1.empty()){
            p=St1.top();
            St1.pop();
            St2.push(p);
            if(p->lchild!=NULL){
                St1.push(p->lchild);
            }
            if(p->rchild!=NULL){
                St1.push(p->rchild);
            }
        }
        while(!St2.empty()){
            p=St2.top();
            St2.pop();
            cout<data<<' ';
        }
    }
}

• 二叉樹的非遞歸后序遍歷算法2

這個(gè)算法具有一個(gè)良好的性質(zhì)：每當(dāng)訪問到這個(gè)節(jié)點(diǎn)時(shí)，棧中存放的是這個(gè)節(jié)點(diǎn)的祖先節(jié)點(diǎn)。由這個(gè)算法可以改寫得到其他許多問題的解法。

//非遞歸后序遍歷算法2
void PostOrder2(BiTree T){
    if(T!=NULL){
        stackSt;
        BiTree p=T;
        BiTree r=NULL;
        while(p!=NULL||!St.empty()){
            if(p!=NULL){
                St.push(p);
                p=p->lchild;
            }
            else{
                p=St.top();
                if(p->rchild!=NULL&&p->rchild!=r){
                    p=p->rchild;
                }else{
                    p=St.top();
                    St.pop();
                    cout<data<<' ';
                    r=p;
                    p=NULL;
                }
            }
        }
    }
}

• 二叉樹的層次遍歷算法

頭文件中要包含#include

//層次遍歷
void LevelOrder(BiTree T){
    queueQ;
    Q.push(T);
    BiTree p;
    while(!Q.empty()){
        p=Q.front();
        Q.pop();
        cout<data<<' ';
        if(p->lchild!=NULL){
            Q.push(p->lchild);
        }
        if(p->rchild!=NULL){
            Q.push(p->rchild);
        }
    }
}

int main(){
    system("chcp 65001");//控制輸出中文
    BiTree T;
    CreatBiTree(T);
    cout<<"二叉樹的先序遍歷序列為：";
    PreOrder(T);
    cout<

運(yùn)行結(jié)果如下圖所示：

上例中建的樹如下圖所示：