0

所以我试图将一个元素放在java中的二叉树（不是搜索树）中。我到处寻找，我所看到的只是将它插入二叉搜索树的算法（我想要一个简单的二叉树）。给定父节点的值，我需要设置左右子节点。我的计划是这样的：

public void addLeft(E elem, E parentVal) {
//Find node with parentVal
//Create node with element elem (call it newNode)
//Set the left child of the node with parentVal as newNode
}

最后两个步骤相当简单，所以我真正的问题是找到具有给定值的节点。在搜索树中，这很容易，但在普通的二叉树中，我不知道该怎么做。我知道这不会有效率；据我所知，要将元素添加到普通二叉树中的给定节点，我们必须遍历整个树才能找到该节点。关于如何做到这一点的任何建议？假设没有数字重复（所有节点都有一个唯一元素）。我已将此标记为算法/伪代码，所以我只需要一个基本的想法就可以开始（尽管代码也很受欢迎）。

4

2 回答 2

0

Found this in Google code and in github search took me to this Java implementation

Another quick raw write-up implementation is the python implementation of Binary tree. The heading for link is misleading, but check the entire write-up.

From the link here is a high level psuedo.,

class Node:
    ...
    def insert(self, data):
        """
        Insert new node with data

        @param data node data object to insert
        """
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.insert(data)
        else:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.insert(data)
于 2013-11-12T18:37:33.477 回答
0

Here is a simple way of recursively traversing the tree and stopping when parentVal is found:

// returns true if the element has been added to this subtree
public boolean addLeft(E elem, E parentVal) {
    if (this.equals(parentVal)) {
        //Create node with element elem (call it newNode)
        //Set the left child of the node with parentVal as newNode
        return true;
    } else if (leftChild != null && leftChild.addLeft(elem, parentVal)) {
        return true;
    } else {
        return rightChild != null && rightChild.addLeft(elem, parentVal);
    }
}

This is assuming that a node has access to its children through leftChild / rightChild.

于 2013-11-12T18:33:44.967 回答