问题描述:

So I'm trying to put an element in a binary tree (not a search tree) in java. I looked everywhere, and all I can see are algorithms for inserting it into a binary search tree (and I want a simple binary tree). Given the value of the parent node, I need to set the left and right children. My plan looks like this:

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

}

The last 2 steps are fairly simple, so my real problem is finding the node with a given value.

In a search tree, it is an easy task, but in a normal binary tree, I don't know how to do it. I understand that it won't be efficient; as far as I know, to add an element to a given node in a normal binary tree, we have to traverse the entire tree to find that node. Any suggestions on how to do this? Assume there will be no repeats of numbers (all nodes have a unique element). I've tagged this as algorithm/pseudocode, so just a basic idea is all I need to get started (although code is appreciated as well).

网友答案:

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.

网友答案:

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)
相关阅读:
Top