How to implement a binary tree

Question

     package tree;

     public class Tree {

     TreeNode treenode=new TreeNode();
     TreeNode root=null;

     void insert(int data){
         root=insert(root,data);

     }

     TreeNode insert(TreeNode node,int data)
     {
         if(node==null)
         {
             node=new TreeNode(data); 
             //node.data=data;

         }
         else
         {

            // while(node!=null){
            if(node.lchild==null){
                node.lchild=insert(node.lchild,data);
                //node.lchild=node;
            }
            else if(node.rchild==null){

                node.rchild=insert(node.rchild,data);
                //node.lchild=node;
            }

    //   }

         }
        return node;



     }
     void printTree(TreeNode treenode)
     {
         if(treenode==null){
             return;
         }
         else
         {
            printTree(treenode.lchild);
            System.out.print("->"+treenode.data);
            printTree(treenode.rchild);

         }
     }

    public void printTree() {
        // TODO Auto-generated method stub
        printTree(root);

    }

     void printTreePostOrder(TreeNode treenode)
     {
         System.out.println("Post Order");
         if(treenode==null){
             return;
         }
         else
         {
            printTree(treenode.lchild);
            printTree(treenode.rchild);
            System.out.print("->"+treenode.data);

         }
     }

    public void printTreePostOrder() {
        // TODO Auto-generated method stub
        printTreePostOrder(root);

    }



}

----------------2nd Class--------------------


package tree;

public class TreeNode {


    enter code here
    int data;
    TreeNode lchild;
    TreeNode rchild;



public TreeNode(int data) {
        // TODO Auto-generated constructor stub
    this.data=data;
    this.rchild=null;
    this.lchild=null;
    }



public TreeNode() {
    // TODO Auto-generated constructor stub
    this.data=0;;
    this.lchild=null;
    this.rchild=null;
}



int getData()
{
    return this.data;
}



public TreeNode getLchild() {
    return lchild;
}



public void setLchild(TreeNode lchild) {
    this.lchild = lchild;
}



public TreeNode getRchild() {
    return rchild;
}



public void setRchild(TreeNode rchild) {
    this.rchild = rchild;
}



public void setData(int data) {
    this.data = data;
}


public static void main(String args[]){
    Tree tree=new Tree();
    tree.insert(4);
    tree.insert(5);
    tree.insert(2);
    tree.insert(7);
    tree.insert(1);
    tree.insert(6);
    tree.printTree();
    tree.printTreePostOrder();

}

}

In this, i am not able to add more than 3 nodes correctly. . I am working on a simple ordered binary tree and not binary search tree. Can anyone tell how this should be done. I am trying to implement a binary tree and not a binary search tree

Have you tried to debug?

Everv0id
– Everv0id

2015-03-11 03:38:04 +00:00
Commented Mar 11, 2015 at 3:38 — Everv0id
– Everv0id, Commented Mar 11, 2015 at 3:38

Pham Trung · Accepted Answer · 2015-03-11 03:59:00Z

1

The problem is in this part of insert(TreeNode node,int data) method:

        if(node.lchild==null){
            node.lchild=insert(node.lchild,data);
            //node.lchild=node;
        }
        else if(node.rchild==null){

            node.rchild=insert(node.rchild,data);
            //node.lchild=node;
        }

You didn't handle the case when both lchild and rchild are not null. you can make a recursive call to one of those two children by calling insert(node.lchild,data) or insert(node.rchild,data) if this case happen.

        if(node.lchild==null){
            node.lchild=insert(node.lchild,data);
            //node.lchild=node;
        }
        else if(node.rchild==null){

            node.rchild=insert(node.rchild,data);
            //node.lchild=node;
        }else{
            double random = Math.random();
            if(random < 0.5)
               insert(node.lchild, data);
            else
               insert(node.rchild, data);
        }

edited Mar 11, 2015 at 3:59

answered Mar 11, 2015 at 3:38

Pham Trung

11.3k2 gold badges26 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

user2902429 Over a year ago

Ya i have tried that as well. But I am having a problem in its implementation. Can you give its algorithm?

Pham Trung Over a year ago

@user2902429 what is your problem in implementation?

Pham Trung Over a year ago

@user2902429 I have added my suggested implementation, which randomly select left or right branch to add data.

user2902429 Over a year ago

Ya I tried that. Thanks for this, But I have one more query. What changes are required to make it a ordered binary tree. As the suggestion you gave will give a unordered binary tree

Pham Trung Over a year ago

@user2902429 ordered binary tree ? you mean binary search tree? what order do you want? you should come up with your own order or just use binary search tree.

|

Irshad ck · Accepted Answer · 2017-10-16 14:53:21Z

below is my solution to implement binary tree in java with in-order traversal

class BinaryTreeNode<T>{
    private T data;
    private BinaryTreeNode left;
    private BinaryTreeNode right;

    BinaryTreeNode(T data){
        this.data = data;
    }

    BinaryTreeNode addLeft(T data){
        left = new BinaryTreeNode(data);
        return left;
    }

    BinaryTreeNode addRight(T data){
        right = new BinaryTreeNode(data);
        return right;
    }

    void inOrderTraversal(BinaryTreeNode node){
        if(node != null){
            inOrderTraversal(node.left);
            System.out.print(" " +node.data);
            inOrderTraversal(node.right);
        }
        return;
    }

}

Suppose my tree structure like below. Then the client class for the above tree structure will be like.

public class Client {
    public static void main(String[] args) {
        BinaryTreeNode root = new BinaryTreeNode(1);
        BinaryTreeNode left = root.addLeft(2);
        BinaryTreeNode right = root.addRight(3);

        left.addLeft(4);
        left = left.addRight(5);
        left.addLeft(7);
        left.addRight(8);

        right = right.addRight(6);
        right = right.addRight(9);
        right.addLeft(10);
        right.addRight(11);

        root.inOrderTraversal(root);

   }
}

OUTPUT : 4 2 7 5 8 1 3 6 10 9 11

Collectives™ on Stack Overflow

How to implement a binary tree

2 Answers 2

8 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related