数据结构实验三树与二叉树的常见操作

冷不防 2022-08-21 08:42 106阅读 0赞

数据结构 实验三 树与二叉树的常见操作

实验内容：

1．输入字符序列，建立二叉链表。

2．中序遍历二叉树:递归算法。

3．中序遍历二叉树:非递归算法。（最好也能实现先序，后序非递归算法）

4．求二叉树的高度 。

5．求二叉树的叶子个数。

\*6．将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。

\*7．建立中序线索二叉树，并实现中序遍历。

8．借助队列实现二叉树的层次遍历。

9．在主函数中设计一个简单的菜单，分别调试上述算法。

\*10．综合训练：为N个权值设计哈夫曼编码。

代码实现：

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    
    #define Size 100
    
    using namespace std;
    
    typedef char ElemType;
    
    typedef struct BiNode
    {
        ElemType data;
        struct BiNode*lchild,*rchild;
    } BiNode,*BiTree;
    
    void CreateBiTree1(BiTree *t)  ///指针实现创建一棵二叉树
    {
        char ch;
        ch=getchar();
        if(ch==' ')
            *t=NULL;
        else
        {
            (*t)=new BiNode;
            (*t)->data = ch;
            CreateBiTree1(&((*t)->lchild));
            CreateBiTree1(&((*t)->rchild));
        }
    }
    
    void CreateBiTree2(BiTree &t)  ///引用实现创建一棵二叉树
    {
        char ch;
        scanf("%c",&ch);
        if(ch==' ')
            t=NULL;
        else
        {
            t=(BiTree)malloc(sizeof(BiNode));
            t->data=ch;
            CreateBiTree2(t->lchild);
            CreateBiTree2(t->rchild);
        }
    }
    
    BiTree CreateBiTree3()  ///返回值为一棵二叉树指针
    {
        BiTree t;
        char ch;
        ch=getchar();
        if(ch!=' ')
        {
            t=new BiNode;
            t->data=ch;
            t->lchild=CreateBiTree3();
            t->rchild=CreateBiTree3();
        }
        else t=NULL;
        return t;
    }
    
    void PreOrder(BiTree t) ///递归先序遍历一棵二叉树
    {
        if(t!=NULL)
        {
            printf("%c ",t->data);
            PreOrder(t->lchild);
            PreOrder(t->rchild);
        }
    }
    
    void InOrder(BiTree t) ///递归中序遍历一棵二叉树
    {
        if(t!=NULL)
        {
            InOrder(t->lchild);
            printf("%c ",t->data);
            InOrder(t->rchild);
        }
    }
    
    void PasOrder(BiTree t) ///递归后序遍历一棵二叉树
    {
        if(t!=NULL)
        {
            PasOrder(t->lchild);
            PasOrder(t->rchild);
            printf("%c ",t->data);
        }
    }
    
    void PreOrderfi(BiTree t) ///非递归先序遍历一个二叉树
    {
        BiTree S[Size];
        int top=-1;
        BiTree p=t;
        while(p!=NULL || top>-1)
        {
            while(p!=NULL)
            {
                cout<<p->data<<" ";
                top++;
                S[top]=p;
                p=p->lchild;
            }
            if(top>-1)
            {
                p=S[top];
                top--;
                p=p->rchild;
            }
        }
    }
    
    void InOrderfi(BiTree t) ///非递归中序遍历一棵二叉树
    {
        BiTree s[Size];
        int top=-1;
        BiTree current;
        current=t;
        while(current!=NULL || top>-1)
        {
            while(current!=NULL)
            {
                top++;
                s[top]=current;
                current=current->lchild;
            }
            if(top>-1)
            {
                current=s[top];
                cout<<current->data<<" ";
                top--;
                current=current->rchild;
            }
        }
    }
    
    void PasOrderfi(BiTree t)  ///非递归后序遍历一棵二叉树
    {
        struct
        {
            BiTree pp;///*模拟三次相遇，tag==0，表示第一次相遇，tag==1，表示第二次相遇（即把其置1），第三次即判断tag的值是否为1，若为1，则表示第三次相遇*///
            int tag;
        } SS[Size];
        int top;
        BiTree p;
        top=0;
        p=t;
        while(p || top>0)
        {
            while(p)
            {
                top++;
                SS[top].tag=0;
                SS[top].pp=p;
                p=p->lchild;
            }
            if(top>0)
            {
                if(SS[top].tag==0)
                {
                    SS[top].tag=1;
                    p=SS[top].pp;
                    p=p->rchild;
                }
                else
                {
                    p=SS[top].pp;
                    cout<<p->data<<" ";
                    top--;
                    p=NULL;
                }
            }
        }
    }
    
    int Depth(BiTree t)///计算树的深度
    {
        int l,r;
        if(t==NULL) return 0;
        else
        {
            l=Depth(t->lchild);
            r=Depth(t->rchild);
            if(l>r)
                return l+1;
            else return r+1;
        }
    }
    
    void PreOrderYezi(BiTree t,int & yezinum) ///先序实现计算叶子节点数
    {
        if(t!=NULL)
        {
            if( t->lchild ==NULL && t->rchild==NULL)
            {
                yezinum++;
            }
            PreOrderYezi(t->lchild,yezinum);
            PreOrderYezi(t->rchild,yezinum);
        }
    }
    
    void Menu()
    {
        cout<<"WELCOME!"<<endl;
        cout<<"0.Break!"<<endl;
        cout<<"1.Create BiTree by Method1."<<endl;
        cout<<"2.Create BiTree by Method2."<<endl;
        cout<<"3.Create BiTree by Method3."<<endl;
        cout<<"4.Digui PreOrder Travel."<<endl;
        cout<<"5.Digui InOrder Travel."<<endl;
        cout<<"6.Digui PasOrder Travel."<<endl;
        cout<<"7.FiDigui PreOrder Travel."<<endl;
        cout<<"8.FiDigui InOrder Travel."<<endl;
        cout<<"9.FiDigui PasOrder Travel."<<endl;
        cout<<"10.The Depth."<<endl;
        cout<<"11.The leaf number."<<endl;
    }
    
    int main()
    {
        BiTree T;
        int high,yezinum;
        int casenum;
        Menu();
        cin>>casenum;
        while(casenum!=0)
        {
            switch(casenum)
            {
            case 1:
                getchar();
                cout<<"Create BiTree Method 1:"<<endl;
                CreateBiTree1(&T);
                cout<<"Create Over!"<<endl;
                cin>>casenum;
                break;
    
            case 2:
                getchar();
                cout<<"Create BiTree Method 2:"<<endl;
                CreateBiTree2(T);
                cout<<"Create Over!"<<endl;
                cin>>casenum;
                break;
    
            case 3:
                getchar();
                cout<<"Create BiTree Method 3:"<<endl;
                T=CreateBiTree3();
                cout<<"Create Over!"<<endl;
                cin>>casenum;
                break;
    
            case 4:
                getchar();
                cout<<"DI GUI XIAN XU: "<<endl;
                PreOrder(T);
                cout<<endl;
                cin>>casenum;
                break;
    
            case 5:
                getchar();
                cout<<"DI GUI ZHONG XU: "<<endl;
                InOrder(T);
                cout<<endl;
                cin>>casenum;
                break;
    
            case 6:
                getchar();
                cout<<"DI GUI HOU XU: "<<endl;
                PasOrder(T);
                cout<<endl;
                cin>>casenum;
                break;
    
            case 7:
                getchar();
                cout<<"FEI DI GUI XIAN XU: "<<endl;
                PreOrderfi(T);
                cout<<endl;
                cin>>casenum;
                break;
    
            case 8:
                getchar();
                cout<<"FEI DI GUI ZHONG XU: "<<endl;
                InOrderfi(T);
                cout<<endl;
                cin>>casenum;
                break;
    
            case 9:
                getchar();
                cout<<"FEI DI GUI HOU XU: "<<endl;
                PasOrderfi(T);
                cout<<endl;
                cin>>casenum;
                break;
    
            case 10:
                getchar();
                high=Depth(T);
                cout<<"THE TREE's HIGHTH IS: "<<high<<endl;
                cin>>casenum;
                break;
    
            case 11:
                getchar();
                yezinum=0;
                PreOrderYezi(T,yezinum);
                cout<<"THE TREE's YEZI IS: "<<yezinum<<endl;
                cin>>casenum;
                break;
    
            default :cin>>casenum;
                break;
            }
        }
        return 0;
    }