Резьбовое дерево предзаказ путевой в Яве

Question

Я пытаюсь написать код для обхода предзаказа бинарного дерева с резьбой в Java. Я написал следующий код, и он подходит для нескольких примеров, но я боюсь, что пропускаю некоторые крайние сценарии.

Дополнительная информация Узел имеет две ссылки слева и справа, указывающие на левого и правого дочернего узла соответственно. Логическое поле с именем successor определяет, указывает ли правый указатель на дочерний элемент или преемник в соответствии с обходом inorder (если successor==false: правый указывает на дочерний элемент, иначе указывает на преемник обхода inorder)

Было бы очень признательно, если бы кто-то мог указать на недостатки в моей логике здесь...

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;
                }
            }
        }
    }

Любая помощь будет оценена...:)

Answer 1

Перво-наперво... Вы должны написать модульные тесты, чтобы найти функциональные ошибки

Однако у вас, похоже, здесь есть ошибка... хотя цикл не выполняется вообще

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

Вы можете заменить его на do-while

Answer 2

      public class ParcelBST extends BinarySearchTree<Parcel> implements Iterable<Parcel>  {

    public ParcelBST(Parcel value, ParcelBST leftNode, ParcelBST rightNode) {
        super(value, leftNode, rightNode);
    }

    public ParcelBST(BinarySearchTree<Parcel> parcelBST) {
        //这里写了root是value
        super(parcelBST.value,parcelBST.leftNode,parcelBST.rightNode);
    }

    public ParcelBST(Tree<Parcel> parcelTree) {
        super(parcelTree.value,parcelTree.leftNode,parcelTree.rightNode);
    }

    public ParcelBST(Parcel value) {
        super(value);
    }


    @Override
    public Iterator<Parcel> iterator() {
        return new IteratorPreOrder();
    }

    class IteratorPreOrder implements Iterator<Parcel> {
        // Hint: value, left/right sub-trees can be accessed by:
        //    ParcelBST.this.value    ParcelBST.this.leftNode   ParcelBST.this.rightNode
        // Or equivalently directly:
        //    value   leftNode    rightNode

        private Deque<BinarySearchTree<Parcel>> stack = new LinkedList<>();

        // You may add methods and variables here if you wish
        //这个方法是干什么？

        public IteratorPreOrder() {
            //初始preorder的迭代器
            // You may add code here if you wish
            //为什么要用外部类?
            //检查的有没有根节点，如果根节点

            if(ParcelBST.this.value != null){
                stack.push(ParcelBST.this);
            }
        }

        //在这个迭代器里，再去写方法

        @Override
        public boolean hasNext() {
            // TODO
            // START YOUR CODE
            //是用来判断stack里有没有东西的
            if(stack.isEmpty()){
                return false;
            }
            return true;
            // END YOUR CODE
        }

        @Override
        //这个方法是为了去迭代树
        public Parcel next() {
            // TODO
            // START YOUR CODE
            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            BinarySearchTree<Parcel> current = stack.pop();

            //right
            if (current.rightNode != null && current.rightNode.value != null) {
                stack.push((BinarySearchTree<Parcel>) current.rightNode);
            }

            //left
            if (current.leftNode != null && current.leftNode.value != null) {
                stack.push((BinarySearchTree<Parcel>) current.leftNode);
            }
            // END YOUR CODE
            //返回整个curren的value
            return current.value;
        }
    }
}