北京赛车pk10直播开奖
首頁
登錄 | 注冊

二叉樹、前序遍歷、中序遍歷、后序遍歷

一、樹

在談二叉樹前先談下樹和圖的概念

樹:不包含回路的連通無向圖(樹是一種簡單的非線性結構)

二叉樹、前序遍歷、中序遍歷、后序遍歷

樹有著不包含回路這個特點,所以樹就被賦予了很多特性

1、一棵樹中任意兩個結點有且僅有唯一的一條路徑連通

2、一棵樹如果有n個結點,那它一定恰好有n-1條邊

3、在一棵樹中加一條邊將會構成一個回路

4、樹中有且僅有一個沒有前驅的結點稱為根結點

在對樹進行討論的時候將樹中的每個點稱為結點,

根結點:沒有父結點的結點

葉結點:沒有子結點的結點

內部結點:一個結點既不是根結點也不是葉結點

每個結點還有深度,比如上圖左邊的樹的4號結點深度是3(深度是指從根結點到這個結點的層數,根結點為第一層)

二、二叉樹

基本概念:

二叉樹是一種非線性結構,二叉樹是遞歸定義的,其結點有左右子樹之分

二叉樹的存儲結構:

二叉樹通常采用鏈式存儲結構,存儲結點由數據域和指針域(指針域:左指針域和右指針域)組成,二叉樹的鏈式存儲結構也稱為二叉鏈表,對滿二叉樹和完全二叉樹可按層次進行順序存儲

特點:

1、每個結點最多有兩顆子樹

2、左子樹和右子樹是有順序的,次序不能顛倒

3、即使某結點只有一個子樹,也要區分左右子樹

4、二叉樹可為空,空的二叉樹沒有結點,非空二叉樹有且僅有一個根節點

二叉樹中有兩種特殊的二叉樹:滿二叉樹、完全二叉樹

滿二叉樹:二叉樹中每個內部結點都有存在左子樹和右子樹(或者說滿二叉樹所有的葉結點都有同樣的深度)

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

(滿二叉樹的嚴格的定義是:一顆深度為h且有2h-1個結點的二叉樹)

二叉樹、前序遍歷、中序遍歷、后序遍歷

完全二叉樹:

第一種解釋:如果一顆二叉樹除最右邊位置上有一個或幾個葉結點缺少外,其他是豐滿的那么這樣的二叉樹就是完全二叉樹(這句話不太好理解),看下面第二種解釋

第二種解釋:除第h層外,其他各層(1到h-1)的結點數都達到最大個數,第h層從右向左連續缺若干結點,則這個二叉樹就是完全二叉樹

也就是說如果一個結點有右子結點,那么它一定也有左子結點

第三種解釋:除最后一層外,每一層上的節點數均達到最大值,在最后一層上只缺少右邊的若干結點

完全二叉樹的形狀類似于下圖

二叉樹、前序遍歷、中序遍歷、后序遍歷

為了方便理解請看下圖(個人理解:完全二叉樹就是從上往下填結點,從左往右填,填滿了一層再填下一層)

二叉樹、前序遍歷、中序遍歷、后序遍歷

二叉樹相關詞語解釋:

結點的度:結點擁有的子樹的數目

葉子結點:度為0的結點(tips:在任意一個二叉樹中,度為0的葉子結點總是比度為2的結點多一個)

分支結點:度不為0的結點

樹的度:樹中結點的最大的度

層次:根結點的層次為1,其余結點的層次等于該結點的雙親結點的層次加1

樹的高度:樹中結點的最大層次

二叉樹基本性質:

性質1:在二叉樹的第k層上至多有2k-1個結點(k>=1)

性質2:在深度為m的二叉樹至多有2m-1個結點

性質3:對任意一顆二叉樹,度為0的結點(即葉子結點)總是比度為2的結點多一個

性質4:具有n個結點的完全二叉樹的深度至少為[log2n]+1,其中[log2n]表示log2n的整數部分

存儲方式

存儲的方式和圖一樣,有鏈表和數組兩種,用數組存訪問速度快,但插入、刪除節點操作就比較費時了。實際中更多的是用鏈來表示二叉樹(下面的實現代碼使用的是鏈表)

實現代碼:

#include <stdio.h>
#include <stdlib.h>
#define N 10

typedef struct node
{
    char data;
    struct node *lchild;    /* 左子樹 */
    struct node *rchild;    /* 右子樹 */

}BiTNode, *BiTree;   

void CreatBiTree (BiTree *T) /* BiTree *T等價于 struct node **T    */
{
    char ch;
   
    scanf("%c", &ch);
    if (ch == '#')    /* 當遇到#時,令樹的結點為NULL,從而結束該分支的遞歸 */
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (*T == NULL)
        {
            printf("內存分配失敗");
            exit(0);
        }
        (*T)->data = ch;        /* 生成結點 */
        CreatBiTree(&(*T)->lchild);    /* 構造左子樹 */
        CreatBiTree(&(*T)->rchild);    /* 構造右子樹 */
        /* 這里需要注意的是->的優先級比&高,所以&(*T)->lchild得到的是lchild的地址 */
    }

}
int main()
{
    int level  = 1;

    BiTree t = NULL;
    printf("以前序遍歷方式輸入二叉樹\n");
    CreatBiTree(&t);    /* 傳入指針的地址 */
}

上面的代碼采用的是以前序遍歷方式輸入二叉樹,當輸入“#”時,指針指向NULL,說明是改結點是葉結點

三、二叉樹的遍歷(前序\中序\后序遍歷)

二叉樹的遍歷是指不重復地訪問二叉樹中所有結點,主要指非空二叉樹,對于空二叉樹則結束返回,二叉樹的遍歷主要包括前序遍歷、中序遍歷、后序遍歷

前序遍歷:首先訪問根結點,然后遍歷左子樹,最后遍歷右子樹(根->左->右)

順序:訪問根節點->前序遍歷左子樹->前序遍歷右子樹

/* 以遞歸方式 前序遍歷二叉樹 */
void PreOrderTraverse(BiTree t, int level)
{
    if (t == NULL)   
    {
        return ;
    }
    printf("data = %c level = %d\n ", t->data, level);
    PreOrderTraverse(t->lchild, level + 1);
    PreOrderTraverse(t->rchild, level + 1);
}

中序遍歷:首先遍歷左子樹,然后訪問根節點,最后遍歷右子樹(左->根->右)

順序:中序遍歷左子樹->訪問根節點->中序遍歷右子樹

/* 以遞歸方式 中序遍歷二叉樹 */
void PreOrderTraverse(BiTree t, int level)
{
    if (t == NULL)   
    {
        return ;
    }
    PreOrderTraverse(t->lchild, level + 1);
    printf("data = %c level = %d\n ", t->data, level);
    PreOrderTraverse(t->rchild, level + 1);
}

后序遍歷:首先遍歷左子樹,然后遍歷右子樹,最后訪問根節點(左->右->根)

順序:后序遍歷左子樹->后序遍歷右子樹->訪問根節點

/* 以遞歸方式 后序遍歷二叉樹 */
void PreOrderTraverse(BiTree t, int level)
{
    if (t == NULL)   
    {
        return ;
    }
    PreOrderTraverse(t->lchild, level + 1);
    PreOrderTraverse(t->rchild, level + 1);
    printf("data = %c level = %d\n ", t->data, level);
}

從上面可以看出,三種遍歷方式極其相似,只是語句 printf("data = %c level = %d\n ", t->data, level);的位置發生了變化



2019 monjeep.com webmaster#monjeep.com
12 q. 0.010 s.
京ICP備10005923號
北京赛车pk10直播开奖
老快3中奖规则 东方六加一今晚开奖结果查询 重庆时时彩调整通知 江苏快三跨度 北京pk走势图教程 福建三十五选七开奖结果 北京赛车pk10sohu 正宗黑龙江麻将 pc蛋蛋稳定挂机模式 中国竞彩网竞猜冠亚军