如何到达二叉树中的节点 25 和 50？我必须在输出中获得二叉树的预序

Question

//
// BinTree class
//
// this class implements a binary tree
//
// the tree is unbounded. fields are
//     info: the value stored in the node (generic type)
//     left:   pointer to the left subtree
//     right:  pointer to the right subtree
//     parent: pointer to the parent
//     preOrderQueue: queue of nodes for preorder traversal
//                    left, right, and parent are public to allow the client                                           //                        code to manipulate the tree as needed
//
// methods:
//     constructor to create empty tree
//     constructor to create tree with one node
//     constructor to create tree given the root value, and
//          pointers to the left and right subtrees
//     get and set methods for the info field
//     isEmpty 
//     attachLeft:  if there is no left child, attach the given tree as
//                  the new left child; otherwisethrowTreeViolationException
//     attachRight: if there is no right child, attach the given tree as the          //                      new right child; otherwise throw TreeViolationException
//     detachLeft:  detach and return the left child
//     detachRight: detach and return the right child
//     root:        return the root of the tree

public class BinTree<T> implements BinTreeInterface<T> {

    protected T info;
    public BinTree<T> left;
    public BinTree<T> right;
    public BinTree<T> parent;
    private LinkedUnbndQueue<T> preOrderQueue;

// create an empty tree
    public BinTree() {
        info = null;
        left = null;
        right = null;
        parent = null;
    }

// create a tree with one node
    public BinTree(T item) {

    info = item;
    right = null;   //idk
    left = null;   //idk
    }

// create a tree where the root contains item
// link the left and right subtrees to the root
// don't forget to set the parent pointers
    public BinTree(T item, BinTree<T> ltree, BinTree<T> rtree) {

          info = item;
          right = rtree;
          left = ltree;

          ltree = null;
          rtree = null;

    }

// return the info field
    public T getInfo() {
        return info;
    }

// set the info field
    public void setInfo(T newitem) {
        info = newitem;
    }

// attach the parm as the left child of the current node
// throw TreeViolationException if the current node already has a left child
    public void attachLeft(BinTree<T> tree) {

        if (this.left != null)
        throw new TreeViolationException("Current node already has a left              child");

        else
             this.left = tree;
}

// attach the parm as the right child of the current node
// throw TreeViolationException if the current node already has a right child
    public void attachRight(BinTree<T> tree) {

            if (this.right != null)
                throw new TreeViolationException("Current node already has a   right child");

                else
                     this.right = tree;
    }

// detach the left child and return it
     public BinTree<T> detachLeft() {

           return this.left;
    }

// detach the right child and return it
    public BinTree<T> detachRight() {

        return this.right;

    }

我认为我的 BinTree 方法是错误的。我不明白我哪里出错了。

public BinTree<T> root() {

     if (this.parent == null)
         return this;

     else
         return this.root();
        /// return parent;

         }
// Initializes preOrderQueue with tree elements in preOrder order.
    public void preOrder(BinTree<T> tree)  {
        if (tree != null) {
            preOrderQueue.enqueue(tree.getInfo());
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

// calls preorder to create queue of nodes in the tree
    public void reset()  {
      preOrderQueue = new LinkedUnbndQueue<T>();
      preOrder(this);
    }

// removes and returns the next node in the preorder queue
// returns null if the queue is empty
    public T getNext()  {
        if (preOrderQueue.isEmpty())
            return null;
        else
            return preOrderQueue.dequeue();
     }

 }

这是我的驱动程序代码。 // 当我编译 fr preorder 时，它只打印出 75 和 bcz 以下，此时当前节点为 75。为什么它不遍历 25 和 50？

public class useTree {
    public static void main(String[] args) {
        Integer num;
        BinTree<Integer> mytree = new BinTree<Integer>(25);
        BinTree<Integer> subtree = new BinTree<Integer>(50);
        mytree.attachLeft(subtree);
        subtree = new BinTree<Integer>(75);
        mytree.attachRight(subtree);

        // subtree = new BinTree<Integer>(10);
        // mytree.attachRight(subtree);
        //         25
        //       /    \
        //     50      75


        subtree = new BinTree<Integer>(10);
        subtree.attachRight(new BinTree<Integer>(100));
        subtree.attachLeft(new BinTree<Integer>(200));
        mytree = mytree.right;
        mytree.attachLeft(subtree);

        //         25
        //       /    \
        //     50      75
        //            /
        //           10
        //          /  \
        //        200  100

        mytree = mytree.root();
        System.out.println("\npreorder traversal:");
        mytree.reset();
        num = mytree.getNext();
        while (num != null) {
        System.out.println(num);
        num = mytree.getNext();
    }
}

}

Answer 1

public BinTree root() {
    if (parent == null) return null;

    BinTree tmp = parent;
    while (tmp.parent != null) {
        tmp = tmp.parent;
    }
    return tmp;
}

您应该创建一个单独的 class 命名 BinNode 之类的。 Tree 和 Node 是不同的东西，您创建的 class 令人困惑且没有意义。

还有，您没有在任何地方分配 parent 变量。

public void attachRight(BinTree<T> tree) {

    if (this.right != null)
        throw new TreeViolationException("Current node already has a   right child");

    else {
        this.right = tree;
        tree.parent = this;
    }
}

适当分配子分支的父级。此外，您的分离方法也是错误的。您只是返回 right/left 分支，但您应该先 detach/remove 它们。

BinTree branch = this.right; // or left
this.right = null;
return branch;

Answer 2

public BinTree root() {

 if (this.parent == null)
     return this;

 else
     return this.root();
    /// return parent;

     }

应该是：

 public BinTree root() {
     if (this.parent == null)
         return this;
     else
         return this.parent.root();
 }

这使用递归，虽然不是最优的，但至少是正确的。

还有：

private LinkedUnbndQueue<T> preOrderQueue;

树的每个节点都有自己的队列？那是不对的。如果你真的想生成一个队列，将队列对象传递给相关方法。而且，为什么 preOrder 方法需要树参数——它不是静态方法； "this" 作为隐式参数。

public void preOrder(LinkedUnbndQueue<T> preOrderQueue)  {
    preOrderQueue.enqueue(this.getInfo());
    if (left != null) left.preOrder(preOrderQueue);
    if (right != null) right.preOrder(preOrderQueue);
}

此外，attachLeft 和 attachRight 方法需要设置附加子树的 parent 字段。

更一般地说，您的 BinTree 既是一个节点又是一棵树。这可以工作，但有些操作在每个节点的基础上并没有真正意义（特别是你定义的自定义迭代应该被移出，因为正如我所指出的，每个节点都有一个队列没有多大意义节点）。

坦率地说，这段代码存在的问题太多了，您需要一种更好的方法来进行开发实践。考虑学习使用调试器。

如何到达二叉树中的节点 25 和 50？我必须在输出中获得二叉树的预序

How do I get to node 25 and 50 in my binary tree? I have to get a preorder of the binary tree in output

java

binary-tree

data-structures