2

我正在尝试为java中二进制线程树的前序遍历编写代码。我编写了以下代码，它适用于一些示例，但我担心我忽略了一些边缘场景。

更多信息 一个节点有两个引用left和right分别指向节点的左右子节点。一个名为successor的布尔字段根据中序遍历判断右指针是指向子还是后继（如果successor==false：右指向子，否则指向中序遍历后继）

如果有人能在这里指出我的逻辑中的缺陷，将不胜感激......

public void threadedPreorder(){
        IntThreadedTreeNode prev, p=root;    //pointers to binary tree nodes

        while(p!=null){
            while(p.left!=null){    //traversal to leftmost node
                visit(p);           //while visiting it
                p=p.left;
            }
            visit(p);
            prev=p;
            p=p.right;                      //shift to right or successor
            if(p!=null && prev.successor){    //avoid visiting the same node twice
                while(p!=null && prev.successor){
                    prev=p;
                    p=p.right;
                }
            }
        }
    }

任何帮助，将不胜感激...：）

4

1 回答 1

2

首先要做的事情...您应该编写单元测试以查找功能错误

但是，您似乎在这里有一个错误... while 循环根本不执行

if(p!=null && prev.successor){ while(p!=null && !prev.successor){ prev=p; p=p.right; } }

您可能想用 do-while 替换它

于 2015-07-21T15:43:19.003 回答