 请教数据结构二叉树非递归遍历
这几天正在看DS二叉树，教材用的是清华殷人昆的，看到前沿数据结构辅导书上一题：
求任意一棵二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
我用后序非递归算法，这么写对不对？还有哪些错误请高手指正。
struct StackNode
{ BinTreeNode <Type> *ptr;
enum tag { L, R};
}
class SeqStack
{ int top; //栈顶指针
Type *elements; //栈元素数组
int maxSize; //栈最大容量
}
void FirstMaxPath ( BinTreeNode <Type> *T) {
SeqStack <StackNode <Type>> s(10);
StackNode <Type> Cnode;
Type LongestPath [MAXSIZE]; //保存最长路径的数组
int longest;
BinTreeNode <Type> *p = T;
do
{ while ( p!= NULL) //遍历左子树，结点加标记进栈
{ Cnode.ptr= p; Cnode.tag= L; s.push (Cnode);
p= p->leftChild;
}
Cnode= s.pop( ); //栈顶元素退栈
p= Cnode.ptr;
while ( Cnode.tag = = R) //左右子树已遍历
{ if ( p->leftChild = = NULL&&p->rightChild = = NULL&&top>longest)
{ for (int i = 0; i<= top; i++) LongestPath[i] = s.elements[i];
longest = top;
}
if ( !s.IsEmpty ( )) //栈不空，退栈
{ Cnode= s.pop( ); p= Cnode.ptr; }
else return;
}
Cnode.tag= R; s.push (Cnode); //遍历右子树，结点加标记进栈
p= p->rightChild;
} while ( p||!s.IsEmpty( ))
for (i= 0;i<=longest;i++) cout<< LongestPath[i]<<endl;
cout<<”longest =”<<longest<<endl;
}
|
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机理论与工程 → 『 计算机考研交流 』 → 请教数据结构二叉树非递归遍历
(订阅本版)
2007/6/15 9:10:00
新浪微博
