C语言二叉树遍历

      该篇文章为学校数据结构实验代码，包括二叉树的深度优先遍历与广度优先遍历 ，分别包括了递归与非递归的形式。

#include
#include
#define MAXSIZE 50
typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct					//栈
{
	BiTNode* data[MAXSIZE];
	int top;
}SqStack;

//初始化栈
SqStack* InitStack(SqStack* s)
{
	s = (SqStack*)malloc(sizeof(SqStack));
	s->top = -1;
	return s;
}

//销毁栈
void DestroySqStack(SqStack* s)
{
	free(s);
}

//判断栈是否为空
int StackEmpty(SqStack* s)
{
	if (s->top == -1)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

//进栈
void push(SqStack* s, BiTNode* p)
{
	if(s->top == MAXSIZE-1)
	{
		return;
	}
	s->top++;
	s->data[s->top] = p;
}

//出栈
SqStack* pop(SqStack* s)
{
	if (s->top == -1)
	{
		return NULL;
	}
	s->top--;
	return s;
}

//取栈顶
BiTNode* GetTop(SqStack* s)
{
	if (s->top == -1)
	{
		return NULL;
	}
	return s->data[s->top];
}

void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        *T=(BiTree  )malloc(sizeof(BiTNode));
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

//二叉树的先序遍历
void PreOrderTraverse(BiTree T)
{
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
 
void InOrderTraverse(BiTree T)//二叉树的中序遍历
{
   if(T==NULL)
       return ;
   InOrderTraverse(T->lchild);
   printf("%c ",T->data);
   InOrderTraverse(T->rchild);
}
 

void PostOrderTraverse(BiTree T)//后序遍历
{
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}

//递归求二叉树的深度
int TreeDeep1(BiTree T)
{
	if (T == NULL)
		return 0;
	else
	{
		int leftdeep = TreeDeep1(T->lchild);
		int rightdeep = TreeDeep1(T->rchild);
		if (leftdeep >= rightdeep)
			return leftdeep+1;
		else
			return rightdeep+1;
	}
}

void PreOrder1(BiTNode* root)
{
    if (root == NULL)
        return;
    BiTNode* p = root;
    SqStack* s = NULL;
    s = InitStack(s);
    while (!StackEmpty(s) || p != NULL)
    {
        while (p)
        {
            printf("%c ", p->data);
            push(s, p);
            p = p->lchild;
        }
        if (!StackEmpty(s) )
        {
            p=GetTop(s);
            s=pop(s);
            p = p->rchild;
        }
    }
}

//非递归中序遍历 
void InOrder1(BiTNode* b)
{
	
    if (b == NULL)
        return;
    BiTNode* p = b;
    SqStack* s = NULL;
    s = InitStack(s);
    while (!StackEmpty(s) || p != NULL)
    {
        //一直遍历到左子树最下边，边遍历边保存根节点到栈中 
		while (p)	
        {
        	push(s, p);
            p = p->lchild;
        }
        if (!StackEmpty(s))
        {
            p=GetTop(s);
            s=pop(s);
            printf("%c ", p->data);
            p = p->rchild;
        }
    }
}

//后序遍历
void PostOrder1(BiTNode* root)
{
    if (root == NULL)
        return;
    SqStack* s = NULL;
    s = InitStack(s);
    BiTNode* pCur, *pLastVisit;

    pCur = root;
    pLastVisit = NULL;
    while (pCur)
    {
        push(s,pCur);
        pCur = pCur->lchild;
    }
    while (!StackEmpty(s))
    {
        pCur = GetTop(s);
        s=pop(s);
        if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
        {
        	printf("%c ", pCur->data);
            pLastVisit = pCur;
        }
        else
        {
            push(s,pCur);
            pCur = pCur->rchild;
            while (pCur)
            {
                push(s,pCur);
                pCur = pCur->lchild;
            }
        }
    }
}



int TreeDeep2(BiTree T) //非递归求二叉树深度
{
	if (T == NULL)//树空返回0
		return 0;
	else
	{
		BiTree Q[MAXSIZE];//定义一个足够储存树中所有元素的队列
		int front = -1, rear = -1;//front为队头，rear为队尾
		int last = 0, level = 0;//last指向当前层最右节点
		rear++;//指针加一头节点入队
		Q[rear] = T;
		BiTree P =NULL;//定义一个运动指针
		while (front < rear)
		{
			front++;//队头指针加一，队头元素出队
			P = Q[front];
			if (P->lchild != NULL)//左子树不为空，左孩子入队
			{
				rear++;
				Q[rear] = P->lchild;
			}
			if (P->rchild != NULL)//右子树不为空，右孩子入队
			{
				rear++;
				Q[rear] = P->rchild;
			}
			if (front == last)//处理该层最右节点
			{
				level++;//层数加一
				last = rear;//last指向下一层最右节点
			}
 
		}//else
		return level;//返回树的深度
	}//while
 
}

int main()
{
	int m;
    BiTree T;
    CreateBiTree(&T);
    
    printf("n前序遍历:n"); 
    PreOrderTraverse (T);
    printf("n");
    PreOrder1(T);
    
    printf("n中序遍历:n");
    InOrderTraverse(T);
    printf("n");
    InOrder1(T);
    
    printf("n后序遍历:n"); 
    PostOrderTraverse(T);
    printf("n");
    PostOrder1(T);
    
    printf("n深度n");
    m=TreeDeep1(T);
    printf("%d",m);
    return 0;
}