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


二叉树的递归实现：

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

3.前2种都是用辅助栈的方法实现的，还有一种不用辅助栈，但需要父结点。
(1). 访问左孩子
(2). 访问右孩子
(3). 如果是从右孩子返回，表明整棵子树已访问完，需要沿树而上寻找父节点。直到是从左孩子返回，或者访问到根节点的父节点

#include <iostream>
#include <stack>
using namespace std;
#define LEN sizeof(struct Tree)
struct Tree
{
	int key;
    struct Tree*lchild;
    struct Tree*rchild;
	struct Tree*parent;
};
void create(struct Tree **p)
{
	static struct Tree *p1=NULL;//p1保存当前结点的父亲结点
	*p=new struct Tree [LEN];
	cin>>(*p)->key;
	(*p)->parent=p1;
	p1=*p;
	if ((*p)->key!=0)
	{
		create((&(*p)->lchild));
		p1=*p;	
		create((&(*p)->rchild));
	}
}
void InOderTraverse(struct Tree *p)
{
   if(!p->key) return;
    struct Tree *x=NULL;
    while(1)
    {
        //访问左孩子
        if(x != p->lchild)
        {
            while(p->lchild->key) 
			{
                p=p->lchild;
			}
        }
        cout<<p->key<<" ";
        //访问右孩子
        if(p->rchild->key)
        {
            p=p->rchild;
            continue;
        }
        //回溯
        do
        {
			x=p;
			p=p->parent;
            //访问到根节点的父节点（NULL)
            if(!p) return;
        }while(x==p->rchild);
    }
}
void main()
{
    struct Tree *p=NULL;
	create(&p);
	InOderTraverse(p);
}
这段代码遍历是借鉴网友的，但是创建的过程是自己写的，尤其是如何把父结点和这颗树相联系起来。



相关内容