二叉鏈的基本操作-有解無憂

【目的】

1. 領會二叉鏈存盤結構；掌握二叉樹的各種基本運算和構造二叉樹的演算法設計，

2. 領會線索二叉樹的構造程序以及構造線索二叉樹的演算法設計，
【內容及要求】撰寫程式實作兩種方式建立二叉樹：

撰寫一個程式btree.cpp，實作二叉樹的基本運算，并在此基礎上設計一個程式完成以下功能：(見教材P247，實驗題1)
(1)由圖7.33所示的二叉樹創建對應的二叉鏈存盤結構b，該二叉樹的括號表示串為“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”，
(2)輸出二叉樹b，(采用凹入表示法)
(3)輸出’H’結點的左、右孩子結點值，
(4)輸出二叉樹b的高度，
(5)釋放二叉樹b，
(6)利用先序序列和中序序列重新構造該
二叉樹(執行(5)的操作后再執行這一功能)，
并以括號表示法輸出該二叉樹，
(7)對該二叉樹進行中序線索化，

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define ElemType char
#define BTNode TBTNode
#define MaxSize 100
#define maxsize 100
typedef struct node
{
    ElemType data;
    int ltag, rtag; //線索的標記
    struct node *lchild;
    struct node *rchild;
} BTNode;

BTNode *pre; //全域變數的指標型別

char Pre[100];
char In[100];
int i = 0;

void CreateBTree(BTNode *&b, char *str) //創建二叉樹
{
    BTNode *St[MaxSize], *p;
    int top = -1, k, j = 0;
    char ch;
    b = NULL;
    ch = str[j];

    while (ch != '\0')
    {
        switch (ch)
        {
        case '(':
            top++;
            St[top] = p;
            k = 1;
            break;
        case ')':
            top--;
            break;
        case ',':
            k = 2;
            break;
        default:
            p = (BTNode *)malloc(sizeof(BTNode));
            p->data =https://www.cnblogs.com/billyme/p/ ch;
            p->lchild = p->rchild = NULL;
            if (b == NULL)
                b = p;
            else
            {
                switch (k)
                {
                case 1:
                    St[top]->lchild = p;
                    break;
                case 2:
                    St[top]->rchild = p;
                    break;
                }
            }
        }
        j++;
        ch = str[j];
    }
}

void DestoryBTree(BTNode *&b) //摧毀二叉樹
{
    if (b != NULL)
    {
        DestoryBTree(b->lchild);
        DestoryBTree(b->rchild);
        free(b);
    }
}

BTNode *FindNode(BTNode *b, ElemType x) //尋找值為x的結點
{
    BTNode *p;
    if (b == NULL)
        return NULL;
    else if (b->data =https://www.cnblogs.com/billyme/p/= x)
        return b;
    else
    {
        p = FindNode(b->lchild, x);
        if (p != NULL)
            return p;
        else
            return FindNode(b->rchild, x);
    }
}

BTNode *LchildNode(BTNode *p) //回傳左孩子結點
{
    return p->lchild;
}

BTNode *RchildNode(BTNode *p) //回傳右孩子結點
{
    return p->rchild;
}

int BTHeight(BTNode *b) //輸出高度
{
    int lchildh, rchildh;
    if (b == NULL)
        return 0;
    else
    {
        lchildh = BTHeight(b->lchild);
        rchildh = BTHeight(b->rchild);
        return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
    }
}

void DispBTree(BTNode *b) //輸出二叉樹
{
    if (b != NULL)
    {
        printf("%c", b->data);
        if (b->lchild != NULL || b->rchild != NULL)
        {
            printf("(");
            DispBTree(b->lchild);
            if (b->rchild != NULL)
                printf(",");
            DispBTree(b->rchild);
            printf(")");
        }
    }
}

void PreOrder(BTNode *b)
//先序遍歷的遞回形式
{
    if (b != NULL)
    {
        printf("%c ", b->data);
        Pre[i] = b->data;
        i++;
        PreOrder(b->lchild);
        PreOrder(b->rchild);
    }
}
void InOrder(BTNode *b)
//中序遍歷的遞回演算法
{
    if (b != NULL)
    {
        InOrder(b->lchild);
        In[i] = b->data;
        i++;
        printf("%c ", b->data);
        InOrder(b->rchild);
    }
}

BTNode *CreateBTree1(char *pre, char *in, int n)
//根據前序和中序推出二叉樹序列
{
    BTNode *b;
    char *p;
    int k;
    if (n <= 0)
        return NULL;
    b = (BTNode *)malloc(sizeof(BTNode));
    b->data = https://www.cnblogs.com/billyme/p/*pre;

    for (p = in; p < in + n; p++)
        if (*p == *pre)
            break;

    k = p - in;
    b->lchild = CreateBTree1(pre + 1, in, k);
    b->rchild = CreateBTree1(pre + k + 1, p + 1, n - k - 1);
    return b;
}

void Thread(TBTNode *&p) //生成二叉樹的線索
{
    if (p != NULL)
    {
        Thread(p->lchild);
        if (p->lchild == NULL) //節點左孩子為空時就直接指向前驅的節點線索
        {
            p->lchild = pre;
            p->ltag = 1;
        }
        else
            p->ltag = 0;

        if (pre->rchild == NULL) //右孩子為空時則指向后繼的結點線索位置
        {
            pre->rchild = p;
            pre->rtag = 1;
        }
        else
            pre->rtag = 0;

        pre = p;
        Thread(p->rchild);
    }
}

TBTNode *CreateThread(TBTNode *b) //把二叉鏈轉換成線索的形式
{
    TBTNode *root;
    root = (BTNode *)malloc(sizeof(BTNode));
    root->ltag = 0;
    root->rtag = 1;
    root->rchild = b;

    if (b == NULL)
        root->lchild = root; //原二叉鏈為空，則指標指回自己root
    else
    {
        root->lchild = b;
        pre = root;
        Thread(b);
        pre->rchild = root;
        pre->rtag = 1;
        root->rchild = pre;
    }
    return root;
}

void ThInOrder(TBTNode *tb)
{
    TBTNode *p = tb->lchild;

    while (p != tb)
    {
        while (p->ltag == 0)
            p = p->lchild;                      //找到中序的第一個節點
        printf("%c ", p->data);                 //如果無左孩子說明是已經到達了樹梢的葉子節點，直接輸出
        while (p->rtag == 1 && p->rchild != tb) //輸出在中序中的下一個節點值
        {
            p = p->rchild;
            printf("%c ", p->data);
        }
        p = p->rchild; //回溯到p的前一個節點或者是直接找下一個的右孩子節點
    }
}

void PreOrder2(BTNode *b, int n, int k)
//凹入法輸出二叉鏈
{
    if (b != NULL)
    {

        for (int j = 0; j < k; j++)
            printf(" ");
        printf("%c ", b->data);
        for (int j = 0; j < n; j++)
            printf("-");
        printf("\n");
        PreOrder2(b->lchild, n - 1, k + 1);
        PreOrder2(b->rchild, n - 1, k + 1);
    }
}

int main()
{
    char a[] = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
    int n = 14;
    BTNode *t, *b;
    CreateBTree(t, a);
    b = FindNode(t, 'H');
    printf("括號法輸出二叉樹：\n");
    DispBTree(t);
    putchar(10);
    printf("凹入表示法輸出二叉樹：\n");
    PreOrder2(t, 14, 1);
    putchar(10);
    printf("該結點的左孩子是 %c , 該孩子的右孩子是 %c \n", b->lchild->data, b->rchild->data);

    printf("該二叉樹的高度是 %d .\n", BTHeight(t));

    printf("先序遍歷的結果:");
    PreOrder(t);
    i = 0;
    printf("\n中序遍歷的結果:");
    InOrder(t);

    DestoryBTree(t);
    printf("\n成功銷毀二叉樹\n");
    printf("\n由先序序列和中序序列生成二叉樹：");
    b = CreateBTree1(Pre, In, n);
    putchar(10);
    DispBTree(b);
    putchar(10);

    printf("二叉樹的線索化\n");
    TBTNode *g;
    g = CreateThread(b);
    printf("成功創建線索化的二叉樹\n");
    printf("中序線索化遍歷二叉樹:");
    ThInOrder(g);
    putchar(10);

    putchar(10);

    system("pause");
    return 0;
}

喜歡的話，記得支持關注哦，關注我或者我的csdn博客：https://blog.csdn.net/horizon08/article/details/106254585

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/47548.html

標籤：其他

上一篇：graphx主點和虛點間如何更新和通信

下一篇：tarjan演算法求割點