树相关操作的递归算法实现

<meta http-equiv="Content-Type" content="text/html;charset=gb2312">

/***************************************************************** * 文件名：Rstree.c * * 文件描述：树相关操作的递归算法实现 * * 创建人：颜清国 2006年4月15日 * * * 修改记录： * **************************************************************/ #include "stdio.h"#include"stdlib.h"#include"conio.h"#define LEFT 1#define RIGHT 2#define MAX 20/************************************** 定义树的结构体***************************************/typedef struct tagtree{ char data;                /*数据域*/ int flag;                 /*非递归操作时用来做标志*/ struct tagtree*lchild;    /*指向左孩子的指针域*/ struct tagtree*rchild;    /*指向右孩子的指针域*/}tree;/****************************************  创建一棵树，要求这棵树用括号表示法输入*****************************************/void CreateTree(tree **root,char *str){ char ch; tree *stack[MAX],*lp=NULL,*temp;      /*定义一个指向树的一个栈，                                    用来创建其结点的父子关系*/ int top=-1,flag;              /*指向树栈的栈顶，flag用来标记左右孩子*/ (*root)=NULL;                 /*特别注意这里一定要先将指向根结点的指针附空，否则                                   在XP系统下就会出大错*/while((*str)!='\0'){ ch=(*str); switch(ch) {  case '(':                 /*下去的DATA值将作为栈顶结点的左右孩子*/           top++;	   stack[top] = lp; /*将双亲结点入栈*/           flag = LEFT;     /*标记其下一个结点将作为此栈顶结点的                               左孩子*/           break;  case ',':           flag = RIGHT;    /*标记为下去结点将作为此栈顶结点的                               右孩子*/           break;  case ')':           top--;           /*将栈顶结点退栈，这样才能保证双亲及                               其对应孩子的正确配对*/           break;  default:                  /*此时CH为DATA域*/           lp = (tree*)malloc(sizeof(tree)); /*创建一个结点*/           lp->data = ch;           lp->lchild = NULL;           lp->rchild = NULL;           if((*root) == NULL)       /*是树的根结点*/             (*root) = lp;           else           {                  /*注意此处不能用这种表达方式*/                 /* temp = (flag == LEFT) ? stack[top]->lchild : stack[top]->rchild;                  temp = lp;  */                 switch(flag)                  {                    case RIGHT:                           /*插到右结点*/                                stack[top]->rchild = lp;                                 break;                    case LEFT:                           /*插到左结点*/                                 stack[top]->lchild = lp;                                  break;                     }               }          break;   }   str++;}}/******************************************** 用括号表示法输出树**********************************************/void OutTree(tree *root){ if(root != NULL) {  printf("%c",root->data);       /*先输出根结点*/  if(root->lchild != NULL || root->rchild != NULL)  {   printf("(");   OutTree(root->lchild);        /*处理左子树*/   if(root->rchild != NULL)   {    printf(",");   }  OutTree(root->rchild);         /*处理右子树*/  printf(")");}}}/************************************************ 递归先序遍历二叉树************************************************/void RsPrePath(tree *root){ if(root!=NULL) {   printf("%c ",root->data);         /*遇到根结点先输出*/   RsPrePath(root->lchild);            /*遇到根结点左子数先输出，                                       直到空，返回是输出左子数                                       根结点右子数*/   RsPrePath(root->rchild);            /*同样处理右子数*/ }}/************************************************ 递归中序遍历二叉树************************************************/void RsMidPath(tree *root){ if(root!=NULL) {   RsMidPath(root->lchild);   printf("%c ",root->data);   RsMidPath(root->rchild); }}/************************************************ 递归后序遍历二叉树************************************************/void RsLastPath(tree *root){ if(root!=NULL) {   RsLastPath(root->lchild);   RsLastPath(root->rchild);   printf("%c ",root->data); }}/*********************************************** 递归遍历二叉树演示************************************************/void RsTreeDemo(tree*root){ printf("\nthe PrePath is:"); RsPrePath(root); printf("\nthe MidPath is:"); RsMidPath(root); printf("\nthe LastPath is:"); RsLastPath(root);}/************************************************ 用树形表示法输出树*************************************************/void DispTree(tree *root,int x,int y,int n)     /*n用来控制第一层树的高度*/{ int i=0; if(root !=NULL)  {    gotoxy(x,y);                               /*到相应结点输出*/    printf("%c",root->data);    if(root->lchild != NULL)                  /*处理左子树，这里只有第一次N为可变的，*/    {       i=1;                                   /*为的是能够输出整棵树，而不会被覆盖，*/       while(ilchild,x-n,y+n,2);       /*递归处理左子树*/     }     if(root->rchild != NULL)    {       i=1;       while(irchild,x+n,y+n,2);       /*递归处理右子树*/     }   }}/***************************************************** 根据DATA域，查找第一个遇到的结点,并返回该结点 *****************************************************/tree* IndexNode(tree *root,char data,int *high,int temp){ if(root == NULL) {    (*high)=0;    return NULL; } else       if(root->data == data)  /*找到所要找的结点*/       {           (*high) = temp;           return root;       }       else       {	   if(IndexNode(root->lchild,data,high,temp+1)==NULL)           {	      IndexNode(root->rchild,data,high,temp+1);/*如果在左子树中没有找到*/           }       }}/**************************************************** 找某一结点的左子树 ****************************************************/tree* FindLchild(tree * node){  if(node !=NULL)  {       return node->lchild;  }  else        return NULL;}/**************************************************** 找某一结点的右子树 ****************************************************/tree* FindRchild(tree * node){if(node !=NULL)  {       return node->rchild;  }  else        return NULL;}/**************************************************** 先序遍历查找所有叶子结点 ****************************************************/void FindLeaft(tree *root){ if(root == NULL)    return; if(root->lchild == NULL && root->rchild == NULL) {    printf("%c ",root->data); } FindLeaft(root->lchild); FindLeaft(root->rchild);}void main(){ tree *root; int high; char str[100]; clrscr(); printf("Please  input the Tree string:"); gets(str); CreateTree(&root,str); printf("\nthe Tree is:"); DispTree(root,10,4,5); gotoxy(2,15); FindLeaft(root); /*printf("\n%c",IndexNode(root,'t',&high,1)->data); printf("\n%d",high);*/ /*RsTreeDemo(root);*/ getch();}