资源描述：
《建立二叉树并求指定结点路径.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、#include#include#definenum100#defineOK1typedefintStatus;typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BinTNode,*BinTree;intfound;BinTNode*p;StatusCreateBiTree(BinTree&bt){//按照先序遍历次序递归建立二叉树,参见教材P131算法6.4//ABC@@DE@G@@F@@@对应于教材P127
2、图6.8(b)charch;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);//构造右子树}returnOK;}StatusInorder(BinTreebt){//二叉树非递归中序遍历算法BinTNode*p,*s[100];//定义数组栈int
3、i=0;//初始化栈p=bt;do{while(p!=NULL)//扫描根结点及其所有的左结点并将其地址入栈{s[i++]=p;p=p->lchild;}if(i>0)//判断栈是否为空{p=s[--i];//出栈printf("%ct",p->data);//访问结点p=p->rchild;//扫描右子树}}while(i>0
4、
5、p!=NULL);returnOK;}//voidNodePath(BinTreebt,BinTNode*ch){//求二叉树根结点到给定结点*p的路径typedefenum{FALSE,TRUE}boolean;BinT
6、Node*stack[num];//定义栈inttag[num];inti,top;booleanfind;BinTNode*s;find=FALSE;top=0;s=bt;do{while(s!=NULL){//扫描左子树top++;stack[top]=s;tag[top]=0;s=s->lchild;}if(top>0){s=stack[top];if(tag[top]==1){if(s==ch){//找到ch,则显示从根结点到ch的路径for(i=1;i<=top;i++)printf("->%c",stack[i]->data);find=T
7、RUE;}elsetop--;s=stack[top];}//endifif(top>0&&!find){if(tag[top]!=1){s=s->rchild;//扫描右子树tag[top]=1;}elses=NULL;}//endif}//endlif}while(!find&&top!=0);}voidFindBT(BinTreebt,DataTypex){if((bt!=NULL)&&!found){if(bt->data==x){p=bt;found=1;}else{FindBT(bt->lchild,x);//遍历查找左子树FindBT(b
8、t->rchild,x);//遍历查找右子树}}}BinTNode*Findx(BinTreebt,DataTypex){//按给定值查找结点intfound=0;//用found来作为是否查找到的标志BinTreep=NULL;//置空指针FindBT(bt,x);return(p);}voidmain(){BinTreebt;charch1;intxz=1;while(xz){printf("建立二叉树并求指定结点路径");printf("===========================");printf("1.建立二叉树的存储结构
9、n");printf("2.求解二叉树的中序遍历");printf("3.求二叉树指定结点的路径");printf("0.退出系统");printf("===========================");printf("请选择：(0-3)");scanf("%d",&xz);getchar();switch(xz){//输入:ABC@@DE@G@@F@@@输出:CBEGDFAcase1:printf("输入二叉树的先序序列结点值:");CreateBiTree(bt);printf("二叉树的链式存储结构建立完成!"
10、);break;case2:printf("该二叉树的中序遍历序列是:");Inorder
