搜索
#includeiostream#includequeue#includestack#includecstdio#includemalloc.husingnamespacestd;typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;voidCreateBiTree(BiTNode**root)//二级指针作为函数参数{charch;//要插入的数据scanf(\n%c,&ch);if(ch=='#')*root=NULL;else{*root=(BiTNode*)malloc(sizeof(BiTNode));(*root)-data=ch;printf(请输入%c的左孩子：,ch);CreateBiTree(&((*root)-lchild));printf(请输入%c的右孩子：,ch);CreateBiTree(&((*root)-rchild));}}voidPreOrder(BiTNode*root){if(root==NULL)return;printf(%c,root-data);//输出数据PreOrder(root-lchild);//递归调用，前序遍历左子树PreOrder(root-rchild);//递归调用，前序遍历右子树}voidInOrder(BiTNode*root){if(root==NULL)return;InOrder(root-lchild);//递归调用，前序遍历左子树printf(%c,root-data);//输出数据InOrder(root-rchild);//递归调用，前序遍历右子树}voidPostOrder(BiTNode*root){if(root==NULL)return;PostOrder(root-lchild);//递归调用，前序遍历左子树PostOrder(root-rchild);//递归调用，前序遍历右子树printf(%c,root-data);//输出数据}voidPreOrder_Nonrecursive(BiTreeT)//先序遍历的非递归{if(!T)return;stackBiTrees;s.push(T);while(!s.empty()){BiTreetemp=s.top();couttemp-data;s.pop();if(temp-rchild)s.push(temp-rchild);if(temp-lchild)s.push(temp-lchild);}}voidPreOrder_Nonrecursive1(BiTreeT)//先序遍历的非递归{if(!T)return;stackBiTrees;BiTreecurr=T;while(curr!=NULL||!s.empty()){while(curr!=NULL){coutcurr-data;s.push(curr);curr=curr-lchild;}if(!s.empty()){curr=s.top();s.pop();curr=curr-rchild;}}}voidPreOrder_Nonrecursive2(BiTreeT){if(!T)return;stackBiTrees;while(T){s.push(T);coutT-data;T=T-lchild;}while(!s.empty()){BiTreetemp=s.top()-rchild;//栈顶元素的右子树s.pop();//弹出栈顶元素while(temp)//栈顶元素存在右子树，则对右子树同样遍历到最下方{couttemp-data;s.push(temp);temp=temp-lchild;}}}voidInOrderTraverse1(BiTreeT)//中序遍历的非递归{if(!T)return;BiTreecurr=T;//指向当前要检查的节点stackBiTrees;while(curr!=NULL||!s.empty()){while(curr!=NULL){s.push(curr);curr=curr-lchild;}//whileif(!s.empty()){curr=s.top();s.pop();coutcurr-data;curr=curr-rchild;}}}voidInOrderTraverse(BiTreeT)//中序遍历的非递归{if(!T)return;stackBiTrees;BiTreecurr=T-lchild;//指向当前要检查的节点s.push(T);while(curr!=NULL||!s.empty()){while(curr!=NULL)//一直向左走{s.push(curr);curr=curr-lchild;}curr=s.top();s.pop();coutcurr-data;curr=curr-rchild;}}voidPostOrder_Nonrecursive1(BiTreeT)//后序遍历的非递归{stackBiTreeS;BiTreecurr=T;//指向当前要检查的节点BiTreeprevisited=NULL;//指向前一个被访问的节点while(curr!=NULL||!S.empty())//栈空时结束{while(curr!=NULL)//一直向左走直到为空{S.push(curr);curr=curr-lchild;}curr=S.top();//当前节点的右孩子如果为空或者已经被访问，则访问当前节点if(curr-rchild==NULL||curr-rchild==previsited){coutcurr-data;previsited=curr;S.pop();curr=NULL;}elsecurr=curr-rchild;//否则访问右孩子}}voidPostOrder_Nonrecursive(BiTreeT)//后序遍历的非递归双栈法{stackBiTrees1,s2;BiTreecurr;//指向当前要检查的节点s1.push(T);while(!s1.empty())//栈空时结束{curr=s1.top();s1.pop();s2.push(curr);if(curr-lchild)s1.push(curr-lchild);if(curr-rchild)s1.push(curr-rchild);}while(!s2.empty()){printf(%c,s2.top()-data);s2.pop();}}intvisit(BiTreeT){if(T){printf(%c,T-data);return1;}elsereturn0;}voidLeverTraverse(BiTreeT)//方法一、非递归层次遍历二叉树{queueBiTreeQ;BiTreep;p=T;if(visit(p)==1)Q.push(p);while(!Q.empty()){p=Q.front();Q.pop();if(visit(p-lchild)==1)Q.push(p-lchild);if(visit(p-rchild)==1)Q.push(p-rchild);}}voidLevelOrder(BiTreeBT)//方法二、非递归层次遍历二叉树{BiTNode*queue[10];//定义队列有十个空间if(BT==NULL)return;intfront,rear;front=rear=0;queue[rear++]=BT;while(front!=rear)//如果队尾指针不等于对头指针时{coutqueue[front]-data;//输出遍历结果if(queue[front]-lchild!=NULL)//将队首结点的左孩子指针入队列{queue[rear]=queue[front]-lchild;rear++;//队尾指针后移一位}if(queue[front]-rchild!=NULL){queue[rear]=queue[front]-rchild;//将队首结点的右孩子指针入队列rear++;//队尾指针后移一位}front++;//对头指针后移一位}}intdepth(BiTNode*T)//树的深度{if(!T)return0;intd1,d2;d1=depth(T-lchild);d2=depth(T-rchild);return(d1d2?d1:d2)+1;//return(depth(T-lchild)depth(T-rchild)?depth(T-lchild):depth(T-rchild))+1;}intCountNode(BiTNode*T){if(T==NULL)return0;return1+CountNode(T-lchild)+CountNode(T-rchild);}intmain(void){BiTNode*root=NULL;//定义一个根结点intflag=1,k;printf(请建立二叉树并输入二叉树的根节点：);CreateBiTree(&root);printf(递归先序遍历二叉树的结果为：);PreOrder(root);printf(\n);printf(递归中序遍历二叉树的结果为：);InOrder(root);printf(\n);printf(递归后序遍历二叉树的结果为：);PostOrder(root);printf(\n);printf(非递归先序遍历二叉树：);PreOrder_Nonrecursive1(root);printf(\n);printf(非递归中序遍历二叉树：);InOrderTraverse1(root);printf(\n);printf(非递归后序遍历二叉树：);PostOrder_Nonrecursive(root);printf(\n);printf(非递归层序遍历二叉树：);//LeverTraverse(root);LevelOrder(root);printf(\n);return0;}