Trees


Premium Content - Free Preview

There are many different ways to store data in a computer. Arrays store data linearly, which makes them easy to store in a computer, but often you want a different data structure to organize the data in some manner. This module will cover Trees, a data structure that has many different purposes.

This is a tree:

Tree

Terms
A Tree contains individual Nodes, such as "2" and "6", and each Node can point to other Nodes, called child nodes. The Node that points to a child Node is called a parent node. The initial Node in the tree has no parent node and is called a Root node, which is "2" in the above tree. Every other Node has just one parent node, and there are no loops in the Tree. The main tree we'll deal with is a Binary Tree, which is a tree where each Node has a maximum of 2 child Nodes.

A Tree is a Tree

Since a computer cannot just store the above Tree directly, we need a way to implement it for a computer. First, let's precisely define a Binary Tree.

A Binary Tree consists of:

  • A node, which contains data, and points to:
  • 0,1 or 2 sub-trees, which are also binary trees.

So a Tree is just a Node that points to additional Trees. This is a recursively-define data structure, which means we'll be able to use many Recursive Algorithms when dealing with Trees.

Implementing a Tree

To implement a Tree, we'll create a Node class. It will store an integer of Data, and point to 2 child Nodes.

class Node {

    int data;
    Node left;
    Node right;

}

The above code is actually enough for a basic Tree. The initial Node will form the root of the Tree, and other Nodes can be set as it's children. A Tree is just Nodes that point to other Nodes/Trees.


End of Free Content Preview. Please Sign in or Sign up to buy premium content.

Comments

  • If it is best practice to make the node value private why isn't it best practice to make the children nodes private and require methods to access them?

  • It may be "better practice" to do that for the Nodes as well, but its simpler to do these algorithms without creating getters and setters for the Node's children.

  • I try to use this code https://www.learneroo.com/user_answers/7605767388

    but I get back "Main.java:11: error: non-static variable this cannot be referenced from a static context Node node = new Node(ar[i]);"

    I am going crazy. Where is the problem?

  • @Salvatore, looking briefly at your code, you should move your Node class out of the Main class (though you'll still have some more work to do).

    public class Main{
      //all of class Main
    }
    
    class Node{
      //all of class Node
    }
    
  • Ops, thanks! Meanwhile I figured it out by myself.

    And I am still fighting to find the solution. Keep (all of) you posted!

Contact Us