二叉树的递归遍历以及非递归遍历（一）----先序遍历

1.二叉树的遍历方式：

先序遍历、中序遍历、后序遍历（此处不考虑层次遍历）

先序遍历：先访问根节点，再访问左子树，然后是右子树

中序遍历：先访问左子树，然后是根节点，然后是右子树

后序遍历：先访问左子树，然后右子树，最后是根节点。

2. 二叉树基本数据结构定义：

typedef struct TNode

{

int val;

struct TNode* pLeft;

struct TNode* pRight;

TNode(int val, TNode* pLeft, TNode* pRight)

{

this->val = val;

this->pLeft = pLeft;

this->pRight = pRight;

}

TNode()

{

}

~TNode()

{

if (pLeft)

{

delete pLeft;

pLeft = NULL;

}

if (pRight)

{

delete pRight;

pRight = NULL;

}

}

}TNode;

二叉树的构造：

/**************************************************************************************

4

1 5

2 3 6 7

***************************************************************************************/

TNode* buildTree()

{

TNode *p = new TNode(1,

new TNode(2, NULL,NULL),

new TNode(3, NULL,NULL));

TNode *q = new TNode(4,

p,

new TNode(5,

new TNode(6, NULL,NULL),

new TNode(7, NULL,NULL)));

return q;

};

树的逻辑结构如下：

图一（测试用树结构）

3. 先序遍历

3.1 先序遍历的递归写法：

/**********************************************

功能：递归先序遍历

注：遍历顺序为根左右

**********************************************/

void preTraverse(TNode* pRoot)

{

if (!pRoot) return;

visit(pRoot);

preTraverse(pRoot->pLeft);

preTraverse(pRoot->pRight);

}

3.2 先序遍历的非递归写法：

/**********************************************

功能：非递归先序遍历

住：遍历顺序为根左右

**********************************************/

void preNoRecTraverse(TNode* pRoot)

{

stack<TNode*> s;

TNode* p = pRoot;

s.push(p);

while (p || !s.empty())

{

p = s.top();

s.pop();

visit(p);

if (p->pRight) s.push(p->pRight);

if (p->pLeft) s.push(p->pLeft);

}

}

3.3 过程模拟及结果展示：

递归调用过程：

图二：递归调用的函数调用层次关系

非递归的遍历过程，其实就是模拟递归算法中的堆栈进出顺序。

在递归调用中，可以看到在每一次的递归调用中，总是首先访问根，然后访问左子树，然后访问右子树。对右子树的访问在左子树访问的后面。所以右子树的根先入栈，右子树的根后入栈。

栈的进出图如下：

图三：非递归调用的栈进出图

遍历结果为：（4,1,2,3,5,6,7）

递归算法和非递归算法的比较：

此处把正在运行的函数看成是一个栈，调用其他函数看成是进栈，调用函数运行完认为是出栈，模拟一下递归调用的栈：

共同点：两者对节点的遍历次序一致

区别：在非递归调用中，对右子树的访问在左子树后面，所以先将右子树节点压栈，再压左子树节点,这样在出栈进行遍历的时候起到先遍历左子树，再遍历右子树的效果。
在递归调用中，对左右子树调用的先后区别在于是先调用左子树的遍历函数，再调用右子树的遍历函数，起到的效果是一致的。