二叉树的非递归算法

先序遍历非递归算法1

先序遍历非递归算法2

非递归交换左右孩子算法

使用栈来实现二叉树的非递归算法
栈的基本算法

#include<stdio.h>
#include<bits/stdc++.h> 
typedef int Status;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef char TElemType;

// ------栈的顺序存储结构表示----------
#define STACK_INIT_SIZE 100 	// 存储空间初始分配量
#define STACK_INCREMENT 10 	// 存储空间分配增量
typedef struct BiNode 
{
	TElemType data;
	struct BiNode *lchild;
	struct BiNode *rchild;
}BiNode,*BiTree;

typedef BiNode*  ElemType;
typedef struct {
  ElemType *base; 	// 栈底指针
  ElemType *top; 	// 栈顶指针
  int stacksize; 	// 栈空间大小
} SqStack;


void InitStack(SqStack &S)
{
    // 构造一个空栈S
    if(!(S.base = (ElemType *)malloc(STACK_INIT_SIZE 
                                  * sizeof(ElemType))))
        exit(OVERFLOW);     // 存储分配失败
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
}

void DestroyStack(SqStack &S)
{
    // 销毁栈S，S不再存在
    free(S.base);
    S.base = NULL;
    S.top = NULL;
    S.stacksize = 0;
}

void Push(SqStack &S, ElemType e)
{
    if(S.top - S.base >= S.stacksize) { // 栈满，追加存储空间
        S.base = (ElemType *)realloc(S.base, (S.stacksize 
              + STACK_INCREMENT) * sizeof(ElemType));
        if(!S.base)
            exit(OVERFLOW);           // 存储分配失败
        S.top = S.base + S.stacksize;
        S.stacksize += STACK_INCREMENT;
    }
    *(S.top)++ = e;
}

Status Pop(SqStack &S, ElemType &e)
{
    // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；
    // 否则返回ERROR
    if(S.top == S.base)
        return ERROR;
    e = *--S.top;
    return OK;
}

Status GetTop(SqStack S, ElemType &e)
{
    // 若栈不空，则用e返回S的栈顶元素，并返回OK；
    // 否则返回ERROR
    if(S.top > S.base) {
        e = *(S.top - 1);
        return OK;
    }
    else
        return ERROR;
}

Status StackEmpty(SqStack S)
{
    // 若栈S为空栈，则返回TRUE，否则返回FALSE
    if(S.top == S.base)
        return TRUE;
    else
        return FALSE;
}

先序遍历非递归算法1

void preorder1(BiTree T)//先序遍历算法1 
{
	BiTree p;
	SqStack st;
	InitStack(st);
	if(T!=NULL)
	{
		Push(st,T);//根结点进栈
		while(!StackEmpty(st))//栈不为空时循环
		{
			Pop(st,p);
			printf("%c ",p->data);//退栈结点p并访问
			
			if(p->rchild!=NULL)//有右孩子时将其进栈
				Push(st,p->rchild);
				
			if(p->lchild!=NULL)//有左孩子时将其进栈
				Push(st,p->lchild);
		}
	}
}

先序遍历非递归算法2

void preorder2(BiTree T)//先序遍历算法2 
{
	BiTree p;
	SqStack st;
	InitStack(st);
	p=T;

		while(!StackEmpty(st)||p!=NULL)
		{
			while(p!=NULL)//访问结点p及其所有左下结点并进栈
			{
				printf("%c ",p->data);
				Push(st,p);
				p=p->lchild;	
			}
			if(!StackEmpty(st))//若栈不空
			{
				Pop(st,p);//出栈结点p
				p=p->rchild;//转向处理其右子树
			}
		}
   
}

非递归交换左右孩子算法
思路：与二叉树的非递归遍历算法相似

 
void Exchange_lchild_rchild(BiTree T)//交换左右子树算法 
{
	BiTree p;
	SqStack st;
	InitStack(st);
	if(T==NULL) return; 
	
	if(T->lchild!=NULL||T->rchild!=NULL)//只要是非叶子结点 
	{
		Push(st,T);//根结点进栈
		while(!StackEmpty(st))//栈不为空时循环
		{
			Pop(st,p);
			
			
			BiTree temp;
			temp=p->lchild;
			p->lchild=p->rchild;
			p->rchild=temp;

			if(p->rchild!=NULL)//有右孩子时将其进栈
				Push(st,p->rchild);
				
			if(p->lchild!=NULL)//有左孩子时将其进栈
				Push(st,p->lchild);
		}
	}
		
	
}