樹(shù)和二叉樹(shù)(順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ))

1.樹(shù)的概念

節(jié)點(diǎn)：節(jié)點(diǎn)包括一個(gè)數(shù)據(jù)元素及若干指向其他子樹(shù)的分支。
節(jié)點(diǎn)的度：節(jié)點(diǎn)所擁有子樹(shù)的個(gè)數(shù)稱(chēng)為節(jié)點(diǎn)的度。
葉節(jié)點(diǎn)：度為0的節(jié)點(diǎn)成為葉結(jié)點(diǎn)，葉結(jié)點(diǎn)也稱(chēng)為終端節(jié)點(diǎn)。
分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)稱(chēng)為分支節(jié)點(diǎn)妻往，分支節(jié)點(diǎn)又稱(chēng)非終端節(jié)點(diǎn)。一棵樹(shù)中排除葉結(jié)點(diǎn)外的所有節(jié)點(diǎn)都是分支節(jié)點(diǎn)试和。
祖先節(jié)點(diǎn)：從根節(jié)點(diǎn)到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)讯泣。
子孫節(jié)點(diǎn)：以某節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù)中所有節(jié)點(diǎn)
雙親節(jié)點(diǎn)：樹(shù)中某節(jié)點(diǎn)有孩子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱(chēng)為它孩子節(jié)點(diǎn)的雙親節(jié)點(diǎn)阅悍，雙親節(jié)點(diǎn)也成為前驅(qū)節(jié)點(diǎn)好渠。
孩子節(jié)點(diǎn)：樹(shù)中一個(gè)節(jié)點(diǎn)的子樹(shù)的根節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的孩子節(jié)點(diǎn)，孩子節(jié)點(diǎn)也稱(chēng)為后繼節(jié)點(diǎn)节视。
兄弟節(jié)點(diǎn)：具有相同雙親節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為兄弟節(jié)點(diǎn)拳锚。
樹(shù)的度：樹(shù)中所有節(jié)點(diǎn)的度的最大值成為該樹(shù)的度。
節(jié)點(diǎn)的層次：從根節(jié)點(diǎn)到樹(shù)中某節(jié)點(diǎn)所經(jīng)路徑上的分支也稱(chēng)為該節(jié)點(diǎn)的層次寻行，根節(jié)點(diǎn)的層次為1霍掺，其他節(jié)點(diǎn)層次是雙親節(jié)點(diǎn)層次加1.
樹(shù)的深度：樹(shù)中所有節(jié)點(diǎn)的層次的最大值稱(chēng)為該樹(shù)的深度。

2.二叉樹(shù)

2.1 定義:

二叉樹(shù)，是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分之的樹(shù)結(jié)構(gòu)杆烁，通常分之被稱(chēng)作“左子樹(shù)”或者“右子樹(shù)”牙丽；二叉樹(shù)的分之具有左右次序，且不能隨意顛倒兔魂。

2.2 性質(zhì):

性質(zhì)1: 在二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)
性質(zhì)2: 深度為K的二叉樹(shù)最多有2k -1 個(gè)結(jié)點(diǎn)(K>=1)
性質(zhì)3: 對(duì)于任何一顆二叉樹(shù)T,如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié) 點(diǎn)數(shù)為n2,則n0 = n2 + 1;
性質(zhì)4: 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為(log2(n))+1
性質(zhì)5:對(duì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)剩岳，如果按照從上至下和從左至右的順序?qū)Χ?叉樹(shù)的所有結(jié)點(diǎn)從1開(kāi)始編號(hào)，則對(duì)于任意的序號(hào)為i的結(jié)點(diǎn)有:
A.如果i>1入热，那么序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號(hào)為i/2;
B.如果i=1，那么序號(hào)為i的結(jié)點(diǎn)為根節(jié)點(diǎn)晓铆，無(wú)雙親結(jié)點(diǎn);
C.如果2i<=n勺良，那么序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)序號(hào)為2i;
D.如果2i>n，那么序號(hào)為i的結(jié)點(diǎn)無(wú)左孩子;
E.如果2i+1<=n骄噪，那么序號(hào)為i的結(jié)點(diǎn)右孩子序號(hào)為2i+1;
F.如果2i+1>n尚困，那么序號(hào)為i的結(jié)點(diǎn)無(wú)右孩子。

2.3 五種形態(tài):

2.4 特殊二叉樹(shù)-斜樹(shù)

2.5 完全二叉樹(shù)

若設(shè)二叉樹(shù)的深度為h链蕊，除第 h 層外事甜，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊滔韵，這就是完全二叉樹(shù)逻谦。

3. 二叉樹(shù)的順序存儲(chǔ)（數(shù)組存儲(chǔ)）

滿(mǎn)二叉樹(shù)的順序存儲(chǔ)

一般二叉樹(shù)的順序存儲(chǔ)，造成了空間浪費(fèi)

斜樹(shù)的存儲(chǔ)陪蜻，會(huì)造成了嚴(yán)重的空間浪費(fèi)

我們想存儲(chǔ)好二叉樹(shù)邦马，就必須解決空間浪費(fèi)的問(wèn)題。

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


#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存儲(chǔ)空間初始分配量 */
#define MAX_TREE_SIZE 100 /* 二叉樹(shù)的最大結(jié)點(diǎn)數(shù) */

typedef int Status;        /* Status是函數(shù)的類(lèi)型,其值是函數(shù)結(jié)果狀態(tài)代碼宴卖，如OK等 */
typedef int CElemType;      /* 樹(shù)結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型滋将，目前暫定為整型 */
typedef CElemType SqBiTree[MAX_TREE_SIZE]; /* 0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)  */
CElemType Nil = 0;   /*設(shè)整型以0為空 或者以 INT_MAX(65535)*/

typedef struct {
    int level; //結(jié)點(diǎn)層
    int order; //本層的序號(hào)(按照滿(mǎn)二叉樹(shù)給定序號(hào)規(guī)則)
}Position;

3.2 二叉樹(shù)的基本操作

//6.1 visit
Status visit(CElemType c){
    printf("%d ",c);
    return OK;
}

//6.2 構(gòu)造空二叉樹(shù)T,因?yàn)門(mén)是固定數(shù)組,不會(huì)改變.
Status InitBiTree(SqBiTree T){
    
    for (int i = 0; i < MAX_TREE_SIZE; i++) {
        //將二叉樹(shù)初始化值置空
        T[i] = Nil;
    }
    
    return OK;
}

//6.3 按層序次序輸入二叉樹(shù)中的結(jié)點(diǎn)值(字符型或整型),構(gòu)造順序存儲(chǔ)的二叉樹(shù)T
Status CreateBiTree(SqBiTree T){
    int i = 0;
    
    //printf("按層序輸入結(jié)點(diǎn)的值(整型),0表示空結(jié)點(diǎn), 輸入999結(jié)束.結(jié)點(diǎn)數(shù)<=%d\n",MAX_TREE_SIZE);
    /*
     1      -->1
     2     3   -->2
     4  5  6   7 -->3
     8  9 10       -->4
     
     1 2 3 4 5 6 7 8 9 10 Nil Nil Nil
     */
    
    while (i < 10) {
        T[i] = i+1;
        printf("%d ",T[i]);
        
        //結(jié)點(diǎn)不為空,且無(wú)雙親結(jié)點(diǎn)
        if (i != 0 && T[(i+1)/2-1] == Nil && T[i] != Nil) {
            printf("出現(xiàn)無(wú)雙親的非根結(jié)點(diǎn)%d\n",T[i]);
            exit(ERROR);
        }
        
        i++;
        
    }
    
    //將空賦值給T的后面的結(jié)點(diǎn)
    while (i < MAX_TREE_SIZE) {
        T[i] = Nil;
        i++;
    }
    
    return OK;
}

//技巧:
//如果大家想要2個(gè)函數(shù)的結(jié)果一樣,但是目的不同;
//在順序存儲(chǔ)結(jié)構(gòu)中, 兩個(gè)函數(shù)完全一樣的結(jié)果
#define ClearBiTree InitBiTree

/*6.4 判斷二叉樹(shù)是否為空
 初始條件: 二叉樹(shù)已存在
 操作結(jié)果: 若T為空二叉樹(shù),則返回TRUE,否則返回FALSE;
 */
Status BiTreeEmpty(SqBiTree T){
    //根結(jié)點(diǎn)為空,則二叉樹(shù)為空
    if (T[0] == Nil)
        return TRUE;
    
    return FALSE;
}

/*6.5 獲取二叉樹(shù)的深度
 初始條件: 二叉樹(shù)已存在
 操作結(jié)果: 返回二叉樹(shù)T深度;
 */
int BiTreeDepth(SqBiTree T){
    
    int j = -1;
    int i;
    
    //找到最后一個(gè)結(jié)點(diǎn)
    //MAX_TREE_SIZE -> 100 -> 10 目的找到最后一個(gè)結(jié)點(diǎn)10的位置
    for (i = MAX_TREE_SIZE-1 ; i>=0; i--) {
        if (T[i] != Nil)
            break;
    }
    
    do {
        j++;
    } while ( powl(2, j) <= i); //計(jì)算2的次冪
    
    return j;
}

/*6.6 返回處于位置e(層,本層序號(hào))的結(jié)點(diǎn)值
 初始條件: 二叉樹(shù)T存在,e是T中某個(gè)結(jié)點(diǎn)(的位置)
 操作結(jié)構(gòu): 返回處于位置e(層,本層序號(hào))的結(jié)點(diǎn)值
 */
CElemType Value(SqBiTree T,Position e){
    
    /*
     Position.level -> 結(jié)點(diǎn)層.表示第幾層;
     Position.order -> 本層的序號(hào)(按照滿(mǎn)二叉樹(shù)給定序號(hào)規(guī)則)
     */
    
    //pow(2,e.level-1) 找到層序
    printf("%d\n",(int)pow(2,e.level-1));
    
    //e.order
    printf("%d\n",e.order);
    
    //4+2-2;
    return T[(int)pow(2, e.level-1)+e.order-2];
    
}


/*6.7 獲取二叉樹(shù)跟結(jié)點(diǎn)的值
 初始條件: 二叉樹(shù)T存在
 操作結(jié)果: 當(dāng)T不空,用e返回T的根, 返回OK; 否則返回ERROR
 */
Status Root(SqBiTree T,CElemType *e){
    if (BiTreeEmpty(T)) {
        return ERROR;
    }
    
    *e = T[0];
    return OK;
}

/*
 6.8 給處于位置e的結(jié)點(diǎn)賦值
 初始條件: 二叉樹(shù)存在,e是T中某個(gè)結(jié)點(diǎn)的位置
 操作結(jié)果: 給處于位置e的結(jié)點(diǎn)賦值Value;
 */
Status Assign(SqBiTree T,Position e,CElemType value){
    
    //找到當(dāng)前e在數(shù)組中的具體位置索引
    int i = (int)powl(2, e.level-1)+e.order -2;
    
    //葉子結(jié)點(diǎn)的雙親為空
    if (value != Nil &&  T[(i+1)/2-1] == Nil) {
        return ERROR;
    }
    
    //給雙親賦空值但是有葉子結(jié)點(diǎn)
    if (value == Nil && (T[i*2+1] != Nil || T[i*2+2] != Nil)) {
        return  ERROR;
    }
    
    T[i] = value;
    return OK;
}

/*
 6.9 獲取e的雙親;
 初始條件: 二叉樹(shù)存在,e是T中的某一個(gè)結(jié)點(diǎn)
 操作結(jié)果: 若e是T的非根結(jié)點(diǎn), 則返回它的雙親,否則返回"空"
 */
CElemType Parent(SqBiTree T, CElemType e){
    
    //空樹(shù)
    if (T[0] == Nil) {
        return Nil;
    }
    
    for (int i = 1 ; i < MAX_TREE_SIZE; i++) {
        //找到e
        if (T[i] == e) {
            return T[(i+1)/2 - 1];
        }
    }
    
    //沒(méi)有找到
    return Nil;
    
}

/*
 6.10 獲取某個(gè)結(jié)點(diǎn)的左孩子;
 初始條件:二叉樹(shù)T存在,e是某個(gè)結(jié)點(diǎn)
 操作結(jié)果:返回e的左孩子,若e無(wú)左孩子,則返回"空"
 */
CElemType LeftChild(SqBiTree T,CElemType e){
    
    //空樹(shù)
    if (T[0] == Nil) {
        return Nil;
    }
    for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
        //找到e
        if (T[i] == e) {
            return T[i*2+1];
        }
    }
    
    //沒(méi)有找到
    return Nil;
    
}

/*
 6.11 獲取某個(gè)結(jié)點(diǎn)的右孩子;
 初始條件:二叉樹(shù)T存在,e是某個(gè)結(jié)點(diǎn)
 操作結(jié)果:返回e的左孩子,若e無(wú)左孩子,則返回"空"
 */
CElemType RightChild(SqBiTree T,CElemType e){
    
    //空樹(shù)
    if (T[0] == Nil) {
        return Nil;
    }
    for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
        //找到e
        if (T[i] == e) {
            return T[i*2+2];
        }
    }
    
    //沒(méi)有找到
    return Nil;
    
}

/*
 6.12 獲取結(jié)點(diǎn)的左兄弟
 初始條件:  二叉樹(shù)T存在,e是T中某個(gè)結(jié)點(diǎn)
 操作結(jié)果: 返回e的左兄弟。若e是T的左孩子或無(wú)左兄弟,則返回＂空＂
 */
CElemType LeftSibling(SqBiTree T,CElemType e)
{
    /* 空樹(shù) */
    if(T[0]==Nil)
        return Nil;
    
    for(int i=1;i<=MAX_TREE_SIZE-1;i++)
    /* 找到e且其序號(hào)為偶數(shù)(是右孩子) */
        if(T[i]==e&&i%2==0)
            return T[i-1];
    
    return Nil; /* 沒(méi)找到e */
}

/* 6.13 獲取結(jié)點(diǎn)的右兄弟
 初始條件: 二叉樹(shù)T存在,e是T中某個(gè)結(jié)點(diǎn)
 操作結(jié)果: 返回e的右兄弟症昏。若e是T的右孩子或無(wú)右兄弟,則返回＂空＂
 */
CElemType RightSibling(SqBiTree T,CElemType e)
{
    /* 空樹(shù) */
    if(T[0]==Nil)
        return Nil;
    
    for(int i=1;i<=MAX_TREE_SIZE-1;i++)
    /* 找到e且其序號(hào)為奇數(shù)(是左孩子) */
        if(T[i]==e&&i%2==1)
            return T[i+1];
    
    return Nil; /* 沒(méi)找到e */
}

3.3 二叉樹(shù)的遍歷

/*
 6.14 層序遍歷二叉樹(shù)
 */
void LevelOrderTraverse(SqBiTree T){
    
    int i = MAX_TREE_SIZE-1;
    
    //找到最后一個(gè)非空結(jié)點(diǎn)的序號(hào)
    while (T[i] == Nil) i--;
    
    //從根結(jié)點(diǎn)起,按層序遍歷二叉樹(shù)
    for (int j = 0; j <= i; j++)
        //只遍歷非空結(jié)點(diǎn)
        if (T[j] != Nil)
            visit(T[j]);
    
    printf("\n");
}

/*
 6.15 前序遍歷二叉樹(shù)
 */
void PreTraverse(SqBiTree T,int e){
    
    //打印結(jié)點(diǎn)數(shù)據(jù)
    visit(T[e]);
    
    //先序遍歷左子樹(shù)
    if (T[2 * e + 1] != Nil) {
        PreTraverse(T, 2*e+1);
    }
    //最后先序遍歷右子樹(shù)
    if (T[2 * e + 2] != Nil) {
        PreTraverse(T, 2*e+2);
    }
}

Status PreOrderTraverse(SqBiTree T){
    
    //樹(shù)不為空
    if (!BiTreeEmpty(T)) {
        PreTraverse(T, 0);
    }
    printf("\n");
    return  OK;
}

/*
 6.16 中序遍歷
 */
void InTraverse(SqBiTree T, int e){
    
    /* 左子樹(shù)不空 */
    if (T[2*e+1] != Nil)
        InTraverse(T, 2*e+1);
    
    visit(T[e]);
    
    /* 右子樹(shù)不空 */
    if (T[2*e+2] != Nil)
        InTraverse(T, 2*e+2);
}

Status InOrderTraverse(SqBiTree T){
    
    /* 樹(shù)不空 */
    if (!BiTreeEmpty(T)) {
        InTraverse(T, 0);
    }
    printf("\n");
    return OK;
}

/*
 6.17 后序遍歷
 */
void PostTraverse(SqBiTree T,int e)
{   /* 左子樹(shù)不空 */
    if(T[2*e+1]!=Nil)
        PostTraverse(T,2*e+1);
    /* 右子樹(shù)不空 */
    if(T[2*e+2]!=Nil)
        PostTraverse(T,2*e+2);
    
    visit(T[e]);
}
Status PostOrderTraverse(SqBiTree T)
{
    if(!BiTreeEmpty(T)) /* 樹(shù)不空 */
        PostTraverse(T,0);
    printf("\n");
    return OK;
}

4. 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)（鏈表存儲(chǔ)）

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

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

/* 存儲(chǔ)空間初始分配量 */
#define MAXSIZE 100
/* Status是函數(shù)的類(lèi)型,其值是函數(shù)結(jié)果狀態(tài)代碼随闽，如OK等 */
typedef int Status;

#pragma mark--二叉樹(shù)構(gòu)造
int indexs = 1;
typedef char String[24]; /*  0號(hào)單元存放串的長(zhǎng)度 */
String str;
typedef char CElemType;
CElemType Nil=' '; /* 字符型以空格符為空 */
typedef struct BiTNode  /* 結(jié)點(diǎn)結(jié)構(gòu) */
{
    CElemType data;        /* 結(jié)點(diǎn)數(shù)據(jù) */
    struct BiTNode *lchild,*rchild; /* 左右孩子指針 */
}BiTNode,*BiTree;

4.2 二叉樹(shù)的基本操作

Status StrAssign(String T,char *chars)
{
    int i;
    if(strlen(chars)>MAXSIZE)
        return ERROR;
    else
    {
        T[0]=strlen(chars);
        for(i=1;i<=T[0];i++)
            T[i]=*(chars+i-1);
        return OK;
    }
}

/*7.1 打印數(shù)據(jù)*/
Status visit(CElemType e)
{
    printf("%c ",e);
    return OK;
}

/* 7.2 構(gòu)造空二叉樹(shù)T */
Status InitBiTree(BiTree *T)
{
    *T=NULL;
    return OK;
}

/* 7.3 銷(xiāo)毀二叉樹(shù)
 初始條件: 二叉樹(shù)T存在。
 操作結(jié)果: 銷(xiāo)毀二叉樹(shù)T
 */
void DestroyBiTree(BiTree *T)
{
    if(*T)
    {
        /* 有左孩子 */
        if((*T)->lchild)
            DestroyBiTree(&(*T)->lchild); /* 銷(xiāo)毀左孩子子樹(shù) */
        
        /* 有右孩子 */
        if((*T)->rchild)
            DestroyBiTree(&(*T)->rchild); /* 銷(xiāo)毀右孩子子樹(shù) */
        
        free(*T); /* 釋放根結(jié)點(diǎn) */
        
        *T=NULL; /* 空指針賦0 */
    }
}
#define ClearBiTree DestroyBiTree

/*7.4 創(chuàng)建二叉樹(shù)
 按前序輸入二叉樹(shù)中的結(jié)點(diǎn)值(字符),#表示空樹(shù);
 */
void CreateBiTree(BiTree *T){
    
    CElemType ch;
    
    //獲取字符
    ch = str[indexs++];
    
    //判斷當(dāng)前字符是否為'#'
    if (ch == '#') {
        *T = NULL;
    }else
    {
        //創(chuàng)建新的結(jié)點(diǎn)
        *T = (BiTree)malloc(sizeof(BiTNode));
        //是否創(chuàng)建成功
        if (!*T) {
            exit(OVERFLOW);
        }
        
        /* 生成根結(jié)點(diǎn) */
        (*T)->data = ch;
        /* 構(gòu)造左子樹(shù) */
        CreateBiTree(&(*T)->lchild);
        /* 構(gòu)造右子樹(shù) */
        CreateBiTree(&(*T)->rchild);
    }
    
}


/*
 7.5 二叉樹(shù)T是否為空;
 初始條件: 二叉樹(shù)T存在
 操作結(jié)果: 若T為空二叉樹(shù),則返回TRUE,否則FALSE
 */
Status BiTreeEmpty(BiTree T)
{
    if(T)
        return FALSE;
    else
        return TRUE;
}

/*
 7.6 二叉樹(shù)T的深度
 初始條件: 二叉樹(shù)T存在
 操作結(jié)果: 返回T的深度
 */
int BiTreeDepth(BiTree T){
    
    int i,j;
    if(!T)
        return 0;
    
    //計(jì)算左孩子的深度
    if(T->lchild)
        i=BiTreeDepth(T->lchild);
    else
        i=0;
    
    //計(jì)算右孩子的深度
    if(T->rchild)
        j=BiTreeDepth(T->rchild);
    else
        j=0;
    
    //比較i和j
    return i>j?i+1:j+1;
}

/*
 7.7 二叉樹(shù)T的根
 初始條件: 二叉樹(shù)T存在
 操作結(jié)果: 返回T的根
 */
CElemType Root(BiTree T){
    if (BiTreeEmpty(T))
        return Nil;
    
    return T->data;
}

/*
 7.8 返回p所指向的結(jié)點(diǎn)值;
 初始條件: 二叉樹(shù)T存在肝谭，p指向T中某個(gè)結(jié)點(diǎn)
 操作結(jié)果: 返回p所指結(jié)點(diǎn)的值
 */
CElemType Value(BiTree p){
    return p->data;
}

/*
 7.8 給p所指結(jié)點(diǎn)賦值為value;
 初始條件: 二叉樹(shù)T存在掘宪，p指向T中某個(gè)結(jié)點(diǎn)
 操作結(jié)果: 給p所指結(jié)點(diǎn)賦值為value
 */
void Assign(BiTree p,CElemType value)
{
    p->data=value;
}

4.3 二叉樹(shù)的遍歷

/*
 7.8  前序遞歸遍歷T
 初始條件:二叉樹(shù)T存在;
 操作結(jié)果: 前序遞歸遍歷T
 */

void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    printf("%c",T->data);/* 顯示結(jié)點(diǎn)數(shù)據(jù)，可以更改為其它對(duì)結(jié)點(diǎn)操作 */
    PreOrderTraverse(T->lchild); /* 再先序遍歷左子樹(shù) */
    PreOrderTraverse(T->rchild); /* 最后先序遍歷右子樹(shù) */
}


/*
 7.9  中序遞歸遍歷T
 初始條件:二叉樹(shù)T存在;
 操作結(jié)果: 中序遞歸遍歷T
 */
void InOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    InOrderTraverse(T->lchild); /* 中序遍歷左子樹(shù) */
    printf("%c",T->data);/* 顯示結(jié)點(diǎn)數(shù)據(jù)分苇，可以更改為其它對(duì)結(jié)點(diǎn)操作 */
    InOrderTraverse(T->rchild); /* 最后中序遍歷右子樹(shù) */
}

/*
 7.10  后序遞歸遍歷T
 初始條件:二叉樹(shù)T存在;
 操作結(jié)果: 中序遞歸遍歷T
 */
void PostOrderTraverse(BiTree T)
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild); /* 先后序遍歷左子樹(shù)  */
    PostOrderTraverse(T->rchild); /* 再后序遍歷右子樹(shù)  */
    printf("%c",T->data);/* 顯示結(jié)點(diǎn)數(shù)據(jù)添诉，可以更改為其它對(duì)結(jié)點(diǎn)操作 */
}

最后編輯于：2020.04.28 15:03:40

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市医寿，隨后出現(xiàn)的幾起案子栏赴，更是在濱河造成了極大的恐慌，老刑警劉巖靖秩，帶你破解...
沈念sama閱讀 217,657評(píng)論 6贊 505
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件须眷，死亡現(xiàn)場(chǎng)離奇詭異竖瘾，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)花颗，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,889評(píng)論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)捕传，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人扩劝，你說(shuō)我怎么就攤上這事庸论。” “怎么了棒呛？”我有些...
開(kāi)封第一講書(shū)人閱讀 164,057評(píng)論 0贊 354
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵聂示，是天一觀的道長(zhǎng)。經(jīng)常有香客問(wèn)我簇秒，道長(zhǎng)鱼喉，這世上最難降的妖魔是什么？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,509評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任趋观，我火速辦了婚禮扛禽，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘皱坛。我一直安慰自己编曼，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,562評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布麸恍。她就那樣靜靜地躺著灵巧，像睡著了一般。火紅的嫁衣襯著肌膚如雪抹沪。梳的紋絲不亂的頭發(fā)上刻肄，一...
開(kāi)封第一講書(shū)人閱讀 51,443評(píng)論 1贊 302
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音融欧，去河邊找鬼敏弃。笑死，一個(gè)胖子當(dāng)著我的面吹牛噪馏，可吹牛的內(nèi)容都是我干的麦到。我是一名探鬼主播，決...
沈念sama閱讀 40,251評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼欠肾，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼瓶颠！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起刺桃，我...
開(kāi)封第一講書(shū)人閱讀 39,129評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤粹淋，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體桃移，經(jīng)...
沈念sama閱讀 45,561評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡屋匕，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,779評(píng)論 3贊 335
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了借杰。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片过吻。...
茶點(diǎn)故事閱讀 39,902評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖蔗衡，靈堂內(nèi)的尸體忽然破棺而出纤虽，到底是詐尸還是另有隱情，我是刑警寧澤绞惦，帶...
沈念sama閱讀 35,621評(píng)論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布廓推，位于F島的核電站，受9級(jí)特大地震影響翩隧，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜呻纹，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,220評(píng)論 3贊 328
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一堆生、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧雷酪，春花似錦淑仆、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,838評(píng)論 0贊 22
一樁弒父案蔗怠，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至吩跋，卻和暖如春寞射，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背锌钮。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,971評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工桥温，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人梁丘。一個(gè)月前我還...
沈念sama閱讀 48,025評(píng)論 2贊 370
代替公主和親
正文我出身青樓侵浸，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親氛谜。傳聞我的和親對(duì)象是個(gè)殘疾皇子掏觉，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,843評(píng)論 2贊 354