以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  我写的后序周游非递归算法  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=37242)

--  作者：mxf3306
--  发布时间：8/26/2006 10:30:00 PM

--  我写的后序周游非递归算法
public void postOrderTraverse() {
        Stack<StackElement> stack = new Stack<StackElement>();
        BinaryTreeNode node = root;
        StackElement element = null;
        while (stack.size() > 0 || node != null) {
            if (node != null) {
                //从父节点进入
                if (element == null || element.getNode() != node) {
                    element = new StackElement();
                    element.setNode(node);
                    element.setFrom(Direction.left);
                    stack.push(element);
                    node = node.getLeft();
                }
                //从左子树返回
                else if (element.getFrom() == Direction.left) {
                    element.setFrom(Direction.right);
                    stack.push(element);
                    node = node.getRight();
                }
                //从右子树返回
                else if (element.getFrom() == Direction.right) {
                    BinaryTreeNode.visit(element.getNode());
                    node = null;
                }
            } else {
                element = stack.pop();
                node = element.getNode();
            }
        }
    }

我写的后序周游非递归算法，测试过几颗树均无问题，不过不敢保证完全正确，贴出来请大家批评指正。

--  作者：Supremgoooo
--  发布时间：8/27/2006 8:56:00 PM

--  
没问题，对！
--  作者：Supremgoooo
--  发布时间：8/28/2006 12:50:00 PM

--  
仔细思考了一下，发现你这个框架很不错啊！

有两处优点：
（1）这不仅是一个后序框架，还是一个前序，中序框架。
（2）这个算法框架一句废话都没有，stack里面一个冗余点都没有。就是说：这个算法框架已经精简到再精简就错误的地步了

--  作者：pkurao
--  发布时间：8/28/2006 6:26:00 PM

--  
其实很多书上都是把正在访问的节点（即书上认为是从右边拉回来的节点）的右节点跟最近访问的那个节点比较，如果是则是从右链回来的，所以不需要再进右边，如果不是则进入右边。因此只要多个模块级变量即可解决是否从右链回来的问题，书上的太烦琐了。
--  作者：msychailce
--  发布时间：8/31/2006 2:49:00 PM

--  
我改了一下书上的算法，让每一节点只进一次栈，不知道对不对，请大家指点。
enum Tags{left,right};
template<class T>
class StackElement
{
 public:
 　　　BinaryTreeNode<T> * point;
 　　　Tags tag;
};

void BinaryTree<T>::PostOrderWithoutRecursion(BinaryTreeNode<T> * root)
{
 using std::stack;
 StackElement<T> element;
                stack < StackElement<T> > aStack;
 BinaryTreeNode<T> * point ;
   if (root == NULL)
      return;
   else point = root;
 while (TRUE)
 { 
  while(point)  
  {
   element.point = point;
   element.tag = left;
   aStack.push(element);  //入栈 
   point = point->leftchild();
  }
  
  element = aStack.top();
  point = element.point;
  // aStack.pop();    

  while(element->tag == right)
  {
   visit(point->vaule());
   aStack.pop();      //出栈

   if(aStack.empty())
    return;    
   else
   {
    element = aStack.top();
                                  point = element.point;
                                                       //  aStack.pop();
   }
  }

  element->tag = right;  
                 //  aStack.push(point);
  point = point->rightchild();  
 }

}

--  作者：Supremgoooo
--  发布时间：8/31/2006 7:03:00 PM

--  
对。你这是利用stl的特点，本质上和二次入栈的一样
--  作者：msychailce
--  发布时间：9/1/2006 9:52:00 AM

--  
supremgoooo说的对，我的这种在本质上没什么改进，如果非stl栈是要弹出的，就相当于aStack.top()和aStack.pop()应该是绑在一起的。
嗯，受教。谢谢supremgoooo兄。
--  作者：Supremgoooo
--  发布时间：9/1/2006 6:41:00 PM

--  
昨天没仔细看，你这个程序有有问题啊：
举一个例子：
int main()
{
      int a,b;
      a=5;
      b=a;
      b=3;
      cout<<a;
      return 0;
}
结果是5，不是3。你的算法也有此问题，element相当于b，栈顶的元素相当于a，你想通过b来改变a的值，需要引用才行，如：
int main()
{
      int a,&b;
      a=5;
      b=a;
      b=3;
      cout<<a;
      return 0;
}
结果是3。这是一个C语言容易错的地方，你自己该下算法吧。
--  作者：mxf3306
--  发布时间：9/1/2006 10:01:00 PM

--  
我这个算法其实就是参照课本的前中序遍历写的，这两个遍历写得很简洁，不知为何后序却风格大变，而且逻辑不是很清楚，看了好几遍还是很晕，算法改写后跟前中序风格一样就很容易记住了。
--  作者：springy126
--  发布时间：9/15/2006 10:12:00 AM

--  
很好的算法，谢谢lz
--  作者：Supremgoooo
--  发布时间：10/9/2006 8:46:00 PM

--  
mxf3306:
您算法张老师今天给评价了：
http://www.db.pku.edu.cn:8080/mzhang/ds/bbs/dispbbs.asp?boardID=16&ID=1780&page=1
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 79.102ms