建立二叉树并求指定结点路径.doc

#include #include #define num 100#define OK 1typedef int Status;typedef char DataType;typedef struct nodeDataType data;struct node *lchild,*rchild;BinTNode,*BinTree;int found;BinTNode *p;Status CreateBiTree(BinTree &bt)/按照先序遍历次序递归建立二叉树,参见教材P131算法6.4/ABCDEGF 对应于教材P127图6.8(b)char ch;printf(ch=);scanf(%c,&ch); getchar(); if (ch=)bt=NULL;else bt=(BinTNode *)malloc(sizeof(BinTNode); bt-data=ch; /生成根结点 CreateBiTree(bt-lchild); /构造左子树 CreateBiTree(bt-rchild); /构造右子树return OK;Status Inorder(BinTree bt)/二叉树非递归中序遍历算法 BinTNode *p,*s100; /定义数组栈 int i=0; /初始化栈 p=bt; do while(p!=NULL) /扫描根结点及其所有的左结点并将其地址入栈 si+=p; p=p-lchild; if (i0) /判断栈是否为空 p=s-i; /出栈 printf(%ct,p-data); /访问结点 p=p-rchild; /扫描右子树 while(i0|p!=NULL);return OK;/void NodePath(BinTree bt,BinTNode *ch)/求二叉树根结点到给定结点*p的路径 typedef enum FALSE,TRUEboolean; BinTNode *stacknum; /定义栈 int tagnum; int i,top; boolean find; BinTNode *s; find=FALSE; top=0; s=bt; do while(s!=NULL) /扫描左子树 top+; stacktop=s; tagtop=0; s=s-lchild; if(top0) s=stacktop; if(tagtop=1) if(s=ch) /找到ch,则显示从根结点到ch的路径 for(i=1;i%c,stacki-data); find=TRUE; else top-; s=stacktop; /endif if(top0 & !find) if(tagtop!=1) s=s-rchild; /扫描右子树 tagtop=1; else s=NULL; /endif /endlif while(!find & top!=0);void FindBT(BinTree bt,DataType x) if(bt!=NULL) & !found) if(bt-data=x) p=bt;found=1; else FindBT(bt-lchild,x); /遍历查找左子树 FindBT(bt-rchild,x); /遍历查找右子树 BinTNode *Findx(BinTree bt,DataType x)/按给定值查找结点 int found=0; /用found来作为是否查找到的标志 BinTree p=NULL; /置空指针 FindBT(bt,x); return(p);void main()BinTree bt; char ch1;int xz=1;while(xz)printf( 建立二叉树并求指定结点路径 n);printf(=n);printf( 1.建立二叉树的存储结构 n);printf( 2.求解二叉树的中序遍历 n);printf( 3.求二叉树指定结点的路径 n); printf( 0.退 出 系 统n);printf(=n);printf( 请选择：(0-3) n);scanf(%d,&xz); getchar();switch(xz) / 输入:ABCDEGF 输出: CBEGDFA case 1:printf(输入二叉树的先序序列结点值:n); CreateBiTree(bt); printf(二叉树的链式存储结构建立完成! n); break; case 2:printf(该二叉树的中序遍历序列是:n); Inorder(bt);printf(n); break; case 3:printf(输入要求路径的节点值：n); ch1=getchar(); p =