C语言构造并递归遍历二叉树的代码
来源:http://blog.csdn.net/ksly_tkol/article/details/8393846
#include<stdio.h> #include<malloc.h> #define FALSE 1 #define ERROR 0 #define OK 1 #define ON 0 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; typedef int Status; BiTree T; Status CreateBiTree(BiTree *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 OK; } // CreateBiTree int vi(char c) { printf("%c ",c); return OK; } //先序遍历的递归 void PreOrder(BiTree T) { if(T) { vi(T->data); //访问结点 PreOrder(T->lchild); //遍历左子树 PreOrder(T->rchild); //遍历右子树 } } //中序遍历的递归 void InOrder(BiTree T) { // 采用二叉链表存储结构,Visit是对数据元素操作的应用函数。 // 中序遍历二叉树T的递归算法,对每个数据元素调用函数Visit。 if(T) { InOrder(T->lchild); vi(T->data); InOrder(T->rchild); } } // InOrderTraverse //后序遍历的递归 void PostOrder(BiTree T) { // 采用二叉链表存储结构,Visit是对数据元素操作的应用函数。 // 中序遍历二叉树T的递归算法,对每个数据元素调用函数Visit。 if(T) { PostOrder(T->lchild); PostOrder(T->rchild); vi(T->data); } } // InOrderTraverse int main() { printf("先序输入二叉树(空格代表空节点):\n"); CreateBiTree(&T); printf("先序输出二叉树:\n"); PreOrder(T); printf("\n"); printf("中序输出二叉树:\n"); InOrder(T); printf("\n"); printf("后序输出二叉树:\n"); PostOrder(T); printf("\n"); return 0; }