本次課程設(shè)計(jì)主要含三部分內(nèi)容，并且每一部分內(nèi)容獨(dú)立為一個(gè)小的課程設(shè)計(jì)

1.二叉樹的建立及其非遞歸的先序悠瞬、中序昵骤、后序遍歷；
2.二叉樹的層序遍歷
3.排序二叉樹的創(chuàng)建及中序遍歷輸出

• 首先我們來(lái)實(shí)現(xiàn)第一小部分的內(nèi)容交惯，先序遞歸構(gòu)建二叉樹并按非遞歸的方法對(duì)其進(jìn)行先序次泽、中序和后序遍歷。

接下來(lái)我們用下面這顆二叉樹作為我們示例進(jìn)行演示席爽，我們示例二叉樹長(zhǎng)這樣：

圖1 示例二叉樹

在前序遍歷生成二叉樹中意荤，我們用‘#’表示結(jié)點(diǎn)為NULL，因此前序遍歷生成二叉樹時(shí)的輸入序列應(yīng)該為："abd#h##k##cef##g##m##"只锻。通過(guò)CreateTree()函數(shù)我們就建立起了一顆如上圖所示的二叉樹玖像，然后就可以愉快的開始各種遍歷測(cè)試了，具體代碼如下：

#include<stdio.h>
#include<stdlib.h>

typedef struct treeNode{
    char data;
    struct treeNode*rchild, *lchild;
}TreeNode;

char str[] = "abd#h##k##cef##g##m##";
int pos = 0;

void CreateTree(TreeNode** T)
{//前序遞歸創(chuàng)建二叉樹
    char ch;
    //scanf("%c", &ch);//讀入字符
    ch = str[pos++];
    if (ch == '#')//.代表空子樹
        *T = NULL;
    else
    {
        *T = (TreeNode *)malloc(sizeof(TreeNode));
        if (!(*T))
        {
            printf("開辟內(nèi)存失敗\n");
            exit(1);
        }
        (*T)->data = ch;//給T賦值
        CreateTree(&(*T)->lchild);//給左子樹賦值
        CreateTree(&(*T)->rchild);//給右子樹賦值
    }
}

void preorderTraversal(TreeNode* root)
{
    if (!root)
        return;

    TreeNode* stack[10]; int top = -1;
    stack[++top] = root;

    while (top > -1)
    {
        TreeNode* temp = stack[top--];
        printf("%c ", temp->data);
        
        if (temp->rchild)
            stack[++top] = temp->rchild;
        if (temp->lchild)
            stack[++top] = temp->lchild;
    }

}
void midorderTraversal(TreeNode* root)
{//中序非遞歸遍歷二叉樹

    TreeNode *stack[10]; int top = -1;
    TreeNode *p = root;
    while (p != NULL || top > -1)
    {
        while (p != NULL)
        {
            stack[++top] = p;
            p = p->lchild;
        }
        if (top > -1)
        {
            p = stack[top];
            printf("%c ", p->data);
            --top;
            p = p->rchild;
        }
    }

}

typedef struct tempNode{
    TreeNode* btnode;
    bool isFirst;
}TempNode;
void postorderTraversal(TreeNode* root)
{//后續(xù)非遞歸遍歷二叉樹
    TempNode *stack[10]; int top = -1;
    TreeNode *p = root;
    TempNode *temp;
    while (p != NULL || top > -1)
    {
        while (p != NULL) //沿左子樹一直往下搜索齐饮，直至出現(xiàn)沒(méi)有左子樹的結(jié)點(diǎn)
        {
            TempNode *tempNode = new TempNode;
            tempNode->btnode = p;
            tempNode->isFirst = true;
            stack[++top] = tempNode;
            p = p->lchild;
        }
        if (top > -1)
        {
            temp = stack[top--];
            if (temp->isFirst == true)   //表示是第一次出現(xiàn)在棧頂
            {
                temp->isFirst = false;
                stack[++top] = temp;
                p = temp->btnode->rchild;
            }
            else  //第二次出現(xiàn)在棧頂
            {
                printf("%c ", temp->btnode->data);
                p = NULL;
            }
        }
    }
}

int choice()
{
    printf("*********歡迎來(lái)到二叉樹非遞歸遍歷演示界面************\n");
    printf("0-退出\n");
    printf("1-顯示前序非遞歸遍歷結(jié)果\n");
    printf("2-顯示中序非遞歸遍歷結(jié)果\n");
    printf("3-顯示后序非遞歸遍歷結(jié)果\n");

    int n;
    printf("請(qǐng)選擇:"); scanf("%d", &n);
    return n;
}

int main()
{
    //freopen("data.txt", "r", stdin);
    TreeNode* root;
    CreateTree(&root);
    int n;
    while (1)
    {
        n = choice();
        if (!(n >= 0 && n <= 3))
        {
            printf("菜單選擇錯(cuò)誤");
            continue;
        }
        if (n == 0)break;
        switch (n)
        {
        case 1:printf("前序遍歷結(jié)果:");
            preorderTraversal(root); break;
        case 2: printf("中序遍歷結(jié)果:");
            midorderTraversal(root);
            break;
        case 3:
            printf("\n后序遍歷結(jié)果:");
            postorderTraversal(root);
            break;
        }
        putchar('\n');
        system("pause"); system("cls");
    }
}//運(yùn)行結(jié)果ok 2019年5月26日15:36:55

以上代碼的運(yùn)行結(jié)果為：

圖2 前序遍歷

圖3 中序遍歷

圖4 后續(xù)遍歷

通過(guò)比較我在圖1中手動(dòng)遍歷的結(jié)果與程序運(yùn)行之后的結(jié)果捐寥，可以看到我們的代碼給出了正確的結(jié)果。

• 接下來(lái)我們?cè)倮^續(xù)第二個(gè)小設(shè)計(jì)——二叉樹的層序遍歷祖驱，這部分內(nèi)容比較簡(jiǎn)單握恳，沒(méi)什么好講述的直接貼代碼好了，代碼如下：

#include<stdio.h>
#include<stdlib.h>
#include<stack>
using namespace std;

typedef struct treeNode{
    char data;
    struct treeNode*rchild, *lchild;
}TreeNode;

void CreateTree(TreeNode** T)
{//前序遞歸創(chuàng)建二叉樹
    char ch;
    scanf("%c", &ch);//讀入字符
    if (ch == '#')//.代表空子樹
        *T = NULL;
    else
    {
        *T = (TreeNode *)malloc(sizeof(TreeNode));
        if (!(*T))
        {
            printf("開辟內(nèi)存失敗\n");
            exit(1);
        }
        (*T)->data = ch;//給T賦值
        CreateTree(&(*T)->lchild);//給左子樹賦值
        CreateTree(&(*T)->rchild);//給右子樹賦值
    }
}

void levelorderTraversal(TreeNode*root)
{//二叉樹從左至右捺僻，從上至下層次遍歷
    int front, rear;
    TreeNode*que[10];
    front = rear = 0;
    TreeNode*q;
    if (root)
    {
        rear = (rear + 1) % 10;
        que[rear] = root;
        while (front != rear)
        {
            front = (front + 1) % 10;
            q = que[front];
            printf("%c ", q->data);
            if (q->lchild)
            {
                rear = (rear + 1) % 10;
                que[rear] = q->lchild;
            }
            if (q->rchild)
            {
                rear = (rear + 1) % 10;
                que[rear] = q->rchild;
            }
        }
    }
}


int main()
{
    freopen("data.txt", "r", stdin);
    TreeNode* root;
    CreateTree(&root);

    printf("層序遍歷結(jié)果:");
    levelorderTraversal(root);

    putchar('\n');
}//運(yùn)行結(jié)果ok2019年5月26日14:37:20

這是一個(gè)完整可以執(zhí)行出結(jié)果的代碼睡互，不過(guò)我們重定義了標(biāo)準(zhǔn)輸入為“data.txt”，因此運(yùn)行這段代碼之前你需要在程序所在的文件夾內(nèi)創(chuàng)建名為“data.txt”的文件陵像，并將"abd#h##k##cef##g##m##"寫入該文件保存(字符串不含引號(hào))就珠，然后程序就可以直接從“data.txt”文本中讀入二叉樹的數(shù)據(jù)，并將按層序遍歷的結(jié)果輸出醒颖。演示結(jié)果為：

圖5 層序遍歷結(jié)果

• 完成了第二個(gè)關(guān)于層序遍歷的小任務(wù)妻怎，再讓我們來(lái)看最后一個(gè)與排序二叉樹有關(guān)的小任務(wù)。
  該任務(wù)比較簡(jiǎn)單泞歉，要求我們首先生成一顆二叉排序樹逼侦，然后對(duì)其進(jìn)行中序遍歷匿辩，輸出遞增序列。由于中序遍歷我們?cè)谌蝿?wù)一中已經(jīng)完成了榛丢，因此只需要構(gòu)建一個(gè)能生成二叉排序樹的函數(shù)就可以了铲球，這里我們采用遞歸的方式來(lái)實(shí)現(xiàn)，具體代碼如下：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef struct treeNode{
    int data;
    struct treeNode*rchild, *lchild;
}TreeNode;

bool CreateTree(TreeNode** root, int data)
{//二叉排序樹創(chuàng)建
    if ((*root) == NULL)    //如果為空晰赞，則創(chuàng)建一個(gè)節(jié)點(diǎn)
    {
        *root = (TreeNode *)malloc(sizeof(TreeNode));
        (*root)->data = data; ( *root)->lchild = (*root)->rchild = NULL;    //該節(jié)點(diǎn)為根節(jié)點(diǎn)稼病，左孩子和右孩子指針均置空
        return true;
    }
    else if (data == (*root)->data) //如果存在，則返回false
        return false;
    else if (data < (*root)->data)  //如果被插入數(shù)據(jù)較小掖鱼，則插入到左子樹
        return CreateTree(&((*root)->lchild), data);
    else    //如果被插入數(shù)據(jù)較大然走，則插入到右子數(shù)
        return CreateTree(&((*root)->rchild), data);
}

void midorderTraversal(TreeNode* root)
{//中序非遞歸遍歷二叉樹
    
    TreeNode *stack[10]; int top = -1;
    TreeNode *p = root;
    while (p != NULL ||  top > -1)
    {
        while (p != NULL)
        {
            stack[++top] = p;
            p = p->lchild;
        }
        if (top > -1)
        {
            p = stack[top];
            printf("%d ", p->data);
            --top;
            p = p->rchild;
        }
    }

}



int main()
{
    
    TreeNode* root = NULL;
    int data;
    srand((unsigned)time(NULL));
    printf("依次保存在排序樹中的值：");
    for (int i = 0; i < 10;)
    {//通過(guò)隨機(jī)生成數(shù)字建立二叉排序樹
        data = rand() % 20;
        
        if (CreateTree(&root, data))
        {
            printf("%d ", data);
            ++i;
        }
    }
    
    printf("\n中序遍歷結(jié)果:");
    midorderTraversal(root);

    putchar('\n');
}//運(yùn)行結(jié)果ok 2019年5月26日14:57:05

圖6 二叉排序樹演示結(jié)果

• 感想：本次課程設(shè)計(jì)比較簡(jiǎn)單，但是它一次性的總結(jié)了二叉樹的創(chuàng)建褐墅、非遞歸先序拆檬、中序、后序及層序遍歷妥凳，對(duì)掌握二叉樹的遍歷方法比較全面系統(tǒng)竟贯，因此有必要進(jìn)行總結(jié)，方便下次使用的時(shí)候直接參考或者拷貝代碼猾封。最后該課程設(shè)計(jì)也涉及了少量的二叉排序樹的知識(shí)澄耍，但是還不夠全面，對(duì)二叉排序樹的查找和結(jié)點(diǎn)刪除等相對(duì)復(fù)雜的點(diǎn)沒(méi)有過(guò)多涉及晌缘，以后還需要補(bǔ)充這方面的知識(shí)齐莲。