ex3.c

数据结构的实验

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20
#define NULL 0
typedef char TElemType;
typedef int Status;
typedef struct BiTNode  /*二叉树二叉链表示*/
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree stack[MAX];
int top=0;
void Push(BiTree T) /*压栈*/
{
    if(top<=(MAX-2))
    {
        top++;
        stack[top]=T;
    }
    else
        printf("Stack Full");
}
BiTree Pop()  /*弹出栈顶元素*/
{
    if(top!=0)
    {
        top--;
        return(stack[top+1]);
    }
    else
    {
        printf("Stack Empty");
        return '\0';
    }
}
Status CreateBiTree(BiTree *T)   /*建立二叉树*/
{
    char ch;
    scanf("%c",&ch);  /*先序输入结点值*/
    if(ch=='#') (*T)=NULL;  /*空树*/
    else
    {
        (*T)=(BiTNode*)malloc(sizeof(BiTNode));
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
    return 1;/*创建成功*/
}
void PreOrderTraverse(BiTree T) /*先序遍历非递归算法*/
{
    while(!(T==NULL&&top==0))
    {
        if(T!=NULL)
        {
            printf("%2c",T->data);
            Push(T);
            T=T->lchild;
        }
        else
        {
            T=Pop();
            T=T->rchild;
        }
    }
}
void PreOrder(BiTree T) /*先序遍历递归算法*/
{
    if(T)
    {
        printf("%2c",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
void InOrderTraverse(BiTree T) /*中序遍历非递归算法*/
{
    while(!(T==NULL&&top==0))
    {
        while(T!=NULL)
        {
            Push(T);
            T=T->lchild;
        }
        T=Pop();
        printf("%2c",T->data);
        T=T->rchild;
    }
}
void InOrder(BiTree T) /*中序遍历递归算法*/
{
    if(T)
    {   InOrder(T->lchild);
        printf("%2c",T->data);
        InOrder(T->rchild);
    }
}
void PostOrderTraverse(BiTree T) /*后序遍历非递归算法*/
{
    BiTree P;
    int tag[MAX];/*存放左右子树标志，1为右，0为左*/
    P=T;
    do
    {
        while(P!=NULL)   /*扫描左节点*/
        {
            top++;
            stack[top]=P;
            tag[top]=0;
            P=P->lchild;
        }
        if(top>0)
        {
            P=stack[top];
            if(tag[top]==1)
            {
                top--;
                printf("%2c",P->data);
            }
            if(top>0)
            {
                P=P->rchild;
                tag[top]=1;
            }
        }
    }while(P!=NULL&&top!=0);
}
void PostOrder(BiTree T) /*后序遍历递归算法*/
{
    if(T)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%2c",T->data);
    }
}
void LevelOrder(BiTree T) /*层次遍历非递归算法*/
{
    BiTree  Queue[MAX],b;
    int front=0,rear=0;
    if(T)
    {
        Queue[rear++]=T;
        while(front!=rear)
        {
            b=Queue[front++];
            printf("%2c",b->data);
            if(b->lchild!=NULL) Queue[rear++]=b->lchild;
            if(b->rchild!=NULL) Queue[rear++]=b->rchild;
        }
    }
}
int depth(BiTree T)   /*求二叉树深度*/
{
    int dep1,dep2;
    if(T==NULL) return 0;
    else
    {
        dep1=depth(T->lchild);
        dep2=depth(T->rchild);
        return dep1>dep2?dep1+1:dep2+1;
    }
}
int judgeComBTree(BiTree root)/*判断完全二叉树*/
{
    if(!root)
    return 0;
    if(!root->lchild && !root->rchild)
    return 1;
    return judgeComBTree(root->lchild) && judgeComBTree(root->rchild);
}
void destroy(BiTree *T)  /*删除二叉树*/
{
    if ( (*T)!= NULL )
    {
        destroy ( &(*T)->lchild );
        destroy ( &(*T)->rchild );
        free((*T));
    }
}
void exchange(BiTree T) /*交换左右子树*/
{
    BiTree temp;
    if(T!=NULL)
    {
        exchange(T->lchild);
        exchange(T->rchild);
        temp=T->lchild;
        T->lchild=T->rchild;
        T->rchild=temp;
    }
}
int nodenum(BiTree T)  /*计算总结点数目*/
{
    int n1,n2;
    if(T==NULL) return (0);
    else if(T->lchild==NULL&&T->rchild==NULL) return(1);
    else
    {
       n1=nodenum(T->lchild);
       n2=nodenum(T->rchild);
       return(n1+n2+1);
    }
}
int leafnum(BiTree T)  /*计算叶结点数目*/
{
    int n1,n2;
    if(T==NULL) return(0);
    else if(T->lchild==NULL&&T->rchild==NULL) return(1);
    else
    {
       n1=leafnum(T->lchild);
       n2=leafnum(T->rchild);
       return(n1+n2);
    }

}
void disp(BiTree T)   /*凹入表示法打印二叉树*/
{
    BiTree P;
    int level[100],n,i;/*场宽数组,根节点场宽为6，左右子树场宽增3*/
    if(T!=NULL)
    {
        printf("Show BiTree:\n");
        top=1;
        stack[top]=T;  /*根入栈*/
        level[top]=3;
        while(top>0)
        {
            P=stack[top];
            n=level[top];
            for(i=1;i<=n;i++)
            {
                printf(" ");
            }
            printf("%c\n",P->data);
            top--;
            if(P->rchild!=NULL)
            {
                top++;
                stack[top]=P->rchild;
                level[top]=n+3;
            }
            if(P->lchild!=NULL)
            {
                top++;
                stack[top]=P->lchild;
                level[top]=n+3;
            }
        }

    }
}
int Menu() /*菜单*/
{
    int nSelect=0;
    do{
        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("请选择：");
        scanf("%d",&nSelect);
        if((nSelect>=1)&&(nSelect<=7))return nSelect;
        }while(1);
}
void main()
{
    BiTree T=NULL;
    int i;
    int nSelect;
    printf("\nCreate a Binary Tree\n");
    CreateBiTree(&T);
    while(1){
        nSelect=Menu();
        switch(nSelect){
        case 1:
            printf("\nThe preorder is:");
            PreOrder(T);
            printf("\nThe inorder is:");
            InOrder(T);
            printf("\nThe postorder is:");
            PostOrder(T);
            break;
        case 2:
            printf("\nThe preorder (no recursion) is:");
            PreOrderTraverse(T);
            printf("\nThe inorder (no recursion) is:");
            InOrderTraverse(T);
            printf("\nThe postorder (no recursion) is:");
            PostOrderTraverse(T);
            printf("\nThe level order is:");
            LevelOrder(T);
            break;
        case 3:
            printf("\nThe depth is %d\n",depth(T));
            printf("The number of nodes is %d\n",nodenum(T));
            printf("The number of leafs is %d\n",leafnum(T));
            i=judgeComBTree(T);
            if(i) printf("This tree is a ComBTree");
            else printf("This tree is not a ComBTree");
            break;
        case 4:
            disp(T);
            break;
        case 5:
            printf("Before Exchange:\n");
            printf("The level order is:");
            LevelOrder(T);
            exchange(T);
            printf("\nAfter Exchange:\n");
            printf("The level order is:");
            LevelOrder(T);
            break;
        case 6:
            destroy(&T);
            printf("\nthe tree has been destroyed~");
            break;
        case 7:
            return;
            }
        }
    getch();
}