Binary tree methods java

Binary tree methods java

Besides traversal, other basic operations on binary trees are the insertion and deletion of nodes. Search operations are provided by special binary trees such as the binary search tree. Without special properties, we can search a binary tree only by traversing over all nodes and comparing each with the searched element.

Insertion of a Node

Case A: Inserting a Node Below a (Half) Leaf

Es ist leicht einen neuen Knoten an ein Blatt oder ein Halbblatt anzuhängen. Hierzu müssen wir lediglich die left — oder right -Referenz des Parent-Knotens P, an den wir den neuen Knoten N anhängen wollen, auf den neuen Knoten setzen. Wenn wir auch mit parent -Referenzen arbeiten, müssen wir diese im neuen Knoten N auf den Parent-Knoten P setzen. It is easy to append a new node to a leaf or half leaf. To do this, we just need to set the left or right reference of the parent node P, to which we want to append the new node N, to the new node. If we are working with a parent reference, we need to set the new node’s parent reference to P.

Case B: Inserting a Node Between Inner Node and Its Child

• If the new node N is to be inserted as a left child below the inner node P, then P‘s current left subtree L is set as a left child below the new node N. Accordingly, the parent of L is set to N, and the parent of N is set to P.
• If the new node N is to be inserted as a right child below the inner node P, then P‘s current right subtree R is set as a right child below the new node N. Accordingly, the parent of R is set to N, and the parent of N is set to P.

The following diagram shows the second case: We insert the new node N between P and R:

This is – as mentioned – a very simple implementation. In the example above, this results in a highly unbalanced binary tree.

Specific binary trees take a different approach here to maintain a tree structure that satisfies the particular properties of the binary tree in question (sorting, balancing, etc.).

Inserting a Binary Tree Node – Java Source Code

Here you can see the code for inserting a new node with the given data below the given parent node to the specified side (left or right) using the reorganization strategy defined in the previous section (class SimpleBinaryTree starting at line 18).

public Node insertNode(int data, Node parent, Side side) < var node = new Node(data); node.parent = parent; switch (side) < case LEFT -> < if (parent.left != null) < node.left = parent.left; node.left.parent = node; >parent.left = node; > case RIGHT -> < if (parent.right != null) < node.right = parent.right; node.right.parent = node; >parent.right = node; > default -> throw new IllegalStateException(); > return node; >Code language: Java (java)

In the createSampleTree() method of the Example1 class, you can see how to create the sample binary tree from the beginning of this article.

Deletion of a Node

Also, when deleting a node, we have to distinguish different cases.

Case A: Deleting a Node Without Children (Leaf)

If the node N to be deleted is a leaf, i.e., has no children itself, then the node is simply removed. To do this, we check whether the node is the left or right child of the parent P and set P‘s left or right reference to null accordingly.

Case B: Deleting a Node With One Child (Half Leaf)

If the node N to be deleted has a child C itself, then the child moves up to the deleted position. Again, we check whether node N is the left or right child of its parent P. Then, accordingly, we set the left or right reference of P to N‘s child C (the previous grandchild) – and C‘s parent reference to N‘s parent P (the previous grandparent node).

Case C: Deleting a Node With Two Children

How to proceed if you want to delete a node with two children?

This requires a reorganization of the binary tree. Analogous to insertion, there are again different strategies for deletion – depending on the concrete type of binary tree. In a heap, for example, the last node of the tree is placed at the position of the deleted node and then the heap is repaired.

We use the following easy-to-implement variant for our tutorial:

1. We replace the deleted node N with its left subtree L.
2. We append the right subtree R to the rightmost node of the left subtree.

We can see clearly how this strategy leads to a severely unbalanced binary tree. Specific implementations like the binary search tree and the binary heap, therefore, have more complex strategies.

Deleting a Tree Node – Java Source Code

The following method (class SimpleBinaryTree starting at line 71) removes the passed node from the tree. Corresponding comments mark cases A, B, and C.

public void deleteNode(Node node) < if (node.parent == null && node != root) < throw new IllegalStateException("Node has no parent and is not root"); > // Case A: Node has no children --> set node to null in parent if (node.left == null && node.right == null) < setParentsChild(node, null); > // Case B: Node has one child --> replace node by node's child in parent // Case B1: Node has only left child else if (node.right == null) < setParentsChild(node, node.left); >// Case B2: Node has only right child else if (node.left == null) < setParentsChild(node, node.right); >// Case C: Node has two children else < removeNodeWithTwoChildren(node); >// Remove all references from the deleted node node.parent = null; node.left = null; node.right = null; >Code language: Java (java)

The setParentsChild() method checks whether the node to be deleted is the left or right child of its parent node and replaces the corresponding reference in the parent node with the child node. child is null if the node to be deleted has no children, and accordingly, the child reference in the parent node is set to null .

In case the deleted node is the root node, we simply replace the root reference.

private void setParentsChild(Node node, Node child) < // Node is root? Has no parent, set root reference instead if (node == root) < root = child; if (child != null) < child.parent = null; > return; > // Am I the left or right child of my parent? if (node.parent.left == node) < node.parent.left = child; >else if (node.parent.right == node) < node.parent.right = child; >else < throw new IllegalStateException( "Node " + node.data + " is neither a left nor a right child of its parent " + node.parent.data); > if (child != null) < child.parent = node.parent; >>Code language: Java (java)

In case C (deleting a node with two children), the tree is reorganized as described in the previous section. This is done in the separate method removeNodeWithTwoChildren() :

private void removeNodeWithTwoChildren(Node node) < Node leftTree = node.left; Node rightTree = node.right; setParentsChild(node, leftTree); // find right-most child of left tree Node rightMostChildOfLeftTree = leftTree; while (rightMostChildOfLeftTree.right != null) < rightMostChildOfLeftTree = rightMostChildOfLeftTree.right; >// append right tree to right child rightMostChildOfLeftTree.right = rightTree; rightTree.parent = rightMostChildOfLeftTree; >Code language: Java (java)

In the deleteSomeNodes() method of the Example1 class, you can see how some nodes of the example tree are deleted again.

Array Representation of a Binary Tree

Finally, I want to show you an alternative representation of the binary tree: storing it in an array.

The array contains as many elements as a perfect binary tree of the height of the binary tree to be stored, i.e., 2 h+1 -1 elements for height h (in the following image: 7 elements for height 2).

The nodes of the tree are sequentially numbered from the root down, level by level, from left to right, and mapped to the array, as shown in the following illustration:

For a complete binary tree, we can trim the array accordingly – or store the number of nodes as an additional value.

Advantages and Disadvantages of the Array Representation

Storing a binary tree as an array has the following advantages:

• Storage is more compact, as references to children (and parents, if applicable) are not required.
• Nevertheless, you quickly get from parents to children and vice versa:
  For a node at index i,
  • the left child is at index 2i+1,
  • the right child is at index 2i+2,
  • the parent node is at index i/2, rounded down.

  Against these, one must weigh the following disadvantages:

  • If the binary tree is not complete, memory is wasted by unused array fields.
  • If the tree grows beyond the array size, the data must be copied to a new, larger array.
  • As the tree shrinks, the data should be copied (with some margin) to a new, smaller array to free up unused space.

  Summary

  In this article, you learned what a binary tree is, what types of binary trees exist, what operations you can apply to binary trees, and how to implement a binary tree in Java.

  If you liked the article, feel free to share it using one of the share buttons below. Do you want to be informed when the next article is published? Then click here to sign up for the HappyCoders newsletter.

  Источник