二叉树的递归与非递归实现

二叉树的递归实现：

#include <iostream>
using namespace std;
#define LEN sizeof(struct Tree)
struct Tree
{
	int key;
    struct Tree*lchild;
    struct Tree*rchild;
};
//二叉树的创建
void create(struct Tree **p)
{
  *p=new struct Tree [LEN];
  cout<<"请输入二叉树key值:(按0结束当前分支输入)"<<endl;
  cin>>(*p)->key;
  static i=0;
  if ((*p)->key!=0)
  {
	  create((&(*p)->lchild));
	  create((&(*p)->rchild));
  }
}
//先序遍历递归过程。。。。（位置1）
void PreOderTraverse(struct Tree *p)
{//递归实现先序遍历
	if (p->key)
	{
		cout<<p->key<<" ";
		PreOderTraverse(p->lchild);
		PreOderTraverse(p->rchild);
	}
}
//中序遍历
void InOderTraverse(struct Tree *p)
{
    if (p->key)
	{		
		InOderTraverse(p->lchild);
		cout<<p->key<<" ";
		InOderTraverse(p->rchild);
	}
}
//后序遍历
void BackOderTraverse(struct Tree *p)
{
    if (p->key)
	{		
		BackOderTraverse(p->lchild);
		BackOderTraverse(p->rchild);
		cout<<p->key<<" ";
	}
}
void main()
{
    struct Tree *p=NULL;
	create(&p);
	cout<<"先序遍历："<<endl;
	PreOderTraverse(p);
	cout<<endl;
	cout<<"中序遍历："<<endl;
	InOderTraverse(p);
	cout<<endl;
	cout<<"后序遍历："<<endl;
	BackOderTraverse(p);
	cout<<endl;
}

二叉树的非递归实现：

这里我们主要谈一下先序遍历的非递归实现的二种方法。

1，可以直接用C++STL的栈实现：

头文件加上#include <stack>，将上面代码位置1的递归实现二叉树遍历过程替换以下代码即可实现。

//先序遍历非递归过程
void PreOderTraverse(struct Tree *root)  
{  //用C++STL实现很容易。
   if (root == NULL) return; 
   stack<struct Tree *>s; 
   s.push(root);
   while (!s.empty()) {   
    struct Tree *p=s.top();
    cout<<p->key<<" ";
    s.pop();
    if (p->rchild->key != 0) 
	{
      s.push(p->rchild); 
	}
    if (p->lchild->key != 0) 
	{
      s.push(p->lchild);  
	}
}  
cout << endl;  
} 

2.也可以用栈的数组实现，栈的实现，包括PUSH POP等栈操作全部自己实现。这个应该是符合《算法导论》10.4-3题目条件。

#include <iostream>
using namespace std;
#define LEN sizeof(struct Tree)
#define m 10//栈的最大容纳空间可以调整
struct Tree
{
	int key;
    struct Tree*lchild;
    struct Tree*rchild;
};
struct Stack
{
    int top;
    int Array[m];
	bool empty();
	void push(struct Tree*);
	int pop();
}s;
//判断栈是否为空
bool Stack::empty()
{
    if (s.top==-1)
    {
        return true;
    }
    else
    {
        return false;
    }
}
//入栈
void Stack::push(struct Tree*p)
{
    if (s.top==m)
    {
        cerr<<"overflow!"<<endl;
    } 
    else
    {
        s.top++;
        s.Array[s.top]=reinterpret_cast<int>(p);//将树形结构体的地址转化为整数储存到栈里面。
    }
}
//出栈
int Stack::pop()
{
    if (empty())
    {
        cerr<<"underflow"<<endl;
        return NULL;
    }
    else
    {
        s.top--;
        return s.Array[s.top+1];
    }    
}
void create(struct Tree **p)
{
  *p=new struct Tree [LEN];
  cin>>(*p)->key;
  static i=0;
  if ((*p)->key!=0)
  {
	  create((&(*p)->lchild));
	  create((&(*p)->rchild));
  }
} 
void PreOderTraverse(struct Tree *root)  
{  //用栈的数组实现，POP PUSH等函数全部自己来写
	if (root == NULL) return; 
	s.top=-1;
	s.push(root);
	struct Tree *p=root;
	while (!s.empty()) {   
		p=reinterpret_cast<struct Tree *>(s.Array[s.top]);//将数组中的数据恢复为编译器所能识别的指针
		cout<<p->key<<" ";
		s.pop();
		if (p->rchild->key != 0) 
		{
			s.push(p->rchild); 
		}
		if (p->lchild->key != 0) 
		{
			s.push(p->lchild);  
		}
	}  
	cout << endl;  
}
void main()
{
    struct Tree *p=NULL;
	create(&p);
	PreOderTraverse(p);
}

二叉树的递归与非递归实现,布布扣,bubuko.com

二叉树的递归与非递归实现

原文：http://blog.csdn.net/z84616995z/article/details/20854381