二叉树总结—

在C++编译器下可直接运行

#include <stdio.h>

#include <malloc.h>

//算法思想:先读入根结点数据,并且创建根结点,在读入左子树数据并创建左子树

//之后再读入右子树数据并创建右子树,在根结点左右子树创建好之后,最终将根结点返回。

typedef char ElemType;

typedef struct BiTNode

{

    ElemType data;

    struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

BiTNode *createBiTree()//该函数用来创建一棵树

{

    BiTNode *T = NULL;

    ElemType enter;

    enter = getchar();//可能读入空格，这样就结束输入

    if('@' != enter)

    {

        T = (BiTNode *)malloc(sizeof(BiTNode));

        T->data = enter;

        T->lchild = createBiTree();//结构体用点，结构体指针用箭头***********

        T->rchild = createBiTree();

    }

    return T;

}

void preOrder(BiTree T)

{

    if(T != NULL)

    {

        printf("%c ", T->data);

        preOrder(T->lchild);

        preOrder(T->rchild);

    }

}

void midOrder(BiTree T)

{

    if(T != NULL)

    {

        midOrder(T->lchild);

        printf("%c ", T->data);

        midOrder(T->rchild);

    }

}

//給定二叉鏈表的先序遍歷和中序遍歷，構造一顆二叉鏈表表示一棵樹

BiTNode *createBiTree1(ElemType preOrderList[],int preStartIndex,int preEndIndex,

                       ElemType inOrderList[],int inStartIndex,int inEndIndex)

{

    if(preStartIndex > preEndIndex)

    {

        return NULL;

    }

    BiTNode *t = (BiTNode *)malloc(sizeof(BiTNode));

    t->data = preOrderList[preStartIndex];

    int rootIndex;

    for(rootIndex = inStartIndex;rootIndex <= inEndIndex;rootIndex++)//在中序序列中查找跟節點位置

    {

        if(t->data == inOrderList[rootIndex])

            {

                break;

            }

    }

    int length = rootIndex - inStartIndex;

    t->lchild = createBiTree1(preOrderList,preStartIndex + 1,preStartIndex + length,

                              inOrderList,inStartIndex,rootIndex - 1);

    t->rchild = createBiTree1(preOrderList,preStartIndex + length + 1,preEndIndex,

                              inOrderList,rootIndex + 1,inEndIndex);

    return t;

}

//层次遍历

//输入层次遍历序列和中序序列创建一棵二叉树

//算法思想：先层次遍历确定（子树）根结点，再到中序序列中确定根位置，分出左右子树数列。

//然后确定层次遍历对左右子树序列，构建左右子树，重复上述步骤，构建整棵二叉树。

#define MAX_SIZE 100

BiTNode *createBiTree2(ElemType levelOrderList[],int levelStartIndex,int levelEndIndex,

                       ElemType inOrderList[],int inStartIndex,int inEndIndex)

{

    if(levelStartIndex > levelEndIndex)

    {

        return NULL;

    }

    BiTNode *t = (BiTNode *)malloc(sizeof(BiTNode));

    t->data = levelOrderList[levelStartIndex];

    int rootIndex;//在中序遍历序列中确定子树根结点位置

    for(rootIndex = inStartIndex;rootIndex < inEndIndex;rootIndex++)

    {

        if(inOrderList[rootIndex] == t->data)

        {

            break;

        }

    }

    ElemType lftLeverOrderList[MAX_SIZE];

    int lftLeverLength = 0;

    for(int j = levelStartIndex + 1;j <= levelEndIndex;j++)//找出左子树的层次遍历序列

    {

        for(int i = inStartIndex;i <= rootIndex - 1;i++)

        {

            if(inOrderList[i] == levelOrderList[j])

            {

                lftLeverOrderList[lftLeverLength++] = levelOrderList[j];

            }

        }

    }

    ElemType rgtLeverOrderList[MAX_SIZE];

    int rgtLeverLength = 0;

    for(int j = levelStartIndex + 1;j <= levelEndIndex;j++)//找出左子树的层次遍历序列

    {

        for(int i = rootIndex + 1;i <= inEndIndex;i++)

        {

            if(inOrderList[i] == levelOrderList[j])

            {

                rgtLeverOrderList[rgtLeverLength++] = levelOrderList[j];

            }

        }

    }

    t->lchild = createBiTree2(lftLeverOrderList,0,lftLeverLength - 1,

                              inOrderList,inStartIndex,rootIndex - 1);

    t->rchild = createBiTree2(rgtLeverOrderList,0,rgtLeverLength - 1,

                              inOrderList,rootIndex + 1,inEndIndex);

    return t;

}

////层次遍历

//void levelTravelBiTree(BiTree T)

//{

//    queue q;

//    initailQueue(q);

//    enQueue

//}

int main()

{

//    BiTree T = createBiTree();

//    preOrder(T);

//    midOrder(T);

//    char preOrderList[] = {'A','B','D','E','C','F','G'};

//    int preOrderListLength = 7;

    char leverOrderList[] = {'A','B','C','D','E','F','G'};

    int leverOrderListLength = 7;

    char inOrderList[] = {'D','B','E','A','F','C','G'};

    int inOrderListLength = 7;

    BiTree t = createBiTree2(leverOrderList,0,leverOrderListLength - 1,inOrderList,0,inOrderListLength - 1);

    preOrder(t);

    printf("\n");

    midOrder(t);

    return 0;

}
巴特西

二叉树总结——BiTree

在C++编译器下可直接运行

最新文章

热门文章
