資料結構先序序列建立二叉樹

2022.11.19連發兩回。

先序序列建立二叉樹

• 任務描述
• 相關知識
• 程式設計要求
• 測試說明
• C/C++代碼

任務描述

本關任務：利用先序周遊建立二叉樹，并給出相應二叉樹的中序周遊結果。

相關知識

為了完成本關任務，你需要掌握：1.二叉樹的前序周遊，2.如何建立一顆二叉樹，3.二叉樹的中序周遊。

二叉樹的前序周遊

前序周遊preorder traversal是指按照先根節點，再左節點，最後右節點的次序通路二叉樹中所有的節點，使得每個節點被通路且僅被通路一次。

例：圖1表示一個二叉樹，前序周遊的順序如節點上面數字所示，結果為ABCDEF。

利用先序周遊建立二叉樹，我們需要知道先序周遊的葉子節點，通過增加符合#表示葉子節點的子節點，則圖1的先序周遊為：ABC##D##EF###。

根據先序周遊的過程，首先建立根節點，然後使用遞歸的方法建立左子樹節點，直到遇到符号#，表示到了葉子節點，回溯父節點并建立右子樹節點。

僞代碼如下：

二叉樹的中序周遊

中序周遊inorder traversal是指按照先左節點，再根節點，最後右節點的次序通路二叉樹中所有的節點，使得每個節點被通路且僅被通路一次。

例：圖2表示一個二叉樹，中序周遊的順序如節點上面數字所示，結果為CBDAFE。

程式設計要求

本關的程式設計任務是補全右側代碼片段CreatBiTree和InOrder中Begin至End中間的代碼，具體要求如下：

在CreatBiTree中，利用先序周遊建立二叉樹，并傳回二叉樹根節點指針。

在InOrder中，完成二叉樹的中序周遊，并輸出周遊結果，中間沒有空格，末尾不換行。

測試說明

平台将自動編譯補全後的代碼，并生成若幹組測試資料，接着根據程式的輸出判斷程式是否正确。

以下是平台的測試樣例：

測試輸入：ABC##D##EF###

預期輸出：CBDAFE

測試輸入：ABCD###E#F##G##

預期輸出：DCBEFAG

開始你的任務吧，祝你成功！

C/C++代碼

//
//  binary_tree.cpp

#include "binary_tree.h"

//建立新結點的工具函數
BTNode* getNewNode(char e)
{
    BTNode* p = (BTNode*)malloc(sizeof(BTNode));
    p->data = e;
    p->lchild = p->rchild = NULL;
    return p;
}


BTNode* CreateTree(char* s, int &i, int len)
// 利用先序周遊建立二叉樹
// 參數：先序周遊字元串s，字元串初始下标i=0，字元串長度len。
// 傳回：二叉樹
{
    // 請在這裡補充代碼，完成本關任務
    /********** Begin *********/
    if(s[i]=='#' || i>len){i++;return NULL;}
    BTNode* BTP = getNewNode(s[i++]);
    BTP->lchild = CreateTree(s,i,len);
    BTP->rchild = CreateTree(s,i,len);
    return BTP;
    /********** End **********/
}

// 二叉樹的中序周遊
// 參數：二叉樹根節點root
// 輸出：中間沒有空格，末尾不換行。
void InOrder(BTNode* root)
{
    // 請在這裡補充代碼，完成本關任務
    /********** Begin *********/
    if(root==NULL){
        return;
    }
    InOrder(root->lchild);
    printf("%c",root->data);
    InOrder(root->rchild);
    /********** End **********/
}