二叉树的非递归遍历 - c++编程基础

编程之美》中使用vector容器来储存n个节点信息，并用一个游标变量last记录前一层的访问结束条件，实现如下:
void PrintNodeByLevel(Node* root)
{
vector vec; // 这里我们使用STL 中的vector来代替数组，可利用到其动态扩展的属性
vec.push_back(root);
int cur = 0;
int last = 1;
while(cur < vec.size()) {
Last = vec.size(); // 新的一行访问开始，重新定位last于当前行最后一个节点的下一个位置
while(cur < last) {
cout << vec[cur]->data << " "; // 访问节点

if(vec[cur] -> lChild) // 当前访问节点的左节点不为空则压入
vec.push_back( vec[cur]->lChild );
// 当前访问节点的右节点不为空则压入，注意左右节点的访问顺序不能颠倒
if( vec[cur]->rChild )
vec.push_back( vec[cur]->rChild );
cur++;
}
cout << endl; // 当cur == last时,说明该层访问结束，输出换行符
}
}
另外，
============求树深==========
//若T为空树，则深度为0，否则其深度等于左子树或右子树的最大深度加1
int getDepth(BiTree T)
{
if (T==NULL) return 0;
else{
dep1 = getDepth(T-> lchild);
dep2 = getDepth(T-> rchild);
return dep1 > dep2 dep1+1 : dep2+1;
}
小结一下：
用栈来实现比增加指向父节点指针回溯更方便：
1.采用栈的方法，就是跟踪指针移动，用栈保存中间结果的实现方式，先序与中序难度一致，后序很困难。先序与中序只需要修改一下访问的位置即可。
2.采用增加父节点的方法，直接用栈来模拟递归，先序非常简单；而中序与后序难度一致。先序简单是因为节点可以直接访问，访问完毕后无需记录。
而中序与后序时，节点在弹栈后还不能立即访问，还需要等其他节点访问完毕后才能访问，因此节点需要设置标志位来判定，因此需要额外的O(n)空间。
附：C源程序
#include
#include
#define MAX 20
#define NULL 0
typedef char TElemType;
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree *T){
char ch;
ch=getchar();

if (ch== '# ') (*T)=NULL; /* #代表空指针*/
else {
(*T)=(BiTree) malloc(sizeof(BiTNode));/*申请结点 */
(*T)-> data=ch; /*生成根结点 */
CreateBiTree(&(*T)-> lchild) ; /*构造左子树 */
CreateBiTree(&(*T)-> rchild) ; /*构造右子树 */
}
return 1;
}
void PreOrder(BiTree T){
if (T) {
printf( "%2c ",T-> data); /*访问根结点，此处简化为输出根结点的数据值*/
PreOrder(T-> lchild); /*先序遍历左子树*/
PreOrder(T-> rchild); /*先序遍历右子树*/
}
}
void LevleOrder(BiTree T){
/*层次遍历二叉树T，从第一层开始，每层从左到右*/
/*用一维数组表示队列，front和rear分别表示队首和队尾指针*/
BiTree Queue[MAX],b;
int front,rear;
front=rear=0;

if(T) /*若树非空*/
{
Queue[rear++]=T; /*根结点入队列*/
while(front != rear){ /*当队列非空*/
b=Queue[front++]; /*队首元素出队列，并访问这个结点*/
printf( "%2c ",b-> data);
if(b-> lchild!=NULL)
Queue[rear++]=b-> lchild; /*左子树非空，则入队列*/
if(b-> rchild!=NULL)
Queue[rear++]=b-> rchild; /*右子树非空，则入队列*/
}
}
}//LevelOrder
int getDepth(BiTree T)
{
if (T==NULL) return 0;
else{
dep1 = getDepth(T-> lchild);
dep2 = getDepth(T-> rchild);
return dep1 > dep2 dep1+1 : dep2+1;
}//depth
main(){
BiTree T=NULL;
printf( "\nCreate a Binary Tree\n ");
CreateBiTree(&T); /*建立一棵二叉树T*/
printf( "\nThe preorder is:\n ");
PreOrder(T); /*先序遍历二叉树*/
printf( "\nThe level order is:\n ");
LevleOrder(T);

二叉树的非递归遍历(二)