/ 指向当前要检查的节点?
? ? BiTree previsited = 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)? ?
? ? ? ? {? ?
? ? ? ? ? ? cout<data<<"? ";? ?
? ? ? ? ? ? previsited = curr;? ?
? ? ? ? ? ? S.pop();? ?
? ? ? ? ? ? curr = NULL;? ?
? ? ? ? }? ?
? ? ? ? else?
? ? ? ? ? ? curr = curr->rchild;? ? ? // 否则访问右孩子?
? ? }? ?
}?
?
void PostOrder_Nonrecursive(BiTree T)? // 后序遍历的非递归? ? 双栈法?
{? ?
? ? stack s1 , s2;? ?
? ? BiTree curr ;? ? ? ? ? // 指向当前要检查的节点?
? ? 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();?
? ? }?
}?
?
?
int visit(BiTree T)?
{?
? ? if(T)?
? ? {?
? ? ? ? printf("%c ",T->data);?
? ? ? ? return 1;?
? ? }?
? ? else?
? ? ? ? return 0;?
}?
?
void LeverTraverse(BiTree T)? //方法一、非递归层次遍历二叉树?
{?
? ? queue Q;?
? ? BiTree p;?
? ? 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);?
? ? }?
}?
void LevelOrder(BiTree BT)? ? //方法二、非递归层次遍历二叉树?
{?
? ? BiTNode *queue[10];//定义队列有十个空间?
? ? if (BT==NULL)?
? ? ? ? return;?
? ? int front,rear;?
? ? front=rear=0;?
? ? queue[rear++]=BT;?
? ? while(front!=rear)//如果队尾指针不等于对头指针时?
? ? {?
? ? ? ? cout<data<<"? ";? //输出遍历结果?
? ? ? ? if(queue[front]->lchild!=NULL)? //将队首结点的左孩子指针入队列?
? ? ? ? {?
? ? ? ? ? ? queue[rear]=queue[front]->lchild;?
? ? ? ? ? ? rear++;? ? //队尾指针后移一位?
? ? ? ? }?
? ? ? ? if(queue[front]->rchild!=NULL)?
? ? ? ? {?
? ? ? ? ? ? queue[rear]=queue[front]->rchild;? ? //将队首结点的右孩子指针入队列?
? ? ? ? ? ? rear++;? //队尾指针后移一位?
? ? ? ? }?
? ? ? ? front++;? ? //对头指针后移一位?
? ? }?
}?
?
int depth(BiTNode *T)? //树的深度?
{?
? ? if(!T)?
? ? ? ? return 0;?
? ? int d1,d2;?
? ? d1=depth(T->lchild);?
? ? d2=depth(T->rchild);?
? ? return (d1>d2?d1:d2)+1;?
? ? //return (depth(T->lchild)>depth(T->rchild)?depth(T->lchild):depth(T->rchild))+1;?
}?
int CountNode(BiTNode *T)?
{?
? ? if(T == NULL)?
? ? ? ? return 0;?
? ? return 1+CountNode(T->lchild)+CountNode(T->rchild);?
}?
?
int main(void)?
{?
? ? BiTNode *root=NULL; //定义一个根结点?
? ? int flag=1,k;?
? ? printf("? ? ? ? ? ? ? ? ? ? 本程序实现二叉树的基本操作。\n");?
? ? printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。\n");?
?
? ? while(flag)?
? ? {?
? ? ? ? printf("\n");?
? ? ? ? printf("|--------------------------------------------------------------|\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? 二叉树的基本操作如下:? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? ? ? 0.创建二叉树? ? ? ? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? ? ? 1.递归先序遍历? ? ? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? ? ? 2.递归中序遍历? ? ? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? ? ? 3.递归后序遍历? ? ? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? ? ? 4.非递归先序遍历? ? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? ? ? 5.非递归中序遍历? ? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? ? ? 6.非递归后序遍历? ? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? ? ? 7.非递归层序遍历? ? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? ? ? 8.二叉树的深度? ? ? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? ? ? 9.二叉树的结点个数? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|? ? ? ? ? ? ? ? ? ? ? ? 10.退出程序? ? ? ? ? ? ? ? ? ? ? ? ? ? |\n");?
? ? ? ? printf("|---------------------------------------------------- |