This is actually a binary tree. A binary tree is a tree where each node has at most two children nodes. If a node has only one child node, that node should be made the left node. If it has both children, then there is a left node and a right node.
Tree Vocabulary
Explanation of tree traversal is done using tree vocabulary.
Root Node: Every node in a tree has a parent except the root node.
Leaf Nodes: The ending nodes are leaf nodes. A leaf node has no child.
Key: This is the value of a node. It can be a primitive data type value or a character. It can also be an operator, e.g., + ot – .
Levels: A tree is organized into levels, with the root node at the first level. The nodes can be imagined in horizontal levels. The above tree has four levels.
Parent Node: The root node is the only node that does not have a parent. Any other node has a parent node.
Sibling Nodes: The children of any particular node are sibling nodes.
Path: A path is a string of nodes and their single branches.
Ancestor Node: All the higher nodes connected to a child, including the parent and the root node, are ancestor nodes.
Descendant Node: All lower nodes, connected to a particular node, right down to connected leaves, are descendant nodes. The node in question is not part of the descendant nodes. The node in question does not have to be the root node.
Subtree: A node plus all its descendants, right down to the related leaves, form a subtree. The starting node is included, and it does not have to be the root; otherwise, it would be the whole tree.
Degree: The node of a binary tree can have one or two children. If a node has one child, its degree is said to be one. If it has two children, its degree is said to be two.
This article explains how to traverse a binary tree in a pre-order fashion, using the Java language.
Article Content
Traversal Model
Orders
The smallest typical sub-tree of a binary tree consists of a parent node and two children nodes. The children nodes are siblings made up of the left child node and the right child node. A right child node may be absent.
Preorder
The parent node is visited first with this order, then the left node, and then the right node. If the left node has its own subtree, then all the subtree nodes will be visited first before the right node is visited. If the right node has its own subtree, then all its subtree will be visited lastly. In visiting a subtree, the pre-order scheme of parent-left-right is followed for each triangle of three nodes. If a node has only one child, meaning there is no real triangle, the only child should be considered the left node while the right node is absent.
Postorder
The left node is visited first with this order, then the right node, and then the parent node. If the left node has its own subtree, then all the subtree nodes will be visited first before the right node is visited. If the right node has its own subtree, then all its subtree will be visited secondly before the parent is visited. In visiting a subtree, the post-order scheme of left-right-parent is followed for each triangle of three nodes.
Inorder
The left node is visited first with this order, then the parent node, and then the right node. If the left node has its own subtree, then all the subtree nodes will be visited first before the parent node is visited. If the right node has its own subtree, then all its subtree will be visited lastly. In visiting a subtree, the in-order scheme of left-parent-right is followed for each triangle of three nodes.
In this article, only the preorder scheme is illustrated.
Recursion or Iteration
The preorder scheme can be implemented either using recursion or iteration. In this article, the only recursion is illustrated.
The Traversal Approach Illustrated
In this article, the pre-order scheme and recursion are used. The above diagram will be used. The diagram has been re-displayed here for easy reference:
In this section, this diagram is used to show the sequence of values (letters) that are displayed (accessed), using the preorder scheme and recursion. The letters A, B, C, etc., are the values (keys) of the different nodes.
Preorder access to the tree begins from the root. So A is access first. A has two children: B (left) and C (right). Preorder is parent-left-right. So B is accessed next. If B never had children, then C would have been accessed next. Since B has children: D (left) and E (right), its left child must be accessed next. Recall that preorder is parent-left-right. After B, the parent has been accessed, its left child, D, has to be accessed next, in accordance with parent-leftCild-rightChild.
The triangle for the parent node, B, is BDE. In this triangle, the parent node, followed by the left-child node, has just been accessed. Accessing all nodes of the triangle must be completed first. So, the next node to be accessed is the right child of node B, which is E.
Now, the triangle BDE is a subtree, which is lead by node B. At this point, node B and its triangle have completely been accessed. Node B is the left child of node A. The access of node B and its subtree have just been completed. Following parent-left-right, after the left child, node B has been accessed, the right child of parent A, C, must be accessed next.
The triangle that C leads is CFG. C is the parent, F is the left child, and G is the right child. So, as soon as C has been accessed, F must be accessed according to the parent-left-right rule. F also has a child, H. So, as soon as F has been accessed, its left child, H, has to be accessed by the parent-left-right rule.
After that, F and its subtree would have been accessed completely. At that point, there would be no question of accessing F again. F is the left child of C, which has a right child, G. After the left child, F has been accessed completely, the right child, G, must then be accessed by the parent-left-right rule.
And so the access sequence is: ABDECFHG.
Java Classes
The tree is re-displayed here for easy reference:
Node
letter) of the node. It should also have two other properties named left and right. The left property will be assigned a child node if the node has a left child. The right property will be assigned the “a” child node if the node has “a” right child.
The node class needs a constructor that will create the node object and assign a value to the key. The code for the class is:
char key;
Node left, right;
public Node(char value) {
key = value;
left = right = null;
}
}
When a node is just created, it does not have any child. That is why the left and right properties are assigned null. In the main() method, if a particular node has a left child, the child will be created and assigned to the left property of the particular node. If a particular node has a right child, the child will be created and assigned to the right property of the particular node.
The Tree Class
The code for the tree class is:
Node root;
BinaryTree() {
root = null;
}
The tree class indicates the root. It has a property called root, which is for the root node. It has a constructor without any parameters. This constructor assigns null to the root. When a tree is just created, it has no node, and that is why the property root is null. The first node created will be the root node, and it will be assigned to this property, root. From there, the tree will grow in the main() method (see below).
The BinaryTree class has the methods, preorder() and main() see below.
The preorder Method
This is the core of the program, though the main() method is also important. The preorder method implements the parent-leftChild-rightChild rule. This is a recursive function, whose code is:
if (node == null)
return;
// access the parent node
System.out.print(node.key + "->");
// access the left child
preorder(node.left);
// access the right child
preorder(node.right);
}
At the end of the tree traversal, no node will traverse, so the value of any node will be null. This accounts for the first statement in the preorder function. The second statement prints the key of the current node. The third statement recalls the same preorder function with the left child node. The next and last statement recalls the preorder function with the right child node. In this way, the whole tree is traversed.
In displaying the sequence, A->B->D, after B has been accessed, “preorder(node.right)” is called for node C but reserved. After D has been accessed, “preorder(node.right)” is called for node E. The call for node C, which was reserved, is executed after that. This explanation applies to the right branch of the whole tree.
And so the output sequence should be: A->B->D->E->C->F->H->G .
The main() Method
The main method builds the tree by assigning new nodes with their keys to a parent node’s left or right property. First, an empty tree is created. At the end of the main() method, the preorder method is called once. Since it is a recursive function, it will keep calling itself until the whole tree has been traversed. The code is:
// create tree object without any node
BinaryTree tree = new BinaryTree();
// create nodes for the tree
tree.root = new Node('A');
tree.root.left = new Node('B');
tree.root.right = new Node('C');
tree.root.left.left = new Node('D');
tree.root.left.right = new Node('E');
tree.root.right.left = new Node('F');
tree.root.right.right = new Node('G');
tree.root.right.left.left = new Node('H');
// preorder tree traversal
System.out.println("Preorder Traversal ");
tree.preorder(tree.root);
System.out.println();
}
All the above codes can be assembled into one program for testing.
The output is:
A->B->D->E->C->F->H->G->
The last -> can be ignored.
Conclusion
The Binary Tree Preorder Traversal in Java, which uses recursion, has two classes. It has the node class and the BinaryTree class. The node class has a property for the key. It also has two node properties for the left child node and the right child node. The BinaryTree class has two methods: the preorder() method and the main() method. The preorder() method implements the parent-leftChild-rightChild scheme recursively. The main() method builds the tree by assigning new nodes with their keys as left and right children to parent nodes.
The problem with the recursive algorithm for preorder is that if the tree is too big, memory may become short. To solve this problem, use the iterative algorithm – see later.
from Linux Hint https://ift.tt/2VHGAGN
0 Comments