[原创]二叉树的应用~! — 编程爱好者社区

主题：[原创]二叉树的应用~!

flysun0311 [专家分：2040] 发布于 2006-04-27 09:36:00

小弟刚学的二叉树.
就把他综合了一下.
请大家指教:

//二叉树的基本操作///////////////////////////
#include <stdio.h>
#include <malloc.h>
//定义二叉树
typedef struct bitnode
{
    int data;
    struct bitnode *lchild,*rchild;
}bitnode,*bitree;
//创建二叉树利用先序创建
void createbitree(bitree *T)
{
    int dat;
    printf("Please Input data:");
    scanf("%d",&dat);
    if(dat==0) (*T) = NULL;
    else
    {
        (*T) = (bitree)malloc(sizeof(bitnode));
        (*T)->data=dat;
        createbitree(&((*T)->lchild));
        createbitree(&((*T)->rchild));
    }
}
//二叉树的先序周游递归算法
void postorder10(bitree T)
{
    if (T != NULL)
    {
       printf("%d\t",T->data);
       postorder10(T->lchild);
       postorder10(T->rchild);

     }

}
//二叉树的先序周游非递归算法
void postorder11(bitree t)
{ bitree s[100];
  int top=0;
  while (t!=NULL || top!=0)
   {
      while (t!=NULL)
      {
           printf("%d\t",t->data); s[++top]=t; t=t->lchild ;
      }
         if (top!=0)
         {
            t=s[top--]->rchild;
         }
   }
}
//二叉树的中序周游递归算法
void postorder20(bitree T)
{
    if (T != NULL)
    {
      postorder20(T->lchild);
       printf("%d\t",T->data);
       postorder20(T->rchild);
    }

}

//二叉树的中序周游非递归算法
void postorder21(bitree t)
   {
    bitree s[100];//指针数组（栈），存放按中序访问的节点的地址
     int top=0;
     while (t!=NULL || top!=0)
      {
         while (t!=NULL)
         {
             s[++top]=t;   t=t->lchild ;
         }
           if (top!=0)
           {
            t=s[top--];  printf("%d\t",t->data);  t=t->rchild;
           }
      }
   }
//二叉树的后序周游递归算法
void postorder30(bitree T)
{
    if (T != NULL)
    {
       postorder30(T->lchild);
       postorder30(T->rchild);
       printf("%d\t",T->data);
    }

}
//二叉树的后序周游非递归算法
void postorder31(bitree  t)
   {
    typedef struct node
       { bitree  t;  int tag;
       } stack;
      stack s[100] ;
       int top=0;
      while (t!=NULL|| top!=0)
      {while (t!=NULL)
         {s[++top].t=t;  s[top].tag=0;  t=t->lchild; }
      while (top!=0 && s[top].tag==1)
          printf("%d\t" ,s[top--].t->data);
      if (top)
        { s[top].tag=1;  t=s[top].t->rchild ; }
     }
   }

本帖地址： http://bbs.pfan.cn/post/161232.html

回复列表（共13个回复）

沙发

flysun0311 [专家分：2040] 发布于 2006-04-27 09:43:00

//在二叉树t中查找值为x的结点
void locate(bitree t, int  x)
{
   bitree p;
   p=t;
   if (t == NULL)
    printf("0\n");
   else if( t->data == x)
     printf("%d\n",p->data);
   else
   {
      p=t->lchild;
      if (p)
        locate(t->lchild, x);
      else
       locate(t->rchild, x);
   }
}
//以二叉链表作存储结构，试编写求二叉树深度的算法
int BinTreeDetth(bitree T)
{
    int l,r;
    if(T==NULL)return 0;
   else
   {
       l=BinTreeDetth(T->lchild);
           r=BinTreeDetth(T->rchild);
           return((l>r?l:r)+1);
   }
}
//以二叉链表作为存储结构，试编写求二叉树中叶子数的算法
int LeafCount1(bitree T)
{
    int i,j;
   if(!T) return 0;                     //空树没有叶子
  else if(T->lchild==NULL&&T->rchild==NULL)
  {
      return 1; //叶子结点
  }

  else
  {
      i=LeafCount1(T->lchild);
      j=LeafCount1(T->rchild);
          return (i+j);
  }
   //左子树叶子数加上右子树叶子数
}

//以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。
int num=0;
void  LeafCount2(bitree T)
{

    if(T)
    {LeafCount2(T->lchild) ;  //中序遍历左子树
      if(!T->lchild && !T->rchild)  num++; //访问根结点
     LeafCount2(T->rchild) ; //中序遍历右子树
     }

}
//以二叉链表作为存储结构，设计算法拷贝二叉树
bitree copy(bitree T)
  {bitree T1;
    if(T==NULL) T1=NULL;
    else
      {T1=(bitree)malloc(sizeof(bitnode));  //申请结点
        T1->data=T->data;
        T1->lchild=copy(T->lchild);
        T1->rchild=copy(T->rchild);
    }

板凳

flysun0311 [专家分：2040] 发布于 2006-04-27 09:43:00

return T1;
   }
//以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树
bitree change(bitree T)
  {
    bitree t;
    if(T!=NULL)
     {
    change(T->lchild);
       change(T->rchild);
    t=T->lchild;
    T->lchild=T->rchild;
    T->rchild=t;
    }
    return T;
   }

void main()
{
   bitree T;int n,m;
   createbitree(&T);
   printf("Create Success!\n\n");
  while(1)
  {
    printf("请输入你要执行的操作:\n");
    printf("0------------------------结束此次操作\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");
    scanf("%d",&n);
    switch(n)
    {
     case 0:
           return;
     case 1:
           printf("先序遍历为:\n");
           printf("put out the diguai DLR:\n");
           postorder10(T);
           printf("\n");
           printf("put out the not diguai DLR:\n");
           postorder11(T);
           printf("\n");
           break;
     case 2:
           printf("中序遍历为:\n");
          printf("put out the diguai DLR:\n");
           postorder20(T);
           printf("\n");
           printf("put out the not diguai DLR:\n");
           postorder21(T);
           printf("\n");
           break;
     case 3:
           printf("后序遍历为:\n");
           printf("put out the diguai DLR:\n");
           postorder30(T);
           printf("\n");
           printf("put out the not diguai DLR:\n");
           postorder31(T);
           printf("\n");
           break;
     case 4:
           printf("请输入你要查找的结点:\n");
           scanf("%d",&m);
           printf("你要查找的结点为: \n");
           locate(T,m);
           break;
     case 5:
           printf("树的深度为:\n");
           printf("%d\n",BinTreeDetth(T));
           break;
     case 6:
           printf("此树的叶子结点数为:\n");
           printf(" using the first way the result is:\n");
           printf("%d\n",LeafCount1(T));
           printf("using the second way the result is:\n");
           LeafCount2(T);
           printf("%d\n",num);
           break;
     case 7:
         printf("拷贝二叉树并中序访问为:\n");
          postorder21(copy(T));
          printf("\n");
          break;
     case 8:
         printf("(注意：（进行二次交换以便恢复到原来的状态）交换所有结点的左右子树并中序访问:\n");
         printf("the first change is:\n");
         postorder21(change(T));
          printf("\n");
          printf("the second change is:\n");
        postorder21(change(T));
          printf("\n");
          break;
    }
  }
}

3 楼

rickone [专家分：15390] 发布于 2006-04-27 13:52:00

这个只能算是二叉树的实现，不是应用吧~~

4 楼

candynet [专家分：80] 发布于 2006-04-29 22:58:00

谢谢楼主，收藏ing!

5 楼

tossboy [专家分：160] 发布于 2006-05-01 14:01:00

不像是新学的也是个老手了吧
藏了

6 楼

tossboy [专家分：160] 发布于 2006-05-01 14:21:00

switch(n)
{
case 0;
break;

7 楼

if007 [专家分：650] 发布于 2006-05-02 03:26:00

哈,那我补充三种稍微不同的非递归遍历吧.
staus Pre(Bitree T)
{
    InitStack(s);
    p=T;
    while(p || StackEmpty(s))
    {
        if (p)
        {
            visit(p->data);
            Push(s,p);
            p=p->lchild;
        }
        else
        {
            Pop(s,p);
            p=p->rchild;
        }
    }
    return OK;
}

status Inorder(Bitree T)
{
    InitStack(s);
    p=T;
    while (p || !StackEmpty(s))
    {
        if (p)
        {
            push(s,p);
            p=p->lchild;
        }
        else
        {
            Pop(s,p);
            Visit(p->data);
            p=p->rchild;
        }
    }
    return OK;
}

8 楼

if007 [专家分：650] 发布于 2006-05-02 03:35:00

以下这一种后序非递归遍历就有点更优了, 所以另起一楼,
它不需要设多一个数组空间来保存标志tag,

status Post(Bitree T)
{
    InitStack(s);
    p=T;
    do
    {
        if (p) { push(s,p); p=p->lchild; }
        else
        {
            b=1; q=NULL;
            while ( b&& ! StackEmpty(s))
            {
                GetTop(s,p);
                if (p->rchild == q)
                {
                    Visit(p->data);
                    Pop(s,p);
                    q=p;
                }
                else
                {
                    p=p->rchil;
                    b=0;
                }
            }
        }
    }while (!StackEmpty(s));
    return OK;
}

顺带一说,楼主的编程风格似乎有点美中不足,有些地方糊成一团.
需知从一个人的编程风格上,也可看出它的编程功底的.

9 楼

lt19870917 [专家分：750] 发布于 2006-05-02 12:47:00

后序非递归算法:
void PostOrder(BiTree T,void (*visit)(char))
{
    BiTree p,temp;
    stack S;
    initstack(S);
    p=T;
    if(p==NULL) return;
    else{
        push(S,p);
        do{
            if(p->lchild!=NULL){
                p=p->lchild;
                push(S,p);
            }
            else{
                if(p->rchild!=NULL){
                    p=p->rchild;
                    push(S,p);
                }
                else{
                    visit(p->data);
                    while(1){
                        pop(S,temp);
                        if(emptystack(S)) return;
                        gettop(S,temp);
                        if(temp->rchild!=NULL&&p!=temp->rchild){
                            p=temp->rchild;
                            push(S,p);
                            break;
                        }
                        else{
                            visit(temp->data);
                            p=temp;
                        }
                    }
                }
            }
        }while(!emptystack(S));
    }
}

10 楼

Goldenrop [专家分：0] 发布于 2006-05-07 16:10:00

都是高手啊本人刚学到二叉树
正好有你们了代码加深理解　
谢谢了诸位

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[原创]二叉树的应用~!

回复列表（共13个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[原创]二叉树的应用~!

回复列表 （共13个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共13个回复）