Draw Binary Tree on Comptuer

Introduction to Trees

The tree data structure (from wiki)

In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.

Definitions:

1. A tree is a collection of nodes with one root and branches that are trees.
2. A tree is a finite set of nodes such that: (1) there exists a specially designated node called root ; (2) the remaining nodes are partitioned into n ≥ 0 disjoint sets, T1, T2, ..., Tn, where each of these sets is a tree, known as subtree .

Concept / Terminology:

• Non-linear organization of elements. The components do not form a simple sequence of first element, second element, and so on.
• Names are from Botany and Genealogy: node, branch, depth (height), root, leaf, non-leaf (inner node), path, forest; parent, child, sibling, cousin, ancestor, descendant, and subtree.
• More terms are given on pages 445 - 447.

Classification:

• By maximum number of branches -- binary, ternary, n-way
• By heights of substree -- balanced, unbalanced trees
• By changeability -- static, dynamic trees

Special Trees:

• Empty (Null)-tree: a tree without any node
• Root-tree: a tree with only one node
• Binary tree: a tree in which each node has at most two children (parent, left, and right)
• Two tree: a binary tree that either is empty or each non-leaf has two children
• Heap: a tree where parent node has bigger (smaller) value than children
• And many others: binary search tree (BST), 2-3 tree, AVL tree, B-tree, Huffman tree, Red-Black tree, Game tree, Spanning tree, etc.

Why Tree Structure?

• O(log n)

Introduction to Binary Trees Definition of Binary Trees:

• A binary tree is a finite set of nodes.
• The set might be empty.
• When the set is not empty, it follows these rules:
  1. There is one special node, called the root.
  2. Each node can be associated with up to two other different nodes, called its left child and its right child. If a node c is the child of another node p,  then we say that "p is c's parent".
  3. Each node, except the root, has exactly one parent; the root has no parent.
  4. If you start at a node and move to the node's parent (if there's one), and then move again to that node's parent, and keep moving upward to each node's parent, you will eventually reach the root.

Is the following a binary tree?

Other definitions:

• Subtree: any node in a tree and its descendants.
• Depth of a node: the number of steps to hop from the current node to the root node of the tree.
• Depth of a tree: the maximum depth of any of its leaves.
• Height of a node: the length of the longest downward path to a leaf from that node.
• Full binary tree: every leaf has the same depth and every nonleaf has two children.
• Complete binary tree: every level except for the deepest level must contain as many nodes as possible; and at the deepest level, all the nodes are as far left as possible.
• Traversal: an organized way to visit every member in the structure.

Tree Representations Storage choices: (1) array representation (contiguous list) and (2) node representation.

For a complete binary tree, follow the following formulas for the array representation:

1. The data from the root always appears in the [0] component of the array.
2. Suppose the data for a non-root node appears in component [i] of the array. Then the data for its parent is always at location [(i - 1)/2].
3. Suppose the data for a node appears in component [i] of the array. Then its children (if they exist) always have their data at these locations:
   1. Left child at component [2i + 1]
   2. Right child at component [2i + 2]

Let's work on an example from the board.

These formulas make it easy to implement algorithms that traverse the tree, moving from node to node in various ways, processing data along the way. In the actual implementation, you will need:

• The array itself
• A second instance variable keeps track of how much of the array is used

The actual links between the nodes are not stored, but are determined by the formula.

Can we also implement a non-complete binary tree using an array?

Node representation of binary trees:

1. Each node of a binary tree can be stored as an object of a binary tree node class. The class contains private instance variables that are references to other nodes in the tree.
2. An entire tree is represented as a reference to the root node.

For example, a generic type implementation:

class BTNode<E>
{
private E data;
private BTNode<E> left;
private BTNode<E> right;
...
}

The reference to the root is similar to the head of a linked list, providing a starting point to access all the nodes in the tree. We could include other things in the tree node.

Binary Tree Implementation with Tree Nodes
// The constructor
public BTNode (E initialData, BTNode<E> initialLeft, BTNode<E> initialRight)
{
data = initialData;
left = initialLeft;
right = initialRight;
}

// Getting and Setting Data Links
public E getData()
public BTNode<E> getLeft()
public BTNode<E> getRight()

public void setData(E newData)
public void setLeft(BTNode<E> newLeft)
public void setRight(BTNode<E> newRight)

// Testing whether a node is a leaf
public boolean isLeaf() // implement it

// Getting data from the leftmost or rightmost node; hints: using recursion
public E getLeftmostData() // implement it
public E getRightmostData()

// Removing the leftmost or rightmost node
// Remove the leftmost node of the tree with this node as its root.
// Postcondition: leftmost node removed. The return value is a reference to the root of the new tree. Return value could be null.
public BTNode<E> removeLeftmost()
{
// the node that activates removeLeftmost has no left child, thus is itself the leftmost node of the subtree
if (left == null) {
return right;
} else {
// a recursive call removes the leftmost node from my left subtree
left = left.removeLeftmost();
return this;
}
}

// Your turn to implement removeRightmost()
public BTNode<E> removeRightmost()

// Copying a tree
public static <E> BTNode<E> treeCopy(BTNode<E> source)
{
BTNode<E> leftCopy, rightCopy;

  if (source == null)
return null;
else {
leftCopy = treeCopy(source.getLeft());
rightCopy = treeCopy(source.getRight());
return new BTNode<E>(source.getData(), leftCopy, rightCopy);
}
}

// Height of a node
public static <E> int height(BTNode<E> node)
{
if (node == null)
return -1; // it's an empty tree
else
return 1 + Math.max(height(node.getLeft()), height(node.getRight()));
}

// Calculate the number of nodes in a binary tree with the given root
public static <E> int treeSize(BTNode<E> root)
// your turn to implement

// Calculate the number of leaves in a binary with the given root
public static <E> int countLeaves(BTNode<E> root)
// your turn to implement

Note: Tree implementation or related algorithms really use a lot of "recursions". Also note that the depth of an average binary tree is considerably smaller than n, even though in the worst case, the depth can be as large as n-1.

Tree Traversals Traversal: the process of visiting all the nodes in a tree in a certain order.

• Pre-order traversal
• In-order traversal
• Post-order traversal

Pre-order traversal:

1. Process the root.
2. Process the nodes in the left subtree with a recursive call.
3. Process the nodes in the right subtree with a recursive call.

In-order traversal:

1. Process the nodes in the left subtree with a recursive call.
2. Process the root.
3. Process the nodes in the right subtree with a recursive call.

Post-order traversal:

1. Process the nodes in the left subtree with a recursive call.
2. Process the nodes in the right subtree with a recursive call.
3. Process the root.

Finish the code for in-order and post-order traversals.

Binary Search Tree (BST) Binary search tree storage rule:

In a binary search tree, the elements of the nodes can be compared with a total order semantics. The following two rules are followed for every node n:

1. Every element in n's left subtree is less than or equal to the element in node n.
2. Every element in n's right subtree is greater than the element in node n.

Example: create a binary search tree with the following values: 51, 29, 68, 90, 36, 40, 22, 59, 44, 99, 77, 60, 29, 83, 15, 75, 3.  Then insert 33, 88, 1, 36 to the BST. Now, delete 44, 90, 68, 70 from the BST.

// Add a new element to the BST
public void add(int element)
{
boolean done = false;
IntBTNode cursor = root;
IntBTNode newE = new IntBTNode(element, null, null);
if (cursor == null) {// the BST is empty
root = newE;
} else {
while (!done) {
if (element <= cursor.getData()) {
if (cursor.getLeft() == null) {
cursor.setLeft(newE);
done = true;
} else {
cursor = cursor.getLeft();
}
} else {// go to the right branch
if (cursor.getRight() == null) {
cursor.setRight(newE);
done = true;
} else {
cursor = cursor.getRight();
}
}
}
}
}

// Remove an element from the BST
public boolean remove(int target)
{
IntBTNode cursor = root, parent = null;
while (true) {
if (cursor == null) return false; // case #1, target not present
if (cursor.getData() == target) {
if (cursor.getLeft() == null) {
if (cursor == root) { // case #2, target found at root with no left child
root = root.getRight();
return true;
}
if (cursor == parent.getLeft()) { // case #3, target found with no left child
parent.setLeft(cursor.getRight()); // cursor is the left child
} else {
parent.setRight(cursor.getRight()); // cursor is the right child
}
return true;
} else { // case #4, there's a left child
cursor.setData(cursor.getLeft().getRightmostData());
cursor.setLeft(cursor.getLeft().removeRightmost());
return true;
}
} else if (target < cursor.getData()) {
parent = cursor;
cursor = cursor.getLeft();
} else { // target is greater than the cursor data
parent = cursor;
cursor = cursor.getRight();
}
}
}

Questions:

• Are there other ways of implementing the above code?
• What is the potential problem with a BST?
• What's the time complexity of finding a specific key in a BST? Worst case? Average case?
• When a node is removed, we normally replace it with the largest in its left subtree. Do we have other possible option?

Learning Objectives When you complete this chapter's study, you should be able to:

• Understand the tree data structure and its related terminologies.
• Design and implement classes for binary tree nodes and nodes for general tree.
• Traverse the tree with the three common orders.
• List the rules for a binary search tree and determine whether a tree satisfies these rules.
• Carry out searches, insertions, and removals on a binary search tree and implement these algorithms using your binary tree node classes.

robersonshissing.blogspot.com

Source: https://www.cpp.edu/~ftang/courses/CS241/notes/trees.htm

Share this post