树的建立与遍历 用C语言版的数据结构实现的

#include "c2.h" #include "c1.h" int found=0; void InitTree(BiTree &T) {//初始化树 T=NULL; } void CreatTree(BiTree &T) {//创建树 TElemtype ch; scanf("%c",&ch); static int i=0; if(ch==Nil) T=NULL; else{ T=(BiTree)malloc(sizeof(BiTNode)); if(!T)exit(OVERFLOW); T->data=ch; CreatTree(T->lchild); CreatTree(T->rchild); } } int chose() { int i; printf("\n=================================================================\n"); printf("请选择遍历二叉树的方式： \n"); printf("1、先序遍历 \n"); printf("2、中序遍历 \n"); printf("3、后序遍历 \n"); printf("4、凹入表横向打印二叉树 \n"); printf("5、退出程序 \n"); printf("=================================================================\n"); fflush(stdin); scanf("%d",&i); return i; } void PreOrderTraverse(BiTree T) {//前序遍历树 if(T){ printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } void InOrderTraverse(BiTree T) {//中序遍历树 if(T){ InOrderTraverse(T->lchild); printf("%c",T->data); InOrderTraverse(T->rchild); } } void PostOrderTraverse(BiTree T) {//后序遍历树 if(T){ PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c",T->data); } } void Level(BiTree r,BiTree T) {//调用BitreeLevel算出每个结点的层次 if(T){ found=0; T->d=BitreeLevel(r,T,0);//把每个结点的层次赋给T->d Level(r,T->lchild); Level(r,T->rchild); } } int BitreeLevel(BiTree root,BiTree T,int level) { //被Level调用算出一个结点的层次 if(root != NULL && found==0) { level++; if(root->data == T->data) found = 1;//found==1时，说明找到该结点 else { level=BitreeLevel(root->lchild,T,level); // 将level的值传给下一次递归 level=BitreeLevel(root->rchild,T,level); if(found==0) level--;//当递归右子树没找到该结点时，则返回父节点，level-- } } return level; } void Output(BiTree T) {//该打印与中序遍历相似，只是打印时，先打印右子树 if(T){ Output(T->rchild);//先遍历右子树 for(int i=0;i<T->d;i++){//每个结点的层次多少就打多少空格 printf(" "); } printf("%c\n",T->data); Output(T->lchild);//后遍历左子数 } }