typora-copy-images-to: upload

前言

上一章講到二叉樹的順序結構實作以及運用,而此篇文章是為了講解二叉樹的鏈式結構以及相關運用.

二叉樹的鏈式結構

如果想用鏈式結構進行實作二叉樹,那么一定少不了左右指標(指向孩子),所以實作結構如下:

typedef char BTDataType;

typedef struct BinaryTree
{
    BTDataType val;
    struct BinaryTree* left;
    struct BinaryTree* right;
}BTNOde;

二叉樹的遍歷方式

二叉樹的遍歷方式主要有四種,前面先介紹3種,最后再介紹第四種.

• 第一種,前序遍歷,方式為先遍歷根結點,左子樹,右子樹
• 第二種,中序遍歷,方式為先遍歷左子樹,根結點,右子樹
• 第三種,后序遍歷,方式為先遍歷左子樹,右子樹,根結點

其中這三種遍歷方式一般都用遞回進行實作.

前序遍歷

上面已經說到,前序遍歷方式為根結點—>左子樹—>右子樹,我們用下圖為例

按照前序遍歷方式,其遍歷順序為A–>B–>D–>R–>T–>E–>Y–>C–>Q–>U–>W,這個答案可能和大家想的不一樣,理由就是沒有明白我們的遍歷方式.按照前序遍歷方式,我們應該先遍歷根結點,即A,然后遍歷左子樹,當進入左子樹后,我們是需要又執行前序遍歷方式,即遍歷根結點B,然后又要遍歷左子樹,當我們再進入左子樹,又是先遍歷根結點即D,然后又遍歷左子樹,按照順序遍歷到R,此時終于完成 根結點,左子樹,我們遍歷右子樹,進入右子樹后又遍歷根結點,即T…所以我們的這種遍歷方式其實遞回性質的.

前序遍歷代碼:

void PreOreder(BTNode* root)
{
    if(!root)  return ;     //如果為空結點,直接列印NULL
    printf("%c-->",root->val);   //遍歷根結點
    PreOreder(root->left);       //遍歷左子樹
    PreOreder(root->right);      //遍歷右子樹
}

測驗:

中序遍歷

中序遍歷方式為左子樹,根結點,右子樹,所以仍以上面的圖為例,我們的遍歷方式順序為:

R–>D–>T–>B–>E–>Y–>A–>Q–>U–>C–>W

中序遍歷代碼:

void InOrder(BTNode* root)
{
    if(!root) return;         //如果當前結點為空,直接結束
    InOrder(root->left);      //遍歷左子樹
    printf("%c",root->val);   //列印當前結點值
    InOrder(root->right);     //遍歷右子樹
}

測驗:

后序遍歷

后序遍歷方式為 左子樹,右子樹,根結點.,按照上面的圖示,我們得出的遍歷順序應該如下:

R–>T–>D–>Y–>E–>B–>U–>Q–>W–>C–>A

后序遍歷代碼如下:

void PostOrder(BTNode* root)
{
    if(!root) return;         //如果當前結點為空,直接結束
    InOrder(root->left);      //遍歷左子樹
    InOrder(root->right);     //遍歷右子樹
    printf("%c",root->val);   //列印當前結點值
}

測驗:

二叉樹前中后序遍歷練習

前序遍歷練習

中序遍歷練習

后序遍歷練習

利用前序遍歷中序遍歷結合

二叉樹其他操作

二叉樹結點個數

按照遞回思想,計算二叉樹的結點數量,我們可以認為 數量 = 1 + 左子樹數量 + 右子樹數量,其中1是當前根結點數量(前提是存在)

int BinaryTreeSize(BTNode* root)
{
    if(!root) return 0;
    int left = BinaryTreeSize(root->left);
    int right = BinaryTreeSize(root->right);
    return 1 + left + right;
}

二叉樹葉子結點個數

按照遞回思想,計算二叉樹的葉子結點數量,我們可以認為數量等于 = 0 + 左子樹葉子結點數量 + 右子樹葉子結點數量,0是因為當前根結點有子樹,說明根結點不是葉子結點.

int BinaryTreeLeafSize(BTNode* root)
{
    if(!root) return 0;
    
    if(root->left == NULL && root->right == NULL) return 1;
    
    int left = BinaryTreeLeafSize(root->left);
    int right = BinaryTreeLeafSize(root->right);
    return left + right;
}

二叉樹第K層節點個數

第k層是指從根結點開始算第一層,往下到第K層.

按照遞回思想我們反過來,根結點是第k層,后面向下k逐漸遞減,k等于1時候便是我們所求.

而數量等于左子樹第k層加上右子樹第k層.

int BinaryTreeKSize(BTNode* root,int k)
{
    if(!root) return 0;
    
    if(k==1) return 1;
    
    int left = BinaryTreeLeafSize(root->left,k-1);
    int right = BinaryTreeLeafSize(root->right,k-1);
    
    return left + right;
}

二叉樹查找值為x的節點

按照遞回思想,先判斷當前結點是否是目標,然后查找左子樹,再查找右子樹.

如果左右子樹都沒有找到,就回傳NULL

BTNode* BinaryTreeFind(BTNode* root, int n)
{
    if(!root) return  NULL;
    if(root->val == n) return root;
    
    BTNode* left = BinaryTreeFind(root->left,n);
    if(left) return left;
    BTNode* right = BinaryTreeFind(root->right,n);
    if(right) return right;
    return NULL;
}

二叉樹的高度

按照遞回思想,二叉樹的高度等于1 + 左右子樹高度的最大值.

int BinaryTreeDepth(BTNode* root)
{
    if(!root) return 0;
    
    int left = BinaryTreeDepth(root->left);
    int right = BinaryTreeDepth(root->right);
    
    int maxval = left < right ? right : left;
    
    return 1 +maxvalue;
}

二叉樹的層序遍歷

層序遍歷我們一般需要使用佇列,什么是程式遍歷呢?

層序遍歷就是遍歷順序是**整整一層,**以下圖為例:

程式遍歷結果為: 3-->4-->3-->8-->6-->6-->7.

而我們利用佇列是怎樣進行實作呢?答案是先進去一個結點,再出去一個結點,但是結點出去之前,孩子按左右順序進入.

如下圖:

我們前面已經實作過了佇列的各種操作,這里便不再續寫佇列,直接參考.

佇列定義細節修改:

typedef struct BinaryTree QDataType;
typedef struct Queue
{
    QdataType* val;
    struct Queue* next;
}Queue;

層序遍歷:

int main()
{
    Queue q = {0};
    BTNode* tree = CreateTree();
    QueueInit(&q);
    
    QueuePush(&q,tree);
    while(!QueueEmpty(&q))
    {
        BTNode* top =  QueueFront(&q);
        QueuePop(&q);
        if(top->left)  QueuePush(&q,top->left);
        if(top->right) QueuePush(&q,top->right);
        printf("%c ",top->val);
    }
    return  0;
}