0

I'm trying to implement a Binary tree (is not important if it's general binary tree, or binary search tree) and I'm having some troubles with the function that creates a node and link it into the tree.
This is the code I've written so far:

class BinaryTree {
    class Node {
        char data;

        Node* leftChild;
        Node* rightChild;

        Node(char d, Node* lc, Node* rc):
            data(d), leftChild(lc), rightChild(rc) {}
    } *head;
    int treeSize;
public:
    BinaryTree(): head(0), treeSize(0) {}

    // totally wrong code
    void createNode(char dat) {
        if (head->data < dat)
            head->leftChild = new Node(dat, 0, 0);
        if (head->rightChild == 0)
            head->rightChild = new Node(dat, 0, 0);
        if (head == 0) {
            head = new Node(dat, head, head);
        }
    }
};

Well, I thought to implement the binary tree using a linked list, but in this case the problem will be that the head pointer will point to one of the last added node, not to the root. Another issue using linked list in this way could be to find an empty child of a node where to add a new node.
There's someone that could help me and maybe suggest a better way to implement the Binary tree?

Note: I planned to make this class a template, char is just for try it on the fly.

Improve this question
1
  • If you have any C++11 support in your compiler, use std::unique_ptr<Node> to hold your Nodes and in function parameters that represent ownership transfer, and liberally use std::move when you want to transfer ownership, and reset when you assign it a new Node. Commented May 31, 2013 at 18:20

3 Answers 3

Reset to default
3

I think you moved the right way but didn't finish it. Your method may look like this:

void addNode( char data ) {
    // when root is uninitialized
    if ( NULL == head ) {
        head = new Node( data, NULL, NULL );
    } else {
        Node *currentNode = head;
        // search for the place to insert the new value
        while ( true ) {
            if ( currentNode->data < data ) {
                // if the current node already has left child
                // so we concern it further
                if ( NULL != currentNode->leftChild ) {
                    currentNode = currentNode->leftChild;
                    continue;
                // if the current node has no left child
                // so we create it with the new value
                } else {
                    currentNode->leftChild = new Node( data, NULL, NULL );
                    return;
                }
            } else {
                // similarly for the value that should be inserted into
                // right subtree
                if ( NULL != currentNode->rightChild ) {
                    currentNode = currentNode->rightChild;
                    continue;
                } else {
                    currentNode->rightChild = new Node( data, NULL, NULL );
                    return;
                }
            }
        }
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

This implement a binary search tree right? I see that you made the check on data to decide where to put the node. Moreover, if it's not tedious for you, could you add some comments(for example in the more nested if)?
Yeah this definitely needs comments. @Overflowh: Trees need a way to find the data you're looking for, and you don't have the members to find by index, but you do have the members to find by binary search, so yeah, this answer is a binary search. I suppose we could insert in random positions, but good luck finding the data again. Unless you have some other way of finding nodes?
@MooingDuck: I thought that I could need a function for finding nodes in the tree, and I want to implement the breadth-first search algorithm (as fa as I will make the insertion algorithm clear).
@Overflowh: if you're going to do a breadth-first search... I don't think you have any idea why you're making a binary tree in the first place. There's almost no reason to have a binary tree which isn't indexed nor sorted.
@Overflowh: Just added comments
|
1

Here are just a few things I noticed:

  1. Your check for head!=null should go first, otherwise your first createNode() will crash.All other branches should be in the "else".

  2. Your last (or should i say first) new Node(dat,head, head) should be new Node(dat,0,0) for the sake of code clarity and/or as a part of International Maintenance Programmer Appreciation Campaign.

  3. You probably want to increment treeSize.

Otherwise, you are on the right track. Keep going.

Improve this answer

2 Comments

#2 is wrong. It's strange, but since it only reaches that fork if head == 0, then new Node(dat, head, head is new Node(dat, 0, 0).
@MooingDuck: Well, sorry. I have wrote and deleted it a number of time. Copied/pasted all aroud the function body, and for this reason it is so messed up.
1

I'm assuming this is a homework assignment of some sort, so I think it's important to emphasize the fundamentals and let you figure out the rest. Since it's the starting point for any traversal of a tree, Head should never change unless you're deleting the root Node. Any traversal should be done by another Node object that can (and likely frequently will) go out of scope at the end of each function call without any side effects in the program.

As has been already pointed out, you need to consider the case when head = NULL as a first condition and then handle the subsequent traversal of head != NULL. With an insertion, you have to consider how you want the insertion to occur, with the proper linking to the other elements of the tree. It might be helpful to remember that a leaf is any Node object where the right and left data members are NULL.

Good luck with your program.

Improve this answer

1 Comment

So, I should modify the in this way: struct Node { /* stuff */ } *root, *traversal;? I seems strange for me that an object called head (or root) changed during the "population" of the tree.. So, my createNode function should change the *head only when it is == 0 and, instead, change the *traversal in other cases?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.