二叉树的各种操作

旧城等待， 2022-08-27 10:44 157阅读 0赞

数据结构实验，主要是对二叉树的各种操作方法。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define TRUE  1
    #define FALSE 0
    #define maxsize 100
    typedef struct TreeNode
    {
        char data;
        struct TreeNode *left;
        struct TreeNode *right;
        int visit;//在遍历的时候用于标记此结点的左右结点是否都已经访问过
    }TreeNode,BinaryTree;
    
    
    //void CreateBiTree(BinaryTree **T,char *definition);//创建树
    void CreateBiTree(BinaryTree **T);//创建树
    int EditTreeNode(BinaryTree *T,int position,char NEW);//修改树的结点
    void DeleteTree(BinaryTree *T);//删除树
    void PrintTree(BinaryTree *T,int layer);//按照树的形状打印树
    int BiTreeDepth(BinaryTree *T);//求树的高度
    int BiTreeDepth_recursive(BinaryTree *T);//递归求树的高度
    int LeafNumber(BinaryTree *T);//求叶子的数目
    int LeafNumber_recursive(BinaryTree *T);//递归求叶子的数目
    void PreOrderTraverse(TreeNode *T,void (*visit)());//前序遍历
    void PreOrderTraverse_recursive(TreeNode *T,void (*visit)());//递归求前序遍历
    void InOrderTraverse(TreeNode *T,void (*visit)());//中序遍历
    void InOrderTraverse_recursive(TreeNode *T,void (*visit)());//递归求中序遍历
    void PostOrderTraverse(TreeNode *T,void (*visit)());//后序遍历
    void PostOrderTraverse_recursive(TreeNode *T,void (*visit)());//递归求后序遍历
    void LevelOrderTraverse(TreeNode *T,void (*visit)());//层次遍历
    
    void display(int e);
    void menu(void);
    TreeNode *Traverse(TreeNode *Node);
    
    char definition[maxsize];
    int i=0;
    int main()
    {
        BinaryTree *T=NULL;
        int op=0;
        do
        {
            system("cls");
            menu();
            op=0;
            printf("          Please input your option[0-12]:");
            scanf("%d",&op);
            switch(op)
            {
                case 0:
                    break;
                case 1:
                {
                    if(T)
                    {
                        printf("该二叉树已经存在,是否确认覆盖重新创建？1:是;2:否：");
                        int ok=0;
                        scanf("%d",&ok);
                        if(ok==0)
                        {
                            system("pause");
                            break;
                        }
                        else//free掉二叉树各个节点
                        {
                            BinaryTree *stack[maxsize],*p;
                            int top=-1;
                            stack[++top]=T;
                            while(top>-1)
                            {
                                p=stack[top--];
                                if(p->right)stack[++top]=p->right;
                                if(p->left)stack[++top]=p->left;
                                free(p);
                            }
                            T=NULL;
                        }
                    }
                    printf("请在一行内输入各个结点代号大写字母值，空结点用空格代替，请勿输入其他字符，树将以前序遍历方式建立\n");
                    //char definition[maxsize];
                    memset(definition,maxsize,'\0');
                    i=0;
                    getchar();
                    gets(definition);//printf("\n%s\n",definition);
                    //scanf("%s",definition);
                    //CreateBiTree(&T,definition);
                    CreateBiTree(&T);
                    printf("恭喜创建成功！\n");
                    system("pause");
                    break;
                }
                case 2:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    int position=0;
                    char NEW;
                    printf("请按照树从左至右、从上到下的编号顺序，输入你要修改值的结点编号：");
                    scanf("%d",&position);
                    getchar();
                    printf("\n请此处的新值[单个字母]：");
                    scanf("%c",&NEW);
                    int ok=EditTreeNode(T,position,NEW);
                    if(ok==FALSE)printf("你输入的位置信息有误！\n");
                    else printf("修改成功！\n");
                    system("pause");
                    break;
                }
                case 3:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    printf("该树的深度是：%d\n",BiTreeDepth(T));
                    system("pause");
                    break;
                }
                case 4:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    printf("该二叉树叶子数为：%d\n",LeafNumber(T));
                    system("pause");
                    break;
                }
                case 5:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    PreOrderTraverse(T,display);
                    printf("\n");
                    system("pause");
                    break;
                }
                case 6:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    InOrderTraverse(T,display);
                    printf("\n");
                    system("pause");
                    break;
                }
                case 7:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    PostOrderTraverse(T,display);
                    printf("\n");
                    system("pause");
                    break;
                }
                case 8:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    LevelOrderTraverse(T,display);
                    printf("\n");
                    system("pause");
                    break;
                }
                case 9:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    DeleteTree(T);
                    T=NULL;
                    printf("删除成功！\n");
                    system("pause");
                    break;
                }
                case 10:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    printf("提示：此处的二叉树是横向输出，树的每一行对应着这里的相应列：\n");
                    PrintTree(T,0);
                    system("pause");
                    break;
                }
                case 11:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    printf("该树的深度是：%d\n",BiTreeDepth_recursive(T));
                    system("pause");
                    break;
                }
                case 12:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    printf("该二叉树叶子数为：%d\n",LeafNumber_recursive(T));
                    system("pause");
                    break;
                }
                case 13:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    PreOrderTraverse_recursive(T,display);
                    printf("\n");
                    system("pause");
                    break;
                }
                case 14:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    InOrderTraverse_recursive(T,display);
                    printf("\n");
                    system("pause");
                    break;
                }
                case 15:
                {
                    if(!T)
                    {
                        printf("该二叉树不存在！\n");
                        system("pause");
                        break;
                    }
                    PostOrderTraverse_recursive(T,display);
                    printf("\n");
                    system("pause");
                    break;
                }
                default :
                    printf("wrong input.\n");
                    system("pause");
                    break;
            }
        }while(op);
        return 0;
    }
    
    
    void CreateBiTree(BinaryTree **T)
    {
        if(definition[i]==' ')*T=NULL;
        else
        {
            *T=(BinaryTree *)malloc(sizeof(BinaryTree));
            (*T)->visit=0;
            (*T)->data=definition[i++];
            CreateBiTree(&((*T)->left));
            i++;
            CreateBiTree(&((*T)->right));
        }
    }
    int EditTreeNode(BinaryTree *T,int position,char NEW)//修改树的结点
    {
        BinaryTree *quene[maxsize],**p;
        int front=0,back=0;
        quene[back++]=T;
        int count=0;
        while(front<back)
        {
            p=&quene[front++];
            ++count;
            if(count==position)break;
            if((*p)->left)quene[back++]=(*p)->left;
            if((*p)->right)quene[back++]=(*p)->right;
        }
        if(count<position)return FALSE;
        (*p)->data=NEW;
        return TRUE;
    }
    void DeleteTree(BinaryTree *T)//删除树
    {
        if(T)
        {
            BinaryTree *p=NULL;
            p=T;
            DeleteTree(T->left);
            DeleteTree(T->right);
            free(p);
            p=NULL;
        }
    }
    void PrintTree(BinaryTree *T,int layer)//按照树的形状打印树
    {
         int i;
         if(T==NULL)
             return;
         PrintTree(T->right,layer+1);
         for(i=0;i<layer;i++)
             printf("  ");
         printf("%c\n",T->data);
         PrintTree(T->left,layer+1);
    }
    int BiTreeDepth(BinaryTree *T)//求树的高度
    {
        BinaryTree *stack[maxsize],*p=T;
        int tag[maxsize];
        int top=-1;
        int count=0;
        while(p || top>-1)
        {
            while(p)
            {
                stack[++top]=p;
                tag[top]=0;
                p=p->left;
            }
            if(tag[top]==1)
            {
                count=count>(top+1)?count:(top+1);
                --top;
                p=NULL;
            }
            else
            {
                p=stack[top];
                tag[top]=1;
                p=p->right;
            }
        }
        return count;
    }
    int BiTreeDepth_recursive(BinaryTree *T)//递归求树的高度
    {
        if(T==NULL)return 0;
        else
        {
            int h_left=0,h_right=0;
            if(T->left==NULL && T->right==NULL)return 1;
            h_left=BiTreeDepth_recursive(T->left);
            h_right=BiTreeDepth_recursive(T->right);
            return h_left>h_right?(h_left+1):(h_right+1);
        }
    }
    int LeafNumber(BinaryTree *T)//求叶子的数目
    {
        BinaryTree *stack[maxsize],*p;
        int top=-1;
        int count=0;
        if(T)
        {
            stack[++top]=T;
            while(top>-1)
            {
                p=stack[top--];
                if(p->right)stack[++top]=p->right;
                if(p->left)stack[++top]=p->left;
                if(p->left==NULL && p->right==NULL)++count;
            }
            return count;
        }
    
    }
    int LeafNumber_recursive(BinaryTree *T)//递归求叶子的数目
    {
        if(T==NULL)return 0;
        else
        {
            int left=0,right=0;
            if(T->left==NULL && T->right==NULL)return 1;
            if(T->left)
            left=LeafNumber_recursive(T->left);
            if(T->right)
            right=LeafNumber_recursive(T->right);
            return left+right;
        }
    }
    void PreOrderTraverse(BinaryTree *T,void (*visit)())//前序遍历
    {
        BinaryTree *stack[maxsize],*p;
        int top=-1;
        if(T)
        {
            stack[++top]=T;
            while(top>-1)
            {
                p=stack[top--];
                visit(p->data);
                if(p->right)stack[++top]=p->right;
                if(p->left)stack[++top]=p->left;
            }
        }
    }
    void PreOrderTraverse_recursive(BinaryTree *T,void (*visit)())//递归求前序遍历
    {
        if(T)
        {
            visit(T->data);
            PreOrderTraverse_recursive(T->left,display);
            PreOrderTraverse_recursive(T->right,display);
        }
    }
    void InOrderTraverse(BinaryTree *T,void (*visit)())//中序遍历
    {
        BinaryTree *stack[maxsize],*p;
        int top=-1;
        while(top>-1 || T!=NULL)
        {
            while(T)
            {
                stack[++top]=T;
                T=T->left;
            }
            if(top>-1)
            {
                p=stack[top--];
                visit(p->data);
                T=p->right;
            }
        }
    }
    void InOrderTraverse_recursive(BinaryTree *T,void (*visit)())//递归求中序遍历
    {
        if(T)
        {
            InOrderTraverse_recursive(T->left,display);
            visit(T->data);
            InOrderTraverse_recursive(T->right,display);
        }
    }
    void PostOrderTraverse(BinaryTree *T,void (*visit)())//后序遍历
    {
        BinaryTree *stack[maxsize],*p=NULL;
        int top=-1;
        if(T)stack[++top]=T;
        while(top>-1)
        {
            p=stack[top--];
            if(p->visit)visit(p->data);
            else
            {
                p->visit=1;
                stack[++top]=p;
                if(p->right)
                {
                    p->right->visit=0;
                    stack[++top]=p->right;
                }
                if(p->left)
                {
                    p->left->visit=0;
                    stack[++top]=p->left;
                }
            }
        }
    
    }
    void PostOrderTraverse_recursive(BinaryTree *T,void (*visit)())//递归求后序遍历
    {
        if(T)
        {
            PostOrderTraverse_recursive(T->left,display);
            PostOrderTraverse_recursive(T->right,display);
            visit(T->data);
        }
    }
    void LevelOrderTraverse(BinaryTree *T,void (*visit)())//层次遍历
    {
        BinaryTree *quene[maxsize],*p;
        int front=0,back=0;
        quene[back++]=T;
        while(front<back)
        {
            p=quene[front++];
            visit(p->data);
            if(p->left)quene[back++]=p->left;
            if(p->right)quene[back++]=p->right;
        }
    }
    
    
    
    void menu(void)
    {
        printf("\n\n");
        printf("      Menu for Binary Tree On Sequence Structure \n");
        printf("------------------------------------------------------------------\n");
        printf("    	  1.  创建二叉树              9. 删除二叉树\n");
        printf("    	  2.  修改二叉树             10. 显示二叉树\n");
        printf("    	  3.  非递归求树深度         11. 递归求树深度\n");
        printf("    	  4.  非递归求树叶子数       12. 递归求树叶子数 \n");
        printf("    	  5.  非递归前序遍历         13. 递归前序遍历\n");
        printf("    	  6.  非递归中序遍历         14. 递归中序遍历\n");
        printf("    	  7.  非递归后序遍历         15. 递归后序遍历\n");
        printf("    	  8.  层次遍历二叉树          0.退出(Exit)\n");
        printf("------------------------------------------------------------------\n");
    }
    void display(int e)
    {
        printf("%c ",e);
    }