数据结构常用算法分析(C++版)-从树的遍历看递归展开

很久很久以前，刚学C++的时候，觉得递归好神奇呀，好难理解呀！能够熟练识别递归问题，运用递归去解决是多么了不起的事情呀！感觉递归总能够把大事情，划分为小事情，是多么的神奇！

现在，虽然有时候遇到递归问题，依然不能一眼看出来，但是总是抑制不住自己打开递归的冲动，总在想：如果能够不用递归方法去解决递归问题，才是多么了不起的一件事情~

所以这里就来初窥递归的展开！

本文主要内容是从树的3种遍历方式：先序遍历、中序遍历、后续遍历实际问题出发，针对 2中递归方式：尾部递归、其他递归，来讲解一下，常用递归展开的基本思想与方法。

本文的代码已经托管到了github: 我是代码，快点我~

数据结构

在讲述树的递归时，使用以下的数据结构：包括树类、节点类2个


//节点类
template <typename T1>
class tree_node
{
public:
	T1 data;
	tree_node * lchild;
	tree_node * rchild;
	tree_node()
	{
		lchild=NULL;
		rchild=NULL;
	}
	tree_node(T1 d)
	{
		data=d;
		lchild=NULL;
		rchild=NULL;
	}
};

//树类
template <typename T>
class tree
{
public:
	tree_node<T> * root;
	void pre_travel1(const tree_node<T> *) const;
	void mid_travel1(const tree_node<T> *) const;
	void post_travel1(const tree_node<T> *) const;
	void level_travel(tree_node<T> *);
	void pre_travel2(tree_node<T> *);
	void mid_travel2(tree_node<T> *);
	void post_travel2(tree_node<T> *);
};

尾递归还是伪递归

这小节先讲一下尾递归的展开与优化，以求和为例，讲述尾递归与迭代的关系：有时候代码尾递归，运行并不是递归！

尾递归举例


//前n个数求和

//递归形式
int add(int n)
{
	if(n==1) return 1;
	return n+add(n-1)
}


//迭代形式
int add2(int n)
{
	int n_pre;
	int sum =0;
	for(int i=1;i<=n;i++)
	{
		n_pre=i;//这里引入n_pre 表示上一次递归的add()结果，
		sum+=i;//总和与上一次值相加
	}
}

偷偷告诉你

从上面代码可以看出，尾递归展开不需要保存递归调用时的栈数据，只需要O(1)大小的变量，去保存上一次的结果！

另外，为什么叫“伪递归”呢？那是因为尾递归是能够被编译器自动优化的,如：

gcc -O2 add.c -o add.out

其他递归

好了，重头戏来了，现在呢，就来看看树的遍历吧，本文以二叉树为例！

递归遍历

首先使用递归的思想进行树的遍历：


//先序
template <typename T>
void tree<T>::pre_travel1(const tree_node<T> * root)  const
{
	if(root == NULL) return;
	cout<<root->data<<endl; //!!!!!!!!!!
	pre_travel1(root->lchild);
	pre_travel1(root->rchild);
}

//中序
template <typename T>
void tree<T>::mid_travel1(const tree_node<T> * root) const
{
	if(root == NULL) return;
	mid_travel1(root->lchild);
	cout<<root->data<<endl; //!!!!!!!!!!
	mid_travel1(root->rchild);
}

//后序
template <typename T>
void tree<T>::post_travel1(const tree_node<T> * root) const
{
	if(root == NULL) return;
	post_travel1(root->lchild);
	post_travel1(root->rchild);
	cout<<root->data<<endl; //!!!!!!!!!!
}

呐，上面就是树遍历的递归实现，是不是超级简单，只需要调整输出的位置，就能轻松改变遍历方式， 当然，这得益于树本身就是使用递归进行定义的！

循环遍历

下面就从非递归的角度，来看树递归的原理！告诉你树遍历的本质~

在写循环遍历时，有大量边界情况需要处理，为了方便理解&记忆，引入以下编程规范：

空指针可入栈/队；
需要先判断栈顶元素是否为NULL，才可使用栈顶元素；
需要先判断栈是否为空，才可进行pop()

先序遍历

先序遍历算法的基本思想是： 每次循环都是一个新树，右孩子入栈

从根节点，向左深入，并输出路径上的节点，路径上节点的右孩子依次入栈；
若左孩子为NULL，则最近的右孩子出栈，并作为根节点进入下一次循环；
直到栈为空，所有右孩子访问完毕！即整棵树遍历完毕~


template <typename T>
void tree<T>::pre_travel2(tree_node<T> * root)
{
	stack<tree_node<T> *> s;
	s.push(root);
	while(!s.empty())//
	{
		if(root == NULL)//到叶子节点了
		{
			root= s.top();
			s.pop();
			continue;
		}
		cout<<root->data<<endl;//输出节点
		s.push(root->rchild);
		root = root->lchild;//更换环境节点
	}
}

中序遍历

中序遍历算法的基本思想：每个循环都是一个新树，根节点入栈

从根节点开始，向左深入，并入栈每个节点；
栈顶元素为NULL，退栈，输出根节点，右孩子入栈；
以右孩子为根，开始下一轮新树循环

template <typename T>
void tree<T>::mid_travel2(tree_node<T> * root)
{
	stack<tree_node<T> *> s;
	if(root == NULL)
	{
		return;
	}
	s.push(root);
	while(!s.empty())  //每个新循环，都是新“树根”
	{
		while(root = s.top())//找到左下角元素
		{
			s.push(root -> lchild);
		}
		s.pop();   //删去空指针
		if(!s.empty())
		{
			root = s.top();
			s.pop();
			cout<<root->data<<endl;
			s.push(root -> rchild);//准备更换环境节点
		}
	}
}

后续遍历

中序遍历算法的基本思想：每个循环都是一个新树，根基点入栈，用旧节点确定从哪返回

从根节点开始，向左深入，并入栈每个节点；
栈顶元素为NULL，退栈，输出左孩子，保存刚刚输出的节点，环境节点置为父节点，
如果环境节点从右节点返回，那么输出环境节点，并继续回退栈
如果从左节点返回，那么右节点入栈，并作为树根，开始新树循环


template <typename T>
void tree<T>::post_travel2(tree_node<T> * root)
{
	tree_node <T> * oldnode=NULL;//保存前一个节点，判断是否是从右节点返回
	stack<tree_node<T> *> s;
	if(root == NULL)
	{
		return;
	}
	s.push(root);
	while(!s.empty())  //每个新循环，都是新“树根”
	{
		while(root = s.top())//找到左下角元素
		{
			s.push(root -> lchild);
		}
		s.pop();
		root = s.top();
		cout<<root->data<<endl;//输出左孩子
		oldnode = root;
		s.empty()? NULL:s.pop();
		root=(s.empty()? NULL:s.top());//返回父节点
		while(!s.empty())
		{
			if(root->rchild==oldnode)//从右节点返回，继续输出根节点
			{
				cout<<root->data<<endl;
				oldnode=root;
				s.empty()? NULL:s.pop();
				s.empty()? NULL:root = s.top(); 
			}
			else //从左孩子返回,为新树
			{
				s.push(root->rchild);//有右节点，//准备更换环境节点索
				break;
			}
		}
	}
}

题外话：层序遍历

层序遍历使用队列作为辅助存储，循环之后，每个节点就乖乖听话，依次排好队了，在出队的时候进行输出操作，就可以轻松实现对树的层序遍历！


template <typename T>
void tree<T>::level_travel(tree_node<T> * root) 
{
	queue<tree_node<T> *> q;
	q.push(root);
	while(!q.empty())
	{
		root = q.front();
		cout<<root->data<<endl;
		if(root->lchild)
			q.push(root->lchild);
		if(root->rchild)
			q.push(root->rchild);
		q.pop();
	}
}

主函数



/*
 树结构  ：    
     0
   1   2
  3 4 5  6 
*/

int main()
{
	tree<int> tree;

	tree_node<int> pnode(1);

	tree_node<int> lnode1(1);
	tree_node<int> rnode1(2);
	tree_node<int> lnode2(3);
	tree_node<int> rnode2(4);
	tree_node<int> lnode3(5);
	tree_node<int> rnode3(6);

	tree.root = & pnode;
	tree.root->data=0;
	tree.root->lchild= &lnode1;
	tree.root->rchild= &rnode1;	
	lnode1.lchild= &lnode2;
	lnode1.rchild= &rnode2;	
	rnode1.lchild= &lnode3;
	rnode1.rchild= &rnode3;

	tree.pre_travel2(tree.root);

	return 0;
}

结束

很不开心！写本文的最初目的，是想从这3个树的遍历算法中，类推出递归展开的普遍规律！可是，写完了，才发现，递归展开还是要深入理解每个算法的基本原理，才能对相应的递归进行展开~ 有种白忙活了的感觉，好不爽！不知道是不是我思考的不够深入，求各路大神赐教！

最后介绍一下近况：为了找工作，最近每天都会用1-2个小时复习功课，为了检测效果，前几天做了“同花顺”的实习招聘题目：（服务器和安卓岗位）发现了几个问题：

在线笔试真的很不适应；
自己复习的依然不够深入，基础还是很薄弱；

后面要加油了！

激情！激情！源源不断的激情！Fighting!

小鸟在嗷嗷