[数据结构与算法]数据结构之二叉树的非递归操作

#include<bits/stdc++.h>
using namespace std;

const int Size=100;
//树的定义 
typedef struct BinNode
{
    char ch;
    struct BinNode *lchild,*rchild;//左右孩子指针 
}BinNode,*BiTree;
//栈的定义 
typedef struct stack{
    BinNode* data[Size];
    int sign[Size];//记录经过根节点的次数,第几次 
    int top; 
}Sqstack;
//入栈 
void push(Sqstack *s,BiTree T){
    if(s->top == Size)printf("栈已满\n");
	else
	{	
        s->top++;  //先移动指针后赋值 
        s->data[s->top]=T;
    }
}
//出栈 
BiTree pop(Sqstack *s)
{
    if(s->top==-1)return NULL;//栈为空 
    else
	{
        s->top--;
        return s->data[s->top+1];
    }
}
//先序创建树 
void CreatTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')*T=NULL;
    else
	{
        *T=(BiTree)malloc(sizeof(BinNode));
        (**T).ch=ch; //根节点 
        CreatTree(&(*T)->lchild);//左子树 
        CreatTree(&(*T)->rchild);//右子树 
    }
}
//先序 
void PreDrderTraverse(BiTree T){
    Sqstack P;
    P.top=-1;
    if(T==NULL)printf("该树为空\n");
    else{
        while (T||P.top!=-1)
		{
            while (T)
			{
                printf("%c ",T->ch);
                push(&P,T);
                T=T->lchild;
            }
            T=pop(&P);
            T=T->rchild;
        }
    }
}
//中序 
void MidDrderTraverse(BiTree T){
    Sqstack P;
    P.top=-1;
    if(T==NULL)printf("该树为空\n");
    else{
        while (T||P.top!=-1){
            while (T)
			{
                push(&P,T);
                T=T->lchild;
            }
            T=pop(&P);
            printf("%c ",T->ch);
            T=T->rchild;
        }
    }
}
//后序 
void BackDrderTraverse(BiTree T)
{
    Sqstack P;
    P.top=-1;
    if(T==NULL)printf("该树为空\n");
    else{
        while(T||P.top!=-1)
		{
            while(T)
			{
                push(&P,T);//第一个节点(根节点)入栈 
                P.sign[P.top]=1;//节点标记为左孩子 
                T=T->lchild;//一直访问左孩子至空 
            }
            if(P.sign[P.top]==1)
			{
                T=P.data[P.top];
                T=T->rchild;
				//访问最后一个左孩子节点的右孩子 
                P.sign[P.top]=2;//节点标记为右孩子 
            }
            else
			{
                while (P.sign[P.top]==2)
				{
                    T=pop(&P);
                    printf("%c ",T->ch);
                }
                T=NULL;
            }
        }
    }
}
int DeepTree(BiTree T)
{
	int lenl,lenr;
	if(T==NULL)return 0;
	else
	{
		lenl=DeepTree(T->lchild);
		lenr=DeepTree(T->rchild);
		if(lenl>lenr)return lenl+1;
		else return lenr+1;
	}
} 
int main(){
    BiTree T;
    printf("输入二叉树前序遍历序列:");
    CreatTree(&T);
    printf("先序遍历序列为:");
    PreDrderTraverse(T);
    printf("\n中序遍历序列为:");
    MidDrderTraverse(T);
    printf("\n后序遍历序列为:");
    BackDrderTraverse(T);
    printf("\n树的深度为:");
    printf("%d\n",DeepTree(T));
    return 0;
}