1,105,344 Community Members

Algorith for complete binary tree

Member Avatar
ilovejava
Junior Poster in Training
76 posts since Sep 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 2 [?]
Skill Endorsements: 0 [?]
 
0
 

This is my code for adding and removing from a binary tree but apparently its not complete can anyone tell me what to do to make it complete tree?

public void add(IBinaryTreeNode<E> e) {
		
		if (getRoot() == null) {
			setRoot(e);
		} else {
			//SAME HERE
			IBinaryTreeNode<E> node = getLastNode();
			node.setRightChild(e);
			e.setParent(node);
		}
		setLastNode(e);
		setSize(getSize() + 1);
	}
	@Override
	public IBinaryTreeNode<E> remove() {
		
		IBinaryTreeNode<E> node = getLastNode();
		if (!node.equals(getRoot())) {
			//IM SURE SOMETHING WRONG HERE
			node.getParent().setRightChild(null);
			setLastNode(node.getParent());
		} else {
			setLastNode(null);
			setRoot(null);
		}
		node.setParent(null);
		setSize(getSize() - 1);
		return node;
	}
Member Avatar
hbluthi
Light Poster
37 posts since Oct 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
-2
 

Post error code you receive when code crashes

Member Avatar
ilovejava
Junior Poster in Training
76 posts since Sep 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 2 [?]
Skill Endorsements: 0 [?]
 
0
 

I do not receive any errors but my tree is shifting to the right i want to figure out way to make it a complete binary tree

Member Avatar
ztini
Posting Whiz in Training
291 posts since Jan 2011
Reputation Points: 8 [?]
Q&As Helped to Solve: 52 [?]
Skill Endorsements: 0 [?]
 
0
 

//IM SURE SOMETHING WRONG HERE

Yes.

Consider this tree:

root
         /     \
    node1       node2
    /   \        /   \
node3  node4  node5  node6

Using your code, if I remove node1 this is what happens:

I get root and I set root's right to null (what?). Then I set the node's parent to null. However, root still has a left reference to the deleted node (that's not right either).

How are you ordering your nodes and balancing your tree? This is important as it determines whether node4 should take node1's spot, or whether node3 should take node1's spot, or whether the root should take node1's spot.

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: