数据结构与算法系列---二叉树

二叉树的代码实现及操作:

#include  < malloc.h >

#define   OK     1

#define   ERROR  0

#define   OVERFLOW -2

#define   TURE   1

#define   FALSE  0

#define   QMAXSIZE  20

typedef  int  TElemType;

typedef  struct  BiTNode

... {

    TElemType data;

    int flag;

    struct BiTNode *lchild,*rchild;

} BiTNode, * BiTree;

// 创建一棵二叉树

int  CreateTree(BiTree  & T)

... {

    int ch;

    printf("input a char:");

    scanf("%d",&ch);

    if(ch==0)

        T=NULL;

    else

    ...{

        T=(BiTree)malloc(sizeof(BiTNode));

        if(!T)

            return ERROR;

        T->data=ch;

        CreateTree(T->lchild);

        CreateTree(T->rchild);

    }

    return OK;

}

// 创建二叉树的数组

int  TreeArray[ 15 ] = ... {1,2,3,0,0,4,5,0,6,0,0,7,0,0,0} ;

// 计数

int  counter = 0 ;

// 由数组创建一棵二叉树

BiTree DefaultCreate()

... {

    int ch=TreeArray[counter++];

    BiTree root;

    if(ch==0)

        root=NULL;

    else

    ...{

        root=(BiTree)malloc(sizeof(BiTNode));

        if(!root)

            return ERROR;

        root->data=ch;

        root->lchild=DefaultCreate();

        root->rchild=DefaultCreate();

    }

    return root;

}

// 创建一棵二叉树

BiTree CreateBiTree()

... {

    int ch;

    BiTree root;

    printf("input a char:");

    scanf("%d",&ch);

    if(ch==0)

        root=NULL;

    else

    ...{

        root=(BiTree)malloc(sizeof(BiTNode));

        if(!root)

            return ERROR;

        root->data=ch;

        root->lchild=CreateBiTree();

        root->rchild=CreateBiTree();

    }

    return root;

}

// 先序遍历(递归算法)

void  PreOrderTraverse(BiTree T)

... {

    if(T!=NULL)

    ...{

        printf("%d ,",T->data);

        PreOrderTraverse(T->lchild);

        PreOrderTraverse(T->rchild);

    }

}

// 先序遍历(非递归算法)

void  PreOrderTraverse2(BiTree T)

... {

    BiTree Q[20];

    BiTree p=T;

    int top=-1;

    while(p||top>-1)

    ...{

        while(p)

        ...{

            printf("%d, ",p->data);

            Q[++top]=p;

            p=p->lchild;

        }

        if(top>-1)

        ...{

            p=Q[top--];

            p=p->rchild;

        }

    }

}

// 中序遍历二叉树(递归算法)

void  InOrderTraverse(BiTree T)

... {

    if(T)

    ...{

        InOrderTraverse(T->lchild);

        printf("%d ,",T->data);

        InOrderTraverse(T->rchild);

    }

}

// 中序遍历(非递归算法)

void  InOrderTraverse2(BiTree T)

... {

    BiTree Q[20];

    BiTree p=T;

    int top=-1;

    while(p||top>-1)

    ...{

        while(p)

        ...{

            Q[++top]=p;

            p=p->lchild;

        }

        if(top>-1)

        ...{

            p=Q[top--];

            printf("%d, ",p->data);

            p=p->rchild;

        }

    }

}

// 后序遍历二叉树(递归算法)

void  PostOrderTraverse(BiTree T)

... {

    if(T)

    ...{

        PostOrderTraverse(T->lchild);

        PostOrderTraverse(T->rchild);

        printf("%d ,",T->data);

    }

}

// 后序遍历(非递归算法)

void  PostOrderTraverse2(BiTree T)

... {

    int flag[20];

    BiTree Q[20],p=T;

    int top=-1;

    while(p||top>-1)

    ...{

        while(p)

        ...{

            Q[++top]=p;

            flag[top]=0;

            p=p->lchild;

        }

        if(top>-1)

        ...{

            if(flag[top]==0&&Q[top]->rchild)

            ...{

                flag[top]=1;

                p=Q[top]->rchild;

            }

            else

            ...{

                printf("%d, ",Q[top]->data);

                top--;

            }

        }

    }

}

// 广度优先遍历

void  BFTraverse(BiTree T)

... {

    BiTree Q[QMAXSIZE],p=T;

    int front=0,rear=0;

    Q[rear++]=p;

    while(front!=rear)

    ...{

        p=Q[front];

        front=(front+1)%QMAXSIZE;

        printf("%d, ",p->data);

        if(p->lchild)

        ...{

            Q[rear]=p->lchild;

            rear=(rear+1)%QMAXSIZE;

        }

        if(p->rchild)

        ...{

            Q[rear]=p->rchild;

            rear=(rear+1)%QMAXSIZE;

        }

    }

}

void  BiTLink_Ancestor2(BiTree T, int  x)

... {

    BiTree stack[20];

    BiTNode *q=T;

    int top=-1,i;

    while(1)

    ...{

        while(q)

        ...{

            ++top;

            stack[top]=q;

            stack[top]->flag=0;

            q=q->lchild;

        }

        if(top==-1)

            return;

        if(stack[top]->flag==0&&stack[top]->rchild)

        ...{

            stack[top]->flag=1;

            q=stack[top]->rchild;

        }

        else

        ...{

            if(stack[top]->data==x)

            ...{

                i=0;

                while(i<top)

                ...{

                    printf("%d, ",stack[i]->data);

                    i++;

                }

                return;

            }

            top--;

        }

    }

}

// 交换左右结点(递归算法)

void  BiTree_ExchangeNode(BiTree T)

... {

    BiTNode *p;

    if(T)

    ...{

        p=T->lchild;

        T->lchild=T->rchild;

        T->rchild=p;

        BiTree_ExchangeNode(T->lchild);

        BiTree_ExchangeNode(T->rchild);

    }

}

int  main( int  argc, char   * argv[])

... {

    BiTree root=NULL;

//    CreateTree(root);

//    root=CreateBiTree();

    root=DefaultCreate();

    printf("preorder is: ");

    PreOrderTraverse(root);

    PreOrderTraverse2(root);

    printf("  inorder is: ");

    InOrderTraverse(root);

    InOrderTraverse2(root);

    printf("  post order is: ");

    PostOrderTraverse(root);

    PostOrderTraverse2(root);

    return OK;

}