看java做的树的三种非递归算法

2008-01-22 13:28:44　来源:ITPUB论坛　作者: 点击:

　　 // 前序遍历

　　 public void preorder( int root)
　　{
　　 int p = root;
　　 int s[] = new int [MaxSize]; // 定义栈

　　 if (p !=- 1 )
　　{
　　 int top = 0 ;
　　s[top] = p;
　　 while (top >= 0 )
　　{
　　p = s[top -- ];
　　System. out .println(treedata[p]);
　　 if (rchild[p] !=- 1 )
　　{
　　top ++ ;
　　s[top] = rchild[p];
　　}
　　}
　　 if (lchild[p] !=- 1 )
　　{
　　top ++ ;
　　s[top] = lchild[p];
　　}
　　}
　　}
　　 // 中序遍历

　　 public void inorder( int root)
　　{
　　 int p = root;
　　 int s[] = new int [MaxSize];
　　 int top =- 1 ;
　　 do
　　{
　　 while (p !=- 1 )
　　{
　　s[ ++ top] = p;
　　p = rchild[p];
　　}
　　 if (top >= 0 )
　　{
　　p = s[top -- ];
　　System. out .println(treedata[p]); 　　p = rchild[p];
　　}
　　} while (top >= 0 || p !=- 1 )
　　}
　　 // 后序遍历

　　 public void posorder( int root)
　　{
　　 int p = root;
　　 int s[] = new int [MaxSize];
　　 int top =- 1 ;
　　 int mark = 0 ;
　　 do
　　{
　　 while (p !=- 1 && mark = 0 )
　　{
　　s[ ++ top] = p;
　　p = rchild[p];
　　mark = 0 ;.
　　}
　　 if (top >= 0 )
　　{
　　p = s[top];
　　}
　　 if (rchild[p] ==- 1 )
　　{
　　System. out .println(treedata[p]);
　　top -- ;
　　mark = p;
　　}
　　 else
　　 if (rchild[p] !=- 1 && rchild[p] = mark)
　　{
　　System. out .println(treedata[p]);
　　top -- ;
　　mark = p;
　　}
　　 else
　　{
　　p = rchild[p];
　　mark = 0 ;
　　} )
　　} while (top >= 0 );
　　}