Status InOrderTraverse Non Recur 2 (BiTree T, Status (*visit)(ElemType))I //非递归中序遍历二叉树T /何时递归:根结点不空时将左孩子入栈作新根结点 /何时不递归:根结点为空时不递归,此后当前空根结点出栈,访问下一个栈顶元素并将其右孩子结点入 栈 /当栈中不含元素时整个树遍历完毕 InitStack(S) BiNOde*p;//实际 BiTree与 BiNOde*等价,具体根据上下文含义确定用谁,如根结点可声明为 BiTree 类型,指向结点的指针可声明为 BiNOde*类型 if(T){ printf("空树"); return ERROR;} else Push(S, T) while(!StackEmpty(S)) while( Get Top(S,p)&&p)Push(S,p-> Child;/p的左孩子入栈,直到入栈元素为空指针,此循 环后栈顶元素为NULL,相当于走到左子树外 Pop(S,p)://左子树是空树,对应的空指针出栈,下一步将访问根结点 if(! StackEmpty(S){//若栈中尚有元素代表未遍历完,下面访问栈顶根结点,之后栈顶跟结 点的右孩子入栈 Pop(s, p) (=*visit)(p) Push(S, p>rchild void main o BiTree bit CreateBiTree(BiT rinf("二叉树BiT的先序输出序列为:") PreOrderTraverse(BiT. PrintTElem printf("\n") printf("二叉树BiT的中序输出为:") InOrderTraverse(BiT, PrintTElem): printf("\") rinf("二叉树BiT后序输出为:") PostOrderTraverse(biT. PrintTElem printf("\n\n") rinf("二叉树BiT树深:%dn", TreeDepth(BiT) printf("二叉树BiT结点总数:%dn", Nodecount(BiT)) printf("递归求得二叉树BiT叶子结点数为:%d\n", LeafCount(BiT) int count=o printf("基于先序遍历求二叉树Bi叶子结点数为:%dnn”, PreOrder Leafcount(BiT, count)) TElemType x BiTree p, parent p;// BiTree等价于 BinOde* rinf("输入要查找的元素,元素值前加一个空格:");/此处在%前加一个空格,因在主函数第一个输入语 句执行时用户最后会输入一个回车,此处不加空格则x变为回车,不会再等待输入.若结点元素为整型则无此问 scanf("%c",&x);/此处在%前加一个空格,因在主函数第一个输入语句执行时用户最后会输入一个回车, 此处不加空格则x变为回车,不会再等待输入.若结点元素为整型则无此问题 if(LocateNode(BiT, x, p)=TRUE)( printf("元素%c在BiT中,",p->data f (LocateParent(BiT, x, parent p, LR)) printf("%c结点的双亲结点为%c,",x, parent_p->data) ifLR=0) printf("是双亲的左孩子n") else printf("是双亲的右孩子\n")Status InOrderTraverse_NonRecur_2(BiTree T,Status (*visit)(ElemType)){ //非递归中序遍历二叉树T //何时递归:根结点不空时将左孩子入栈作新根结点, //何时不递归:根结点为空时不递归，此后当前空根结点出栈，访问下一个栈顶元素并将其右孩子结点入 栈 //当栈中不含元素时整个树遍历完毕 SqStack S; InitStack(S); BiTNode* p; //实际BiTree与BiTNode*等价，具体根据上下文含义确定用谁，如根结点可声明为BiTree 类型，指向结点的指针可声明为BiTNode*类型 if(!T){printf("空树");return ERROR;} else{ Push(S,T); while(!StackEmpty(S)){ while( GetTop(S,p)&&p)Push(S,p->lchild);//p的左孩子入栈，直到入栈元素为空指针，此循 环后栈顶元素为NULL，相当于走到左子树外 Pop(S,p);//左子树是空树，对应的空指针出栈，下一步将访问根结点 if(!StackEmpty(S)){ //若栈中尚有元素代表未遍历完,下面访问栈顶根结点，之后栈顶跟结 点的右孩子入栈 Pop(S,p); (*visit)(p); Push(S,p->rchild); } } return OK; } } void main() { BiTree BiT; CreateBiTree(BiT); printf("二叉树BiT的先序输出序列为："); PreOrderTraverse(BiT,PrintTElem); printf("\n"); printf("二叉树BiT的中序输出为："); InOrderTraverse(BiT,PrintTElem); printf("\n"); printf("二叉树BiT后序输出为："); PostOrderTraverse(BiT,PrintTElem); printf("\n\n"); printf("二叉树BiT树深：%d\n",TreeDepth(BiT)); printf("二叉树BiT结点总数：%d\n",NodeCount(BiT)); printf("递归求得二叉树BiT叶子结点数为：%d\n",LeafCount(BiT)); int count=0; printf("基于先序遍历求二叉树BiT叶子结点数为:%d\n\n",PreOrder_LeafCount(BiT,count)); TElemType x; BiTree p,parent_p; //BiTree等价于BiTNode * int LR; printf("输入要查找的元素,元素值前加一个空格：");//此处在%c前加一个空格，因在主函数第一个输入语 句执行时用户最后会输入一个回车，此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问 题 scanf(" %c",&x);//此处在%c前加一个空格，因在主函数第一个输入语句执行时用户最后会输入一个回车， 此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题 if(LocateNode(BiT,x,p)==TRUE){ printf("元素%c在BiT中，",p->data); if(LocateParent(BiT,x,parent_p,LR)){ printf("%c结点的双亲结点为%c，",x,parent_p->data); if(LR==0)printf("是双亲的左孩子\n"); else printf("是双亲的右孩子\n"); }