C++ 二叉树-遍历

二叉树--遍历

二叉树的遍历：1，递归遍历，效率低
                             2.非递归遍历
本文实现用堆栈存储二叉树的根节点，进行非递归遍历。

//==========================================//
//程序目的：1.建立二叉树                    //
//          2.递归遍历二叉树                //
//          3.非递归遍历二叉树              //
//          4.非递归遍历用栈保存根地址      //
//          5.用链表实现栈                  //
//Written By HEWEI                          //
//2011 06 01                                //
//==========================================//

#include<iostream>
using namespace std;

#define MAX 20
//------------------------------------------//
//------------树节点的声明------------------//
//------------------------------------------//
struct tree
{
	struct tree *left;
	int Data;
	struct tree *right;
};

typedef struct tree nodetree;
typedef nodetree *b_tree;


//-----------------------------------------//
//--------堆栈节点声明存储树节点-----------//
//-----------------------------------------//
struct List
{
	b_tree Tree_Node;
	struct List *pNext;
};
typedef struct List Node;
typedef Node *Link;
//-----------------------------------------//
//-----------非递归法二叉树节点插入--------//
//-----------------------------------------//
b_tree Insert_Tree(int Data,b_tree root)
{
	b_tree currentnode;  //current节点
	b_tree parentnode;   //current的父节点
	b_tree New;          //新建节点


	//初始化新节点
	New = new nodetree[sizeof(nodetree)];
	New->left = NULL;
	New->Data = Data;
	New->right = NULL;

	//判断root是否为空
	if(root == NULL)
	{
		root = New;
	}
	else
	{
		currentnode = root;
		while(currentnode != NULL)
		{
			//判断插在左节点还是右节点
			if(New->Data <= currentnode->Data) //左节点
			{
				//判断左节点是否为空
				if(currentnode != NULL)
				{
					parentnode = currentnode;   //当前节点的父节点
					currentnode = currentnode->left;
				}
				else
					parentnode = currentnode;  //父节点
			}
			else               //右节点
			{

				//判断左节点是否为空
				if(currentnode != NULL)
				{
					parentnode = currentnode;   //当前节点的父节点
					currentnode = currentnode->right;
				}
				else
					parentnode = currentnode;  //父节点
			}
		}
	
		//找到当前插入的位置后插入数据
		if(Data <= parentnode->Data)
		{
			parentnode->left = New;
		}
		else
			parentnode->right = New;
	}
	return root;
}


//-----------------------------------------//
//------------二叉树的建立-----------------//
//-----------------------------------------//
b_tree Create_Tree(int len,int *pArray)
{
	b_tree root;
	int i;

	root = NULL;
	//数组数据储存到二叉树中
    for(i = 0; i<len; i++)
	{
		root = Insert_Tree( pArray[i],root);
	}
	return root;
}


//-----------------------------------------//
//--------递归前序遍历二叉树---------------//
//-----------------------------------------//
void PerInorder(b_tree Pointer)
{
	if (Pointer == NULL)
		return ;
	else 
	{
		cout << Pointer->Data << " ";
		PerInorder(Pointer->left);
        PerInorder(Pointer->right);
	}
}

//----------------------------------------//
//-------------链表建立堆栈---------------//
//----------------------------------------//
Link Create_List()
{
	//声明根节点
	Link List_Root;
	//初始化根节点
	List_Root = new Node[sizeof(Node)];
	List_Root->pNext = NULL;
	List_Root->Tree_Node = NULL;
    return List_Root;
}

b_tree Pop_List(Link & Head)  //出栈，这里用来引用，引用如何应用
{
	b_tree Pop_Treenode;  //用于储存取出的树节点
	Link Pointer;
	//从前面取出数据
	if(Head == NULL)
	{
		cout << "The List is empty!!"<< endl;
		exit(1);
	}
	else
	{
		Pointer = Head;
		Pop_Treenode = Pointer->Tree_Node;
		Head = Head->pNext;
		free(Pointer);  //删除被取出的节点
	}
	return Pop_Treenode;
}
Link Push_List(Link Head,b_tree New_Node) //入栈
{
	Link Pointer;
	Link New;
	New = new Node[sizeof(Node)];
	New->pNext = NULL;
	New->Tree_Node = New_Node;
	////判断根节点是否为空
	if(Head== NULL)
	{
		Head = New;
	}
	else
	{ 
		Pointer = Head;
		Head=New;
		New->pNext = Pointer;//从前面插入，堆栈，先进后出
	}
	return Head;
}

//----------------------------------------//
//---------非递归前序遍历二叉树-----------//
//----------------------------------------//
void PerSearch(b_tree root)
{
	b_tree Pointer;
    Link NewList;
  
   //初始化
   //NewList = Create_List();
   NewList = NULL;
   Pointer = root;
   
   while(Pointer != NULL || NewList != NULL )
   {
        while(Pointer != NULL)
		{
			cout << Pointer->Data << " ";  //输出当前节点数据
            //将当前节点存储到堆中
            NewList = Push_List(NewList,Pointer);
			Pointer = Pointer->left;
		}
		if(NewList != NULL) //取出堆栈中的存储值进行输出
		{
			Pointer = Pop_List(NewList)->right;
		}
   }
}




//----------------------------------------//
//-----------储存数组元素-----------------//
//----------------------------------------//
void Store_Data(int len,int *pArray)
{
	int i;
	int temp;

	for(i = 0; i <len; i++)
	{
		cout <<"Please Input the Data =>";
		cin >> temp;
		pArray[i] = temp;
	}
}

//----------------------------------------//
//--------------主函数--------------------//
//----------------------------------------//
int main(void)
{
	b_tree root = NULL; //声明根节点  
	int i,index,capacity;  
	int value;  
	int nodelist[MAX];  

	//读取数值到数组中  
	cout <<"Please Input the capacity : ";  
	cin >> capacity;  
	cout << endl;  
	Store_Data(capacity,nodelist);  
	//建立二叉树  
	root = Create_Tree(capacity,nodelist);  
	//遍历二叉树  
	cout <<"递归遍历二叉树:";
	PerInorder(root);  
	cout << endl;
	//非递归遍历二叉树
	cout <<"非递归遍历二叉树 :";
	PerSearch(root);
	cout << endl;
	return 0;
}

在编写Pop_List()函数利用了引用，需要注意一下几点：
1.push堆栈时要从Head处push，而不是从Rear处push，这才是先进后出的理念；若从Rear处push则是队列的理念。
2.pop堆栈时也要从Head处pop，无论堆栈还是队列都要从Head处pop，这样便于操作。
3.pop代码

   pointer = Head;
   Head = Head->pNext;
   free(Pointer);

4.push代码
Head处插入：

pointer = Head;
Head = NewNode;
NewNode->pNext = Pointer;

Rear处插入：

pointer = Head;
while(pointer != NULL)
{
  pointer = pointer->pNext;
}
pointer->pNext = NewNode;

二叉树的非递归遍历：
while循环ree节点，知道节点为空，且栈为空
{
a:当树节点不为空时
1，输出当前节点值；2并把当前树节点压入栈；3，继续往下遍历左节点
b:当遍历到树节点为空且栈top不为空
1，将栈顶元素pop；2，准备遍历pop树节点的右节点
}