2021-10-15【数据结构/严蔚敏】【二叉树的前/中/后/递归/非递归遍历&层序遍历】【代码实现算法6.1-6.4】

因为非递归版需要用到 栈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;
}

具体实现请看：

二叉树的前序遍历

递归版

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;
}

具体实现请看：

代码实现

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;
}