二叉树结构的建立与遍历

小灰灰 2022-03-26 01:48 213阅读 0赞

**实验项目：**

**1****．****编写建立二叉树的二叉链表存储结构（左右链表示）的程序，并以适当的形式显示和保存二叉树；**

**2****．完成二叉树的****7****种遍历操作**

**3****．给定一个二叉树，** 编写算法完成下列应用:

（1）判断其是否为完全二叉树；

（2）求二叉树中任意两个结点的公共祖先。

输入示例（空子树以'\#'表示）：

ab\#\#c\#\#

#include <stdio.h>
    #include <stdlib.h>
    #define MAX_LEN 50
    /*二叉树的二叉链表结构*/
    typedef struct node
    {
        struct node *lchild;
        struct node *rchild;
        char data;
    }BTREE;
    /*栈的数组实现*/
    typedef struct
    {
        int top;
        BTREE *a[MAX_LEN]; //结构体数组，每个元素均为一个结点
    }Stack;
    /*队列的数组实现*/
    typedef struct
    {
        BTREE *a[MAX_LEN]; //结构体数组，每个元素均为一个结点
        int front;
        int rear;
    }Queue;
    /*为栈分配空间*/
    Stack *Createstack()
    {
        Stack *p;
        p = (Stack *)malloc(sizeof(Stack));
        p->top = -1;
        return p;
    }
    /*为队列分配空间*/
    Queue *Createqueue()
    {
        Queue *p;
        p = (Queue *)malloc(sizeof(Queue));
        p->front = 0;
        p->rear = 0;
        return p;
    }
    /*菜单*/
    int Menu()
    {
        int x;
        printf("\n\n");
        printf("1.先序遍历(递归)\n");
        printf("2.先序遍历(非递归)\n");
        printf("3.中序遍历(递归)\n");
        printf("4.中序遍历(非递归)\n");
        printf("5.后序遍历(递归)\n");
        printf("6.后序遍历(非递归)\n");
        printf("7.层序遍历\n");
        printf("8.判断其是否为完全二叉树\n");
        printf("9.求二叉树中任意两个结点的公共祖先\n");
        printf("10.退出\n\n");
        printf("请选择你要执行的操作：\n");
        scanf("%d",&x);
        return x;
    }
    /*先序遍历建立二叉树*/
    void CreateBT(BTREE **T)
    {
        char ch;
        scanf(" %c",&ch);
        if(ch=='#')
            *T = NULL;
        else
        {
            *T = (BTREE *)malloc(sizeof(BTREE));
            if(*T==NULL)
            {
                printf("No enough memory！\n");
                exit(0);
            }
            (*T)->data = ch;
            CreateBT(&((*T)->lchild));   //构造左子树
            CreateBT(&((*T)->rchild));   //构造右子树
        }
    }
    /*压栈*/
    void Push(Stack *s,BTREE *p)
    {
        s->top++;
        s->a[s->top] = p;
    }
    /*出栈*/
    BTREE *Pop(Stack *s)
    {
        BTREE *p;
        if (s->top == -1)
        {
        printf("栈空！\n");
        return NULL;
        }
        p = s->a[s->top];
        s->top--;
        return p;
    }
    /*栈顶*/
    BTREE *Top(Stack *s)
    {
        BTREE *p;
        if (s->top == -1)
        {
        printf("栈空！\n");
        return NULL;
        }
        p = s->a[s->top];
        return p;
    }
    /*输出结点数据*/
    void Printdata(char ch)
    {
        printf("%c  ",ch);
    }
    /*先序遍历二叉树递归算法*/
    void Preorder(BTREE *T)
    {
        if(T == NULL)
        {
            return;
        }
        Printdata(T->data);
        Preorder(T->lchild);
        Preorder(T->rchild);
    }
    /*中序遍历二叉树的递归算法*/
    void Inorder(BTREE *T)
    {
        if(T != NULL)
        {
            Inorder(T->lchild);
            Printdata(T->data);
            Inorder(T->rchild);
        }
    }
    /*后序遍历二叉树的递归算法*/
    void Postorder(BTREE *T)
    {
        if(T != NULL)
        {
            Postorder(T->lchild);
            Postorder(T->rchild);
            Printdata(T->data);
        }
    }
    /*先序遍历二叉树的非递归算法,栈顶保存当前结点的左子树*/
    void NPreorder(BTREE *T)
    {
         Stack *s;
         s = Createstack(); //创建一个栈
         while(T!=NULL||s->top!=-1)
         {
             while(T!=NULL)   //直到最左
             {
                 Printdata(T->data);
                 Push(s,T);
                 T=T->lchild;
             }
             if(s->top!=-1)
             {
                 T=Pop(s);
                 T=T->rchild;
             }
         }
    }
    /*中序遍历二叉树的非递归算法*/
    void NInorder(BTREE *T)
    {
         Stack *s;
         s = Createstack(); //创建一个栈
         while(T!=NULL||s->top!=-1)
         {
             while(T!=NULL)
             {
                 Push(s,T);
                 T=T->lchild;
             }
             if(s->top!=-1)
             {
                 T=Pop(s);
                 Printdata(T->data); //输出位置不同，其余与先序非递归遍历一致
                 T=T->rchild;
             }
         }
    }
    /*后序遍历的非递归算法，不设标志，设一变量*/
    void NPostorder(BTREE *T)
    {
        BTREE *p,*pr;
        Stack *s;
        s = Createstack(); //创建一个栈
        p = T;
        while(p!=NULL||s->top!=-1)
        {
            while(p!=NULL)
            {
                Push(s,p);
                pr = p->rchild;
                p = p->lchild;
                if(p==NULL)    //直到最底层，即后序遍历第一个
                p = pr;
            }
            p = Pop(s);
            Printdata(p->data);
            if(s->top!=-1&&Top(s)->lchild==p)
                p=Top(s)->rchild;  //遍历右子树
            else
                p=NULL;
        }
    }
    /*层序遍历，队列实现*/
    void Levelorder(BTREE *T)
    {
        Queue *p;
        p = Createqueue();  //创建一个队列
        if(T==NULL)
            return;
        p->rear++;   //二叉树非空，根指针入队
        p->a[p->rear]=T;
        while(p->front !=p->rear)  //循环直到队列不为空
        {
            p->front++;
            T=p->a[p->front];
            Printdata(T->data);
            if(T->lchild!=NULL) //若结点存在左孩子，将左孩子入队
            {
                p->rear++;
                p->a[p->rear]=T->lchild;
            }
            if(T->rchild!=NULL) //若结点存在右孩子，将右孩子入队
            {
                p->rear++;
                p->a[p->rear]=T->rchild;
            }
        }
    }
    /*判断二叉树是否为完全二叉树，采用层序遍历的方式*/
    int CompleteTree(BTREE *T)
    {
        Queue *p;
        p = Createqueue(); //创建队列
        if(T==NULL)
            return 0;
        p->rear++; //二叉树非空，根指针入队
        p->a[p->rear]=T;
        while(p->front !=p->rear)   //循环直到队列不空
        {
            if(T->lchild!=NULL&&T->rchild!=NULL) //若结点左右孩子都不为空，结点出队，左右孩子进队
            {
                p->front++;
                T=p->a[p->front];
                if(T->lchild!=NULL)
                {p->rear++;
                p->a[p->rear]=T->lchild;}
                if(T->rchild!=NULL)
                {p->rear++;
                p->a[p->rear]=T->rchild;}
            }
            if(T->lchild==NULL&&T->rchild!=NULL) //如果只有右子树没有左子树，不是
                return 0;
            if((T->lchild!=NULL&&T->rchild==NULL)||(T->lchild==NULL&&T->rchild==NULL))
                //左孩子不空右孩子空，或者左右都空,则该结点之后的所有结点必定是叶子结点
            {
                p->front++;
                while(p->front !=p->rear)
                {
                    T=p->a[p->front];
                    if(T->lchild==NULL&&T->rchild==NULL)
                        p->front++;
                    else
                        return 0;
                }
                return 1;
            }
        }
        return 1;
    }
    /*先序递归遍历，寻找数据对应的结点*/
    BTREE *Getnode(BTREE *m,char c)
    {
        BTREE *ret=NULL;
        if(m == NULL)
            return NULL;
        if(m->data==c)
            return m;
        else
        {
            ret =Getnode(m->lchild,c);
            if(ret!=NULL)
            {
                if(ret->data==c) //进入下一层递归前判断，若返回地址是要找的地址，则不用向下进行
                return ret;
            }
            ret =Getnode(m->rchild,c);
        }
        return ret;
    }
    /*先序递归遍历，寻找结点对应的数据*/
    char Getdata(BTREE *r,BTREE *T)
    {
        if(T == NULL)
            return ' ';
        if(T==r)
            return T->data;
        Getdata(r,T->lchild);
        Getdata(r,T->rchild);
    }
    /*递归寻找两个结点的公共祖先*/
    BTREE *Commonancestor(BTREE *T,BTREE *p,BTREE *q)
    {
        BTREE *left=T,*right=T;
        if(T==NULL||p==NULL||q==NULL)
            return NULL;
        if(p==T||q==T)
            return T;
        left=Commonancestor(T->lchild,p,q);
        right=Commonancestor(T->rchild,p,q);
        if(left!=NULL&&right!=NULL) //如果左右子树都能找到，那么当前的结点就是最近公共祖先
            return T;
        if(left==NULL)  //左子树没有，返回右子树查找结构
            return right;
        else   //否则返回左子树查找结果
            return left;
    }
    
    int main()
    {
        BTREE *T,*p,*q,*r;
        char ch,a,b,c;
        int flag;
        printf("请以先序遍历的方式输入二叉树(空子树以'#'表示)：\n");
        CreateBT(&T);
        while(1)
        {
            getchar();
            ch = Menu();
            switch(ch)
            {
                case 1:Preorder(T);
                break;
                case 2:NPreorder(T);
                break;
                case 3:Inorder(T);
                break;
                case 4:NInorder(T);
                break;
                case 5:Postorder(T);
                break;
                case 6:NPostorder(T);
                break;
                case 7:Levelorder(T);
                break;
                case 8:flag = CompleteTree(T);
                if(flag)
                    printf("该二叉树是完全二叉树！\n");
                else
                    printf("该二叉树不是完全二叉树！\n");
                break;
                case 9:
                printf("请输入第一个结点的数据：\n");
                scanf(" %c",&a);
                printf("请输入第二个结点的数据：\n");
                scanf(" %c",&b);
                p=Getnode(T,a);   //找到数据对应的结点
                q=Getnode(T,b);
                r=Commonancestor(T,p,q);
                printf("最近公共祖先是：%c\n",r->data);
                break;
                case 10:exit(0);
                default:printf("请输入正确序号!\n");
            }
        }
        return 0;
    }