二叉树递归遍历

  1 /* 模块名      : 树
  2 /* 文件名      : btree.cpp
  3 /* 功能描述    : 二叉树的递归遍历
  4 
  5 /* 备注        : 输入示例与输出结果
  6 /* e.g. input  : ABD###CE#F###
  7 /* bi-tree     :
  8 /*                 A
  9 /*                / \
 10 /*               B   C
 11 /*              /   /
 12 /*             D   E
 13 /*                  \
 14 /*                   F
 15 /* 
 16 /* pre-order traverse: A B D C E F
 17 /* in-order traverse: D B A E F C
 18 /* post-order traverse: D B F E C A
 19 *******************************************************************************/
 20 #include <stdio.h>
 21 #include <stdlib.h>
 22 #include <string>
 23 
 24 /******************************************************************************
 25 /* 数据类型和常量定义
 26 /******************************************************************************/
 27 #define OK           1
 28 #define ERROR        0
 29 #define OVERFLOW    -2
 30 
 31 typedef int Status;
 32 typedef int TElemType;
 33 
 34 
 35 /******************************************************************************
 36 /* 数据结构声明
 37 /******************************************************************************/
 38 /* 二叉树的链式存储结构 */
 39 typedef struct BiTNode {
 40     TElemType data;
 41     struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
 42 } BiTNode, *BiTree;
 43 
 44 
 45 /******************************************************************************
 46 /* 函数原型声明
 47 /******************************************************************************/
 48 Status Visit(TElemType e);
 49 Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType));
 50 Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType));
 51 Status PostOrderTraverse(BiTree T, Status (*Visit)(TElemType));
 52 
 53 
 54 //功能     : 打印节点数据
 55 Status Visit(TElemType e)
 56 {
 57     printf("%c", e);
 58     return OK;
 59 }
 60 
 61 //功能     : 前序遍历二叉树
 62 Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType))
 63 {
 64     if(T){
 65         if(Visit(T->data))
 66             if(PreOrderTraverse(T->lchild, Visit))
 67                 if(PreOrderTraverse(T->rchild, Visit))
 68                     return OK;
 69                 return ERROR;
 70     }
 71     else
 72         return OK;
 73 }
 74 
 75 
 76 //功能     : 中序遍历二叉树
 77 Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType))
 78 {
 79     if(T){
 80         if(InOrderTraverse(T->lchild, Visit))
 81             if(Visit(T->data))
 82                 if(InOrderTraverse(T->rchild, Visit))
 83                     return OK;
 84                 return ERROR;
 85     }
 86     else
 87         return OK;
 88 }
 89 
 90 //功能     : 后序遍历二叉树
 91 Status PostOrderTraverse(BiTree T, Status (*Visit)(TElemType))
 92 {
 93     if(T){
 94         if(PostOrderTraverse(T->lchild, Visit))
 95             if(PostOrderTraverse(T->rchild, Visit))
 96                 if(Visit(T->data))
 97                     return OK;
 98                 return ERROR;
 99     }
100     else
101         return OK;
102 }
103 
104 
105 //功能     : 创建二叉树
106 //备注     : 前序方式创建
107 Status CreateBiTree(BiTree &T)
108 {
109     char ch = getchar();
110     if('#' == ch) T = NULL;
111     else {
112         if(!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
113         T->data = ch;             //生成根结点
114         CreateBiTree(T->lchild);  //构造左子树
115         CreateBiTree(T->rchild);  //构造右子树
116     }
117     return OK;
118 }
119 
120 void main()
121 {
122     BiTree T;
123     CreateBiTree(T);
124 
125     printf("Pre Order Traverse: ");
126     PreOrderTraverse(T, Visit);        //前序方式遍历二叉树
127 
128     printf("\nIn Order Traverse: ");
129     InOrderTraverse(T, Visit);         //中序方式遍历二叉树
130 
131     printf("\nPost Order Traverse: ");
132     PostOrderTraverse(T, Visit);       //后序方式遍历二叉树
133 }