0 Replies - 409 Views - Last Post: 01 July 2013 - 03:11 PM Rate Topic: -----

#1 boxchamp  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 78
  • Joined: 22-November 10

Insertion into a binary tree not a BST

Posted 01 July 2013 - 03:11 PM

I am trying to insert into a Binary Tree. I originally did it as a BST and my professor pointed out that it was wrong. So when inserting I am trying to insert based off the number of children a node has.


if(numChildren() == 0) { its a leaf and can either insert left or right. I want to go left to right to make a full tree. }
else if ( numChildren ==1 && node.left == null){ then I can insert into the left child.
else if(numChildren() == 1 && node.right == null){insert into right node.}
else{ current = current.left;}

Does this make sense or is this a complete ass backwards way to do this? I keep getting a stack overflow error.

Node Class
public class Node<T> {
	T data;
	Node<T> left;
	Node<T> right;
	Node<T> parent;
	int balanceFactor;
	int key;

	public Node(T data){
		this.data = data;
		 balanceFactor = 0;;
		parent = null;
		left = null;
		right = null;
		 key = 0;
	}
	public int numChildren(){
		if(this.left == null && this.right == null){
			return 0;
		}
		else if(this.right != null || this.left != null){
			return 1;
		}
		else if(this.right != null && this.left != null){
			return 2;
		}
		//should not be reached
		return -1;
	}
}



Binary Tree class

public class BinaryTree {

	public Node<Integer> root;
	int numNode;
	int height;
	int depth;

	public BinaryTree(){
		numNode = 0;
		root = null;
		height = 0;
		depth = 0;
	}

	public int numNodes(){
		return this.numNode;
	}
	public void insert(Integer key, Node<Integer> node){
		Node<Integer> c = new Node<Integer>(key);

		if(root == null){
			root = c;
			depth++;
			//System.out.println("Num children of root: " + root.numChildren());
		}
		else{
			Node<Integer> current = root;
			Node<Integer> parent;
			while(true)
			{
				 parent = current;
				 if(parent.numChildren() == 0){
					 //it is  a leaf and can insert in either the left or right children.
						 insert(key, parent.left);
						 return;
				 }
				 else if(parent.numChildren()== 1 && parent.left == null){
					 //right has a child and left is available to be inserted.
					insert(key, parent.left);
					return;
				}
				else if(parent.numChildren() == 1 && parent.right == null){
					insert(key, current.right);
					return;
				}
				else{
					current = current.left;
				}
				 depth++;
				//setBalance(current);
			}
		}

	}
}


Is This A Good Question/Topic? 0
  • +

Page 1 of 1