二叉树的后序遍历（非递归+递归）

• 一、头文件
• • 1.stack.h 栈头文件
  • 2.stack1.h 栈1头文件
  • 3.tree.h 树头文件
• 二、源文件
• • 1.0.后序遍历（递归）
  • 1.1.后序遍历----借助栈----地址的强制转换（非递归）
  • 2.后序遍历----借助栈----二级指针（非递归）
  • 3.删除结点
  • 4.0.查找（非递归）
  • 4.1.查找（递归）
  • 5.找出最大结点
  • 6.入口函数
  • 7.测试结果
• 三、总结

#pragma once
#include 
#include 
#include "tree.h"

using namespace std;

#define MaxSize 128

typedef struct _SqStack
{
	int *base;//栈底指针
	int *top;//栈顶指针 
	
}SqStack;

bool InitStack(SqStack &S)
{
	S.base = new int[MaxSize];
	
	if(!S.base)
		return false;
	
	S.top = S.base;
	
	return true;
}

bool PushStack(SqStack &S,int e)//e 表示地址，地址就是一个整数的值，现在只考虑32位
{
	if(S.top-S.base == MaxSize)
		return false;
	
	*S.top = e;
	S.top++;

	return true;
}

bool PopStack(SqStack &S,int &e)
{
	if(S.base == S.top)
		return false;
	
	e = *(--S.top);
	
	return true; 
}


int GetTop(SqStack &S)
{
	if(S.top != S.base){//非空
		
		return *(S.top-1);
	}
	else
		return NULL; 
}

int GetSize(SqStack &S)
{
	return (S.top-S.base);
} 

bool IsEmpty(SqStack &S)
{
	if(S.top == S.base)
		return true;
	else
		return false;
}

void DestroyStack(SqStack &S)
{
	if(S.base)
		free(S.base);
		
	S.base = NULL;
	S.top  = NULL;
}

#pragma once
#include 
#include 
#include "tree.h"

using namespace std;

#define MaxSize 128

typedef struct _pStack
{
	Bnode **base;//栈底指针
	Bnode **top;//栈顶指针 
	
}pStack;

bool InitStack1(pStack &S)
{
	S.base = new Bnode*[MaxSize];//这里定义一个指针数组
	
	if(!S.base)
		return false;
	
	S.top = S.base;
	
	return true;
}

bool PushStack1(pStack &S,Bnode* e)
{
	if(S.top-S.base == MaxSize)
		return false;
	
	*S.top = e;
	S.top++;

	return true;
}

bool PopStack1(pStack &S,Bnode* &e)
{
	if(S.base == S.top)
		return false;
	
	e = *(--S.top);
	
	return true; 
}


Bnode* GetTop1(pStack &S)
{
	if(S.top != S.base){//非空
		
		return *(S.top-1);
	}
	else
		return NULL; 
}

int GetSize1(pStack &S)
{
	return (S.top-S.base);
} 

bool IsEmpty1(pStack &S)
{
	if(S.top == S.base)
		return true;
	else
		return false;
}

void DestroyStack1(pStack &S)
{
	if(S.base)
		free(S.base);
		
	S.base = NULL;
	S.top  = NULL;
}

这里为什么要给两种栈头文件呢？
是因为后面处理后序遍历的时候特别麻烦，我用了两种方式去解决后序遍历——借助栈，这个大块头，所以继续往下看呗！

#ifndef _TREE_H_
#define _TREE_H_

#define MAX_NODE 1024

#define isLess(a,b) (a
	ElemType data;
	struct _Bnode *lchild;//左子节点指针
	struct _Bnode *rchild;//右子节点指针
}Bnode,Btree;


#endif

void PreOrderRec3(Btree *root)
{
	if(root == NULL)
		return ;

	PreOrderRec3(root->lchild);
	PreOrderRec3(root->rchild);	
	printf("-%d-",root->data);
} 

void PreOrder3(Btree* root)
{
	Bnode* cur = root;
	Bnode* aftercur = root;// 由于我们的访问只能从上到下，所以要多定义一个指针来保存已经被输出的节点,避免访问不到右孩子
	
	
	SqStack stack;
	
	InitStack(stack);
	
	
	while(!(IsEmpty(stack))|| cur!=NULL) 
	{
		
		while(cur!=NULL)
		{
			PushStack(stack,(int)cur);
			cur = cur->lchild;
		}

		Bnode *top1 = (Bnode *)GetTop(stack);
	

		if(top1->rchild == NULL || aftercur == top1->rchild)//如果当前的top右子节点为NULL或者top是右子节点证明已经被遍历过，可以输出top了
		{
			int addr = 0;
			PopStack(stack, addr);//出栈 (根节点，记录器) 
			
			printf("-%d-",top1->data);//打印出栈元素

			aftercur = top1;
		}else
			cur = top1->rchild;//左边遍历完，转向右边
		
	}
	DestroyStack(stack);	
}

void PreOrder3pro(Btree* root)
{
	Bnode *cur2 = root;
	Bnode *aftercur2 = root;

	pStack stack1;

	InitStack1(stack1);

	while(!(IsEmpty1(stack1))||cur2!=NULL)
	{
		while(cur2!=NULL)
		{
			PushStack1(stack1,cur2);
			cur2 = cur2->lchild;
		}

		Bnode *top1 = GetTop1(stack1);

		if(top1->rchild == NULL||top1->rchild == aftercur2)
		{
			PopStack1(stack1,top1);

			printf("-%d-",top1->data);
			
			aftercur2 = top1;
		}else
			cur2 = top1->rchild;
	}
	DestroyStack1(stack1);
}

Btree* DeleteNode(Btree* root,int key, Bnode* &deletedNode)
{
		if(root==NULL)//没有找到删除节点 
			return NULL;
		
		if(root->data>key)//根节点的数据大于 要删除的节点，就往左子树上面找 
		{
			root->lchild = DeleteNode(root->lchild,key, deletedNode);//左子树的节点递归成新的根节点 
			return root;
		}
		if(root->data
			root->rchild = DeleteNode(root->rchild,key, deletedNode);//右子树的节点递归成新的根节点 
			return root;
		}
		
		deletedNode = root;//告诉main函数，被删除的是哪一个数据
		//走到这里说明已经找到了要删除的节点,此时的root就是目标节点 
		
		
		//删除节点不存在左右子节点，即为叶子节点，直接删除
		if(root->lchild==NULL&&root->rchild==NULL)
			return NULL;
		
		//删除节点只存在左子节点，直接用那个左子节点替代要删除的节点
		if(root->lchild!=NULL&&root->rchild==NULL)
			return root->lchild; 
			
		//删除节点只存在右子节点，直接用那个右子节点替代要删除的节点
		if(root->rchild!=NULL&&root->lchild==NULL)
			return root->rchild; 	
			
		//删除节点存在左右节点，直接用要删除节点的左子节点最大值或右子节点的最小值替代删除节点
		int val = findMax(root->lchild);      //	int val = findMax(root->rchild);	
		root->data = val;//用左子树上的最大节点 取代删除节点 
		root->lchild = DeleteNode(root->lchild,val, deletedNode);//递归把左子树的最大节点置空, 上面if(root->data 
4.0.查找（非递归） 
 
Bnode* queryByLoop(Btree* root,ElemType e)
{
	while(root!=NULL && !isEqual(root->data,e))
	{
		if(isLess(e,root->data))
			root = root->lchild;
		else
			root = root->rchild;
	}
	return root;
}
 
4.1.查找（递归） 
Bnode* queryByRec(Btree* root,ElemType e)
{
	if(root == NULL ||isEqual(root->data,e))//找不到该节点 || 找到了该节点   找到了直接返回目标节点到第一次调用该函数的地方 
		return root;
	else if(isLess(e,root->data))
		return queryByRec(root->lchild,e);
	else
		return queryByRec(root->rchild,e);
}
 
5.找出最大结点 
int findMax(Btree* root)
{
	if(!root)
	{
		cout<<"finMax()函数报错！";
		return false;		
	}
	
	
	
	
	 while(root->rchild)
	 {
	 	root = root->rchild;
	 }
	 
	 return root->data;
	 
}
 
这里也同样给出两种方法，利用了二叉搜索树的特性。
 
6.入口函数 
int main()
{
	int test[]={19,7,25,5,11,15,21,61};
	int i; 
	
	Bnode *root = NULL,*node = NULL;
	
	node = new Bnode;
	node->data = test[0];

	//1.插入
	InsertBtree(&root,node);
	
	for(i=1;i
		node = new Bnode;
		node->data = test[i];
		
		if(InsertBtree(&root,node))
		{
			cout<<"节点"<data<<"插入成功!"< 
 
7.测试结果 
 
三、总结 
1.树的遍历有三种，前中后序遍历，这里展示的是后序遍历。
 2.这里是二叉搜索树，遵循“左子树小于右子树”的规律。
 3.后序遍历的栈方法，我这里用了两种方式，注意3.1和3.2用的栈头文件不一样。4.后序遍历的强制转换那里，由于入栈是要入栈cur但是，cur的类型是Bnode*,但是下面的GetTop所取出来的是int类型，为了统一地址类型，我们就把入栈的cur给强制转换成int类型，最后GetTop取出来的int类型地址再进行一个强制转换成结构体指针类型，那么这样做下面的aftercur与top1->rchild的等于判断，才能成立。正是这一点，一开始没有注意到地址类型的统一，使得aftercur与top1->rchild的等于判断一直无法正常进行，程序就没有正常进行
 5.如果采用二级指针就可以保存指针的地址，这样就比单纯处理一级指针要方便很多，可见二级指针还是很有必要的。
 6.后序遍历借助栈，都是很底层的代码了，如果不能理解也没事，因为已经有前辈帮我们写好了前中后序遍历的库函数，我们可以不用递归，通过调用库函数也一样可以实现。我们自己写一写也就只是锻炼一下编程思维，所以如果实在不会就算了。