静态创建二叉树及其遍历

佚名 5年前 (2019-11-03) 算法 1395人围观抢沙发百度已收录

我们以这个二叉树为例

1.构造二叉树的链式存储结构

1 struct BTNode{
2    char data;     //结点数据域
3    struct BTNode * pLchild;  //左孩子指针-->指向左孩子
4    struct BTNode * pRchild;  //右孩子指针-->指向右孩子
5 };

View Code

2.静态的创建二叉树

struct BTNode * createBTree()
{
    struct BTNode* pa = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode* pb = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode* pc = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode* pd = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode* pe = (struct BTNode*)malloc(sizeof(struct BTNode));
    pa->data = 'A';
    pb->data = 'B';
    pc->data = 'C';
    pd->data = 'D';
    pe->data = 'E';

    pa->pLchild = pb;
    pb->pLchild = pb->pRchild = NULL;
    pa->pRchild = pc;
    pc->pLchild = pd;
    pc->pRchild = NULL;
    pd->pLchild = NULL;
    pd->pRchild = pe;
    pe->pLchild = pe->pRchild = NULL;

    return pa;

}

View Code

3.先序遍历二叉树(递归方式)

void preBTree(struct BTNode * PT)
{
    if(PT!=NULL)
    {
        printf("%c\n",PT->data);
        preBTree(PT->pLchild);
        preBTree(PT->pRchild);
    }

    //先序访问的步骤
    //先访问根节点
    //再先序访问左子树
    //再先序访问右子树
}

View Code

3.中序遍历二叉树(递归方式)

 1 void midBTree(struct BTNode * PT)
 2 {
 3    //中序遍历二叉树的步骤
 4    //中序遍历左子树
 5    //访问根节点
 6    //中序遍历右子树
 7     if(PT!=NULL)
 8     {
 9         if(PT->pLchild!=NULL)
10         {
11            midBTree(PT->pLchild);//中序遍历左子树
12         }
13         printf("%c\n",PT->data); //访问根节点
14         if(PT->pRchild!=NULL)
15         {
16             midBTree(PT->pRchild);//中序遍历右子树
17         }
18     }
19 }

View Code

4.后序遍历二叉树（递归方式）

void lastBTree(struct BTNode * PT)
{
   //后序遍历二叉树的步骤
   //后序遍历左子树
   //后序遍历右子树
   //访问根节点
    if(PT!=NULL)
    {
        if(PT->pLchild!=NULL)
        {
            lastBTree(PT->pLchild); //后序遍历左子树
        }
        if(PT->pRchild!=NULL)
        {
            lastBTree(PT->pRchild);//后序遍历右子树
        }
        printf("%c\n",PT->data);//访问根节点
    }
}

View Code

完整代码：

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

//二叉树的链式存储结构
struct BTNode{
   char data;
   struct BTNode * pLchild;
   struct BTNode * pRchild;
};

struct BTNode * createBTree();
void preBTree(struct BTNode * PT);
void midBTree(struct BTNode * PT);
void postBTree(struct BTNode * PT);

//主函数
int main()
{
   struct BTNode *PT = createBTree();
   preBTree(PT);
   printf("\n");
   midBTree(PT);
   printf("\n");
   postBTree(PT);

}
//后序遍历二叉树
void postBTree(struct BTNode * PT)
{
    if(PT!=NULL)
    {
        if(PT->pLchild!=NULL)
        {
            postBTree(PT->pLchild);
        }
        if(PT->pRchild!=NULL)
        {
            postBTree(PT->pRchild);
        }
        printf("%c\n",PT->data);
    }
}
//中序遍历二叉树
void midBTree(struct BTNode * PT)
{
    if(PT!=NULL)
    {
        if(PT->pLchild!=NULL)
        {
           midBTree(PT->pLchild);
        }
        printf("%c\n",PT->data);
        if(PT->pRchild!=NULL)
        {
            midBTree(PT->pRchild);
        }
    }
}

//后序遍历二叉树
void preBTree(struct BTNode * PT)
{
    if(PT!=NULL)
    {
        printf("%c\n",PT->data);
        preBTree(PT->pLchild);
        preBTree(PT->pRchild);
    }


    //先访问根节点
    //再先序访问左子树
    //再先序访问右子树
}
//创建一个二叉树
struct BTNode * createBTree()
{
    struct BTNode* pa = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode* pb = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode* pc = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode* pd = (struct BTNode*)malloc(sizeof(struct BTNode));
    struct BTNode* pe = (struct BTNode*)malloc(sizeof(struct BTNode));
    pa->data = 'A';
    pb->data = 'B';
    pc->data = 'C';
    pd->data = 'D';
    pe->data = 'E';

    pa->pLchild = pb;
    pb->pLchild = pb->pRchild = NULL;
    pa->pRchild = pc;
    pc->pLchild = pd;
    pc->pRchild = NULL;
    pd->pLchild = NULL;
    pd->pRchild = pe;
    pe->pLchild = pe->pRchild = NULL;

    return pa;

}