因为非递归版需要用到 栈stack 的操作


#define SElemType BiTree
// -----栈的链式存储结构----------------------------------
typedef struct SNode {
   
    SElemType data;                 // 数据域
    struct SNode *next;             // 指针域
} SNode, *LinkStack;


Status InitStack(LinkStack& S)
{
   
	S = (LinkStack)malloc(sizeof(SNode));
	if (!S)
		return 0;
	S->next = NULL;
}

Status DestroyStack(LinkStack& S)
{
   
	LinkStack p = S->next, ptmp;
	while (p) {
   
		ptmp = p->next;
		free(p);
		p = ptmp;
	}
	free(S);
	return 1;
}

Status ClearStack(LinkStack& S)
{
   
	LinkStack p = S->next, ptmp;
	while (p) {
   
		ptmp = p->next;
		free(p);
		p = ptmp;
	}
	S->next = NULL;
	return 1;
}

Status StackEmpty(LinkStack& S)
{
   
	return S->next == NULL;
}

int StackLength(LinkStack S)
{
   
	int ans = 0;
	LinkStack p = S->next;
	while (p) {
   
		ans++;
		p = p->next;
	}
	return ans;
}

Status GetTop(LinkStack S, SElemType& e)
{
   
	if (S->next == NULL)
		return 0;
	e = S->next->data;
	return 1;
}

Status Push(LinkStack& S, SElemType e)
{
   
	SNode* p = (SNode*)malloc(sizeof(SNode));
	p->data = e;
	p->next = S->next;
	S->next = p;
	return 1;
}

Status Pop(LinkStack& S, SElemType& e)
{
   
	if (S->next == NULL)
		return 0;
	e = S->next->data;
	SNode* p = S->next;
	S->next = p->next;
	free(p);
	return 1;
}

Status Visit(TElemType e){
   
    cout << e << " ";
    return 1;
}

具体实现请看:
2021-9-22【数据结构/严蔚敏】【顺序栈&链式栈&迷宫求解&表达式求值】【代码实现算法3.1-3.5】

二叉树的前序遍历

递归版

Status Visit(TElemType e){
   
    cout << e;
    return 1;
}
//先序遍历
//算法6.1
Status PreOrderTraverse(BiTree T,Status Visit(TElemType e)){
   
    if(T){
   
        Visit(T->data);
        PreOrderTraverse(T->lchild, Visit);
        PreOrderTraverse(T->rchild, Visit);
    }
}

非递归版

//先序遍历
Status PreOrderTraverse1(BiTree T,Status Visit(TElemType e))
{
   
	if (T == NULL)
		return 0;
    BiTree p;
    LinkStack s;
    InitStack(s);
    Push(s, T);//根进栈
    while (!StackEmpty(s))
	{
   
		while(GetTop(s,p) && p){
   
            if(!Visit(p->data))
                return 0;
            Push(s, p->lchild); //左走到尽头
		}
        Pop(s, p);  //空指针退栈
        if(!StackEmpty(s)){
   //访问结点
            Pop(s, p);
            Push(s, p->rchild);
        }
	}
    return 1;
}

Status PreOrderTraverse2(BiTree T,Status Visit(TElemType e))
{
   
	if (T == NULL)
		return 0;
    BiTree p = T, e;
    LinkStack s;
    InitStack(s);
    while (p || !StackEmpty(s))
	{
   
        if(p){
             //根指针进栈,遍历左子树
            if(!Visit(p->data))
                return 0;
            Push(s, p);
            p = p->lchild;
        }else{
             //根指针退栈,访问根结点,遍历右子树
            Pop(s, p);
            p = p->rchild;
        }
	}
    return 1;
}


中序遍历

递归版


//中序遍历
Status InOrderTraverse(BiTree T,Status Visit(TElemType e)){
   
    if(T!=NULL){
   
	    InOrderTraverse(T->lchild, Visit);
	    Visit(T->data);
	    InOrderTraverse(T->rchild, Visit);
	}
}

非递归版

//中序非递归实现
//算法6.2
Status InOrderTraverse1(BiTree T,Status Visit(TElemType e))
{
   
	if (T == NULL)
		return 0;
    BiTree p;
    LinkStack s;
    InitStack(s);
    Push(s, T);//根进栈
    while (!StackEmpty(s))
	{
   
		while(GetTop(s,p) && p){
   
            Push(s, p->lchild); //左走到尽头
		}
        Pop(s, p);  //空指针退栈
        if(!StackEmpty(s)){
   //访问结点
            Pop(s, p);
            if(!Visit(p->data))
                return 0;
            Push(s, p->rchild);
        }
	}
    return 1;
}
//算法6.3
Status InOrderTraverse2(BiTree T,Status Visit(TElemType e))
{
   
	if (T == NULL)
		return 0;
    BiTree p = T, e;
    LinkStack s;
    InitStack(s);
    while (p || !StackEmpty(s))
	{
   
        if(p){
             //根指针进栈,遍历左子树
            Push(s, p);
            p = p->lchild;
        }else{
             //根指针退栈,访问根结点,遍历右子树
            Pop(s, p);
            if(!Visit(p->data))
                return 0;
            p = p->rchild;
        }
	}
    return 1;
}

后序遍历

递归版


//后序遍历
Status PostOrderTraverse(BiTree T,Status Visit(TElemType e)){
   
    if(T!=NULL){
   
	    PostOrderTraverse(T->lchild, Visit);
	    PostOrderTraverse(T->rchild, Visit);
        Visit(T->data);
    }
}

非递归版

//后序非递归
Status PostOrderrTraverse2(BiTree T, Status(*Visit)(TElemType e))
{
   
	if (T == NULL)
		return 0;
	BiTree p = T, r = NULL;
	LinkStack s;
	InitStack(s);
	while ( p != NULL || !StackEmpty(s))
	{
   
		if (p) {
   
			Push(s, p);
			p = p->lchild;
		}
		else
		{
   
			GetTop(s, p);
			if (p->rchild && p->rchild != r) {
   
				p = p->rchild;
				Push(s, p);
				p = p->lchild;
			}
			else
			{
   
				Pop(s, p);
				Visit(p->data);
				r = p;
				p = NULL;
			}
		}
    }
	return 1;
}

层序遍历

层序遍历需要使用队列queue


//层次遍历
#define QElemType BiTree
#define Status int
//---------链队列实现--------------
typedef struct QNode{
   
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct{
   
    QueuePtr front;
    QueuePtr rear;
} LinkQueue;
Status QueueEmpty(LinkQueue Q){
   
    if (Q.front == Q.rear)
        return 1;
    else
        return 0;
}
Status InitQueue(LinkQueue &Q){
   
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front)
        exit(_OVERFLOW);
    Q.front->next = NULL;
    return 1;
}
Status EnQueue(LinkQueue &Q, QElemType e){
   
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if (!p)
        exit(_OVERFLOW);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p; 
    Q.rear = p;    
    return 1;
}

Status DeQueue(LinkQueue &Q, QElemType &e){
   
    QueuePtr p;
    if (Q.front == Q.rear)
        return 0;
    p = Q.front->next;   
    e = p->data;           
    Q.front->next = p->next; 
    if (Q.rear == p)  
        Q.rear = Q.front;
    free(p);
    return 1;
}

具体实现请看:
2021-9-27【数据结构/严蔚敏】【链队列】

代码实现

Status LevelOrderTraverse(BiTree &T){
   
	LinkQueue lq;
    InitQueue(lq);
    QElemType q;
    EnQueue(lq, T);
    while (QueueEmpty(lq) != 1){
    //队列不空,则出队
        DeQueue(lq, q);
        printf("%c ", q->data);
        if(q->lchild)
            EnQueue(lq, q->lchild); //若有左孩子,则入队
        if(q->rchild)
            EnQueue(lq, q->rchild); //若有右孩子,则入队
    }
    return 1; 
}

int main(){
   
    printf("测试代码\n");
	BiTree T;
	T = (BiTree)malloc(sizeof(BiTNode));
	printf("请给二叉树按照先序方式依次输入结点的值(空结点为#):\n");
	CreateBiTree(T);
	printf("层序方式遍历结果:\n");
	LevelOrderTraverse(T);
	printf("\n");
    return 0;
}