第五章树先序遍历二叉树的非递归算法。后序遍历二叉树的非递归算法。非递归复制二叉树。层序遍历二叉树的非递归算法。求二叉树T中结点p和q的最近共同祖先。（在求最近共同祖先时，可以设立两个辅助数组暂存从根到p,q的路径，查找两条路径上最后一个相同结点。）判断二叉树是否完全二叉树,是则返回1,否则返回0。（提示：可以通过层序遍历的方法来解决。不管当前结点是否有左右孩子,都入队列。这样当树为完全二叉树时，遍历时得到是一个连续的不包含空指针的序列。）求孩子兄弟链表表示的树T的度。求孩子兄弟链表表示的树T的深度。1、voidPreOrder_Nonrecursive(BitreeT)//先序遍历二叉树的非递归算法{InitStack(S);Push(S,T);//根指针进栈while(!StackEmpty(S)){while(Gettop(S,p)&&p){visit(p->data);push(S,p->lchild);}//向左走到尽头pop(S,p);if(!StackEmpty(S)){pop(S,p);push(S,p->rchild);//向右一步}}//while}//PreOrder_Nonrecursive2、typedefstruct{BTNode*ptr;enum{0,1,2}mark;}PMType;//有mark域的结点指针类型voidPostOrder_Stack(BiTreeT)//后续遍历二叉树的非递归算法,用栈{PMTypea;InitStack(S);//S的元素为PMType类型Push(S,{T,0});//根结点入栈while(!StackEmpty(S)){Pop(S,a);switch(a.mark){case0:Push(S,{a.ptr,1});//修改mark域if(a.ptr->lchild)Push(S,{a.ptr->lchild,0});//访问左子树break;case1:Push(S,{a.ptr,2});//修改mark域if(a.ptr->rchild)Push(S,{a.ptr->rchild,0});//访问右子树break;case2:visit(a.ptr);//访问结点,返回}}//while}//PostOrder_Stack分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作。3、voidBitree_Copy_Nonrecursive(BitreeT,Bitree&U)//非递归复制二叉树{InitStack(S1);InitStack(S2);push(S1,T);visited(T->data)=T;//根指针进栈U=(BTNode*)malloc(sizeof(BTNode));U->data=T->data;q=U;push(S2,U);while(!StackEmpty(S)){while(Gettop(S1,p)&&(p->lchild)&&!visited(p->lchild->data)){push(S1,p->lchild);p=p->lchild;visited(p->data)=T;q->lchild=(BTNode*)malloc(sizeof(BTNode));q=q->lchild;q->data=p->data;push(S2,q);}//向左走到尽头if(!StackEmpty(S1)){pop(S1,p);pop(S2,q);if(p->rchild){push(S1,p->rchild);p=p->rchild;visited(p->data)=T;q->rchild=(BTNode*)malloc(sizeof(BTNode));q=q->rchild;q->data=p->data;push(S2,q);}else{pop(s1,p);pop(s2,q);}}//while}//BiTree_Copy_Nonrecursive4、voidLayerOrder(BitreeT)//层序遍历二叉树{InitQueue(Q);//建立工作队列EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);visit(p);if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}//LayerOrder5、intfound=FALSE;Bitree*Find_Near_Ancient(BitreeT,