重发二叉树的各种算法（顶的加分）

主题：重发二叉树的各种算法（顶的加分）

yrd2002 [专家分：1000] 发布于 2006-01-22 15:22:00

包括了各种遍历，搜索路径，交换子树，求树的深度，叶子树
还有线索二叉树的生成。用相对符合课本的形式写的。
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX 100
#define MAXSIZE 100
typedef int Status;
typedef char ElemType;
typedef struct BitNode/* 定义二叉树机构 */
{
  ElemType data;
  struct BitNode *lchild,*rchild;
}BitNode,*BiTree;
typedef struct Queue/* 定义队列 */
{
   BiTree *base;
   int front,rear;
}Queue;
Status InitQueue(Queue *Q)/* 初始化队列 */
{
  Q->base=(BiTree *)malloc(MAXSIZE*sizeof(BiTree));
  if(!Q->base) return ERROR;
  Q->front=Q->rear=0;
  return OK;
}
Status QueueEmpty(Queue *Q)/* 队列判空 */
{
  if(Q->front==Q->rear) return 1;
  return 0;
}
Status EnQueue(Queue *Q,BiTree e)/* 入队 */
{
   if((Q->rear+1)%MAXSIZE==Q->front) return ERROR;
   Q->base[Q->rear]=e;
   Q->rear=(Q->rear+1)%MAXSIZE;
   return OK;
}
Status DeQueue(Queue *Q,BiTree *e)/* 出队 */
{
  if(Q->rear==Q->front) return ERROR;
  (*e)=Q->base[Q->front];
  Q->front=(Q->front+1)%MAXSIZE;
  return OK;
}

Status PrintElement(ElemType e)/* 最简单的Visit函数 */
{
  printf("%c",e);
  return OK;
}
Status CreateBiTree(BiTree *T)/* 创建二叉树 */
{
  ElemType ch;
  scanf("%c",&ch);
  if(ch==' ') (*T)=NULL;
  else
  {
    if(!((*T)=(BitNode *)malloc(sizeof(BitNode)))) exit (OVERFLOW);
    (*T)->data=ch;
    (*T)->lchild=(*T)->rchild=NULL;
    CreateBiTree(&((*T)->lchild));
    CreateBiTree(&((*T)->rchild));
  }
return OK;
}
Status PreOrderTraverse(BiTree T,Status(*Visit)(ElemType e))/* 先序遍历 */
{
    if(T)
    {
        if(!Visit(T->data)) exit(ERROR);
        PreOrderTraverse(T->lchild,Visit);
        PreOrderTraverse(T->rchild,Visit);
    }
    return OK;
}
Status InOrderTraverse(BiTree T,Status(*Visit)(ElemType e))/* 中序遍历 */
{
if(T)
{
   InOrderTraverse(T->lchild,Visit);
   if(!Visit(T->data)) exit(ERROR);
   InOrderTraverse(T->rchild,Visit);
}
return OK;
}
Status PostOrderTraverse(BiTree T,Status(*Visit)(ElemType e))/* 后序遍历 */
{
  if(T)
  {
    PostOrderTraverse(T->lchild,Visit);
    PostOrderTraverse(T->rchild,Visit);
    if(!Visit(T->data)) exit(ERROR);
  }
  return OK;
}
Status PreOrderTraverse_None_Recursion(BiTree T,Status(*Visit)(ElemType e))/* 先序非递归 */
{
    BiTree p=T,Stack[MAX];
    int top=0;
    while (p|| top>0)
    {
        while (p)
        {
            if(!Visit(p->data)) exit(ERROR);
            Stack[top++]=p;
            p=p->lchild;
        }
        if (top>0)
        {
            p=Stack[--top];
            p=p->rchild;
       }
    }
    return OK;
}

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

回复列表（共18个回复）

沙发

yrd2002 [专家分：1000] 发布于 2006-01-22 15:23:00

Status InOrderTraverse_None_Recursion(BiTree T,Status(*Visit)(ElemType e))/* 中序非递归 */
{
    BiTree p=T,Stack[MAX];
    int top=0;
    while (p!=NULL || top>0)
    {
        while (p!=NULL)
        {
            Stack[top++]=p;
            p=p->lchild;
        }

        if (top>0)
        {
            p=Stack[--top];
            if(!Visit(p->data)) exit(ERROR);
            p=p->rchild;
        }
    }
  return OK;
}
Status PostOrderTraverse_None_Recursion(BiTree T,Status(*Visit)(ElemType e))/* 后序非递归 */
{
    BiTree p=T, Stack[MAX];
    int tag[MAX];
    int top=0;
    do
    {
        while(p != NULL)
        {
            Stack[top++] = p;
            tag[top] = 0;
            p = p->lchild;
        }
        if(top > 0)
        {
            if(!tag[top])
            {
                p = Stack[top-1];
                p = p->rchild;
                tag[top] = 1;
            }
            else if (!Visit(Stack[--top]->data)) exit (ERROR);
        }
    } while((p != NULL)||(top >0));
    return OK;
}
Status LevelOrderTraverse(BiTree T,Status(*Visit)(ElemType e))/* 层次遍历 */
{
  BiTree p;
  Queue *Q=(Queue *)malloc(sizeof(Queue));
  if(!T) return ERROR;
  if(!InitQueue(Q)) exit(OVERFLOW) ;
  EnQueue(Q,T);
  while(!QueueEmpty(Q))
  {
    DeQueue(Q,&p);
    if(!Visit(p->data)) exit(ERROR);
    if(p->lchild) EnQueue(Q,p->lchild);
    if(p->rchild) EnQueue(Q,p->rchild);
  }
  return OK;
}
Status DestroyBiTree(BiTree *T)/*销毁二叉树*/
{
  if(*T)
  {
     DestroyBiTree(&(*T)->lchild);
     DestroyBiTree(&(*T)->rchild);
     free(*T);
     (*T)=NULL;
  }
  return OK;
}
int BiTreeDepth(BiTree T)/* 求树的深度 */
{
  int dep1,dep2;
  if(T==NULL) return 0;
  else
  {
    dep1=BiTreeDepth(T->lchild);
    dep2=BiTreeDepth(T->rchild);
     if(dep1>dep2) return dep1+1;
     else return dep2+1;
  }
}
int Leaf_Count(BiTree T)/* 求叶子数 */

{
  if(!T) return 0;
  else if(!T->lchild&&!T->rchild) return 1;
  else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);
}
void Bitree_Revolute(BiTree T)/* 交换所有左右子树 */
{
  BiTree temp;
  temp=T->lchild;/*swap(T->lchild,T->rchild)*/
  T->lchild=T->rchild;
  T->rchild=temp;/*end swap*/
  if(T->lchild) Bitree_Revolute(T->lchild);
  if(T->rchild) Bitree_Revolute(T->rchild);
}

板凳

yrd2002 [专家分：1000] 发布于 2006-01-22 15:24:00

Status FindNode(BitNode *T, char e)/* 搜索结点并返回路径 */
{
    BitNode *p=T, *Stack[MAX];/* p表示当前结点，栈Stack[]用来存储结点  */
    int tag[MAX];
    int top=0, i;
    do
    {
        while(p != NULL)/* 先处理结点的左孩子结点，把所有左孩子依次入栈  */
        {
            Stack[top++] = p;
            tag[top] = 0;
            p = p->lchild;
        }
        if(top > 0) /* 所有左孩子处理完毕后  */
        {
            if(!tag[top]) /* 如果当前结点的右孩子还没被访问  */
            {
                p = Stack[top-1];/* 输出栈顶结点，但不退栈，因为要先输出其孩子结点  */
                p = p->rchild; /* 处理其右孩子结点  */
                tag[top] = 1; /* 表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出  */
            }
            else /* 如果该结点的左右孩子都被访问过了  */
            {
                if(Stack[top-1]->data==e)
                {
                    printf("The path: ");
                    for(i=0; i<top; i++) /* 输出从栈底到栈顶的元素构成路径  */
                        printf("%c", Stack[i]->data);
                    return OK;
                }
                top--;
            }
        }
    } while((p != NULL)||(top >0));
    return ERROR;
}
void welcome()
{
   printf("A.CreateBiTree\n");
   printf("B.PreOrderTraverse\n");
   printf("C.InOrderTraverse\n");
   printf("D.PostOrderTraverse\n");
   printf("E.PreOrderTraverse_None_Recursion\n");
   printf("F.InOrderTraverse_None_Recursion\n");
   printf("G.PostOrderTraverse_None_Recursion\n");
   printf("H.LevelOrderTraverse\n");
   printf("I.DestroyBiTree\n");
   printf("J.BiTreeDepth\n");
   printf("K.Leaf_Count\n");
   printf("L.Bitree_Revolute\n");
   printf("M.Find_Node\n");
   printf("Q.Quit the System\n");
}
void Action(BiTree T)
{
  char e;
  fflush(stdin);
  printf("Input a Data to Search:");
  e=getchar();
  if(!FindNode(T,e)) printf("Data Not Find");

}
void main()
{
  BitNode *T=NULL;
  char key;
   system("cls");
   welcome();
   while((key=getch())!='q')
   {
      switch(key)
      {   case 'a' :system("cls");CreateBiTree(&T);fflush(stdin);system("cls");welcome();break;
          case 'b' :system("cls");PreOrderTraverse(T,PrintElement);getch();system("cls");welcome();break;
          case 'c' :system("cls");InOrderTraverse(T,PrintElement);getch();system("cls");welcome();break;
          case 'd' :system("cls");PostOrderTraverse(T,PrintElement);getch();system("cls");welcome();break;
          case 'e' :system("cls");PreOrderTraverse_None_Recursion(T,PrintElement);getch();system("cls");welcome();break;
          case 'f' :system("cls");InOrderTraverse_None_Recursion(T,PrintElement);getch();system("cls");welcome();break;
          case 'g' :system("cls");PostOrderTraverse_None_Recursion(T,PrintElement);getch();system("cls");welcome();break;
          case 'h' :system("cls");LevelOrderTraverse(T,PrintElement);getch();system("cls");welcome();break;
          case 'i' :system("cls");DestroyBiTree(T);getch();system("cls");welcome();break;
          case 'j' :system("cls");printf("Depth=%d",BiTreeDepth(T));getch();system("cls");welcome();break;
          case 'k' :system("cls");printf("Leadf=%d",Leaf_Count(T));getch();system("cls");welcome();break;
          case 'l' :system("cls");Bitree_Revolute(T);printf("Revolute Success");getch();system("cls");welcome();break;
          case 'm' :system("cls");Action(T);getch();system("cls");welcome();break;
          default :;
      }
   }
}

3 楼

yrd2002 [专家分：1000] 发布于 2006-01-22 15:25:00

再来一个线索二叉树

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
typedef int Status;
typedef int TElemType;
typedef enum {Link,Thread} PointerTag;/*枚举 Link==0：指针，Thread==1:线索*/
typedef struct BiThrNode/*定义线索二叉树*/
{
   TElemType data;
   struct BiThrNode *lchild,*rchild;
   PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrTree pre;
void InThreading(BiThrTree p)/*递归中序线索化二叉树*/
{
  if(p)
  {
   InThreading(p->lchild);/*左子树线索化*/
   if(!p->lchild)
   { p->LTag=Thread;p->lchild=pre; } /*前驱线索*/
   if(!pre->rchild)
   { pre->RTag=Thread;pre->rchild=p;}/*后继线索*/
   pre=p;/*保持pre指向p的前驱*/
   InThreading(p->rchild);/*右子树线索化*/
  }
}
Status PrintElement(TElemType e)/*最简单的Visit函数*/
{
  printf("%d",e);
  return OK;
}
Status CreateBiTree(BiThrTree *T)/*先序遍历建二叉树*/
{
  int dat;
  scanf("%d",&dat);
  if(!dat) (*T)=NULL;
  else
  {
    (*T)=(BiThrNode *)malloc(sizeof(BiThrNode));
    if(!(*T)) return ERROR;
    (*T)->data=dat;(*T)->LTag=(*T)->RTag=Link;
    (*T)->lchild=(*T)->rchild=NULL;
    CreateBiTree(&((*T)->lchild));/*创建左孩子*/
    CreateBiTree(&((*T)->rchild));/*创建右孩子*/
  }
return OK;
}
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)/*中序遍历二叉树T，并将其中序线索化，Thrt指向头节点*/
{
   (*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode));
   if(!Thrt) return ERROR;
   (*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建头结点*/
   (*Thrt)->rchild=(*Thrt);/*右指针回指*/
   if(!T) (*Thrt)->lchild=(*Thrt);/*若二叉树空，则左指针回指,为了若T为空树是能结束循环*/
   else {
   (*Thrt)->lchild=T;
   pre=(*Thrt);
   InThreading(T);/*中序遍历进行中序线索化*/
   pre->rchild=(*Thrt);/*最后一个结点的右孩子线索化,因为pre=p */
   pre->RTag=Thread;
   (*Thrt)->rchild=pre;
   }
   return OK;
}

Status InOrderTraverse_Thr(BiThrTree T,Status (*Visit)(TElemType e))/*T指向头结点，头结点的左链lchild指向根结点，中序遍厉二叉树*/
/*道理同逆序*/
{
   BiThrTree p;
   p=T->lchild;/*p指向根结点*/
   while(p!=T)/*空树或遍厉结束时，p==T  */
   {
     while(p->LTag==Link) p=p->lchild;
     if(!Visit(p->data)) return ERROR;/*访问其左子树为空的结点*/
     while(p->RTag==Thread&&p->rchild!=T)
     {
       p=p->rchild;
       if(!Visit(p->data)) return ERROR;/*访问后继结点*/
     }
    p=p->rchild;
   }
  return OK;
}
Status InOrderTraverse_Thr_Reverse(BiThrTree T,Status (*Visit)(TElemType e))/*反向遍历*/
{
BiThrTree p;
p=T->rchild;
while(p!=T)
{
   while(p->RTag==Link) p=p->rchild;/*搜索至最右的结点*/
   if(!Visit(p->data)) return ERROR;/*访问其右子树为空的结点*/
   while(p->LTag==Thread&&p->lchild!=T)
   {
      p=p->lchild;
      Visit(p->data);
   }
   p=p->lchild;/*非叶子结点，首先找其左子树*/
}
}

void main()
{
   BiThrTree T,Thrt;
   CreateBiTree(&T);
   InOrderThreading(&Thrt,T);
   InOrderTraverse_Thr(Thrt,PrintElement);
   printf("\n");
   InOrderTraverse_Thr_Reverse(Thrt,PrintElement);
   getch();
}

4 楼

freetyy [专家分：40] 发布于 2006-01-25 14:42:00

谢谢

5 楼

mabawo [专家分：0] 发布于 2006-06-08 08:54:00

[size=6][/size][size=6]谢谢你的程序,在运行时怎么输入啊,我不会输入啊,希望你能帮助我一下,好吗[/size]

6 楼

mabawo [专家分：0] 发布于 2006-06-08 08:56:00

不用线索二叉树那个,只要二叉树的基本操作那个就行,运行通过后我不会输入,帮我一下吧,大侠,我真的急用啊,谢谢了

7 楼

mabawo [专家分：0] 发布于 2006-06-08 08:58:00

你的程序真的不错,呵呵

8 楼

mabawo [专家分：0] 发布于 2006-06-13 21:38:00

给我回个内容吧,我急等着用啊,谢谢啊

9 楼

henryliuch [专家分：290] 发布于 2006-06-17 23:03:00

谢谢楼主的归纳啊。很全面，对我们学习是很有帮助的，顶一下

10 楼

vargent [专家分：0] 发布于 2006-06-18 21:13:00

支持

我来回复

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

主题：重发二叉树的各种算法（顶的加分）

回复列表（共18个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：重发二叉树的各种算法（顶的加分）

回复列表 （共18个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共18个回复）