注册 登录
编程论坛 数据结构与算法

二叉树递归遍历二叉树,我的中序和后序输出是不对的,我不知道哪里错了,帮帮忙

支风儿 发布于 2013-04-22 23:12, 653 次点击
#include <stdio.h>
#include <malloc.h>
#define TRUE 1
#define FALSE 0
#define OK  1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int  Status;

typedef char  ElemType;
typedef struct BiTNode{
  ElemType data;
  struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;

BiTree CreateBiTree(BiTree &T) {  // 算法6.4
  // 按先序次序输入二叉树中结点的值(一个字符),’#’字符表示空树,
  // 构造二叉链表表示的二叉树T。
  char ch;
  scanf("%c",&ch);
  if (ch=='#')
  T = NULL;
  else {
    if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
    return ERROR;
    T->data = ch;              // 生成根结点
    CreateBiTree(T->lchild);   // 构造左子树
    CreateBiTree(T->rchild);   // 构造右子树
  }
  return T;
} // CreateBiTree


Status Visit( ElemType e ) {  // 输出元素e的值
     if(e!='#')
    {printf("%c", e );
      return OK;}
    else
    return ERROR;
}// PrintElement


Status PreOrderTraverse( BiTree T) {
   // 算法6.1
   // 采用二叉链表存储结构,Visit是对数据元素操作的应用函数,
   // 先序遍历二叉树T的递归算法,对每个数据元素调用函数Visit。
   // 最简单的Visit函数是:
   //     Status PrintElement( ElemType e ) {  // 输出元素e的值
   //        printf( e );  // 实用时,加上格式串
   //        return OK;
   //     }
   // 调用实例:PreOrderTraverse(T, PrintElement);
   if (T) {
      if (Visit(T->data))
         if (PreOrderTraverse(T->lchild))
            if (PreOrderTraverse(T->rchild))
                return OK;
      return ERROR;
   } else return OK;
} // PreOrderTraverse

Status InOrderTraverse(BiTree T)
{
    if(T)
    {
        if(InOrderTraverse(T->lchild))
            if(Visit(T->data))
                if(InOrderTraverse(T->rchild))
                    return OK;
        return ERROR;
    }
    else
        return OK;
} // InOrderTraverse

Status PostOrderTraverse( BiTree T ) {
     // 后序遍历二叉树T的递归算法,对每个数据元素调用函数Visit。

   if (T) {
       if (PostOrderTraverse(T->rchild))
          if (PostOrderTraverse(T->lchild))
            if  (Visit(T->data))
              return OK;
      return ERROR;
   }
    else return OK;
} // PostOrderTraverse



int main()   //主函数
{  BiTree T;
   CreateBiTree(T);
   PreOrderTraverse(T);
   printf("\n");
   InOrderTraverse(T);
   printf("\n");
   PostOrderTraverse(T);
   printf("\n");
   return OK;
                      //补充代码
 }//main
2 回复
#2
不玩虚的2013-04-23 00:04
遍历能不能把除了if(T)之外的if都去掉啊,你建二叉树为啥不这么写,遍历为啥要这么写啊,你自己想想逻辑吧。
#3
邓士林2013-04-24 19:05
if (T) {
      if (Visit(T->data))
         if (PreOrderTraverse(T->lchild))
            if (PreOrderTraverse(T->rchild))
                return OK;
这么多if真的没有用!
给你个例子:
void InOrder(BiTree T){

    if(T!=NULL)         //=NULL是递归结束条件
    {
        InOrder(T->lchild);        //中序遍历根的左子树
     printf("%c",T->data);          //访问根结点
        InOrder(T->rchild);          //右子树
    }

[ 本帖最后由 邓士林 于 2013-4-24 19:07 编辑 ]
1