Trees
In the world of data structures, a tree is a hierarchical structure that is used to represent data in a tree-like form. It consists of nodes connected by edges, with a single node known as the root. Nodes in a tree can have children nodes and can also be connected to other nodes.
Trees are commonly used to represent hierarchical relationships, such as file systems, organization structures, or family trees. In computer science, trees are also fundamental to various algorithms and data structures.
There are several types of trees, including:
- Binary Tree: A tree with at most two children per node.
- Binary Search Tree: A binary tree with the property that the left child is less than the parent node, and the right child is greater.
- AVL Tree: A self-balancing binary search tree with the property that the heights of the left and right sub-trees of any node differ by at most one.
- Red-Black Tree: A self-balancing binary search tree with the property that the heights of the left and right sub-trees of any node differ by at most one, and the color of each node is either red or black.
Let's take a look at an example of creating and traversing a binary tree in Java:
TEXT/X-JAVA
1class Main {
2 public static void main(String[] args) {
3 // Let's create a binary tree
4 BinaryTree tree = new BinaryTree();
5
6 // Add nodes to the tree
7 tree.insert(5);
8 tree.insert(3);
9 tree.insert(8);
10 tree.insert(2);
11 tree.insert(4);
12 tree.insert(6);
13 tree.insert(9);
14
15 // Traverse the tree
16 System.out.println("Inorder traversal:");
17 tree.inorder();
18
19 System.out.println("Preorder traversal:");
20 tree.preorder();
21
22 System.out.println("Postorder traversal:");
23 tree.postorder();
24 }
25}
26
27// Binary Tree class
28class BinaryTree {
29 // Root of the Binary Tree
30 Node root;
31
32 // Constructor
33 BinaryTree() {
34 root = null;
35 }
36
37 // Class representing a tree node
38 static class Node {
39 int data;
40 Node left, right;
41
42 // Constructor
43 Node(int data) {
44 this.data = data;
45 left = right = null;
46 }
47 }
48
49 // Insert a node
50 void insert(int data) {
51 root = insertNode(root, data);
52 }
53
54 // Insert a node recursively
55 Node insertNode(Node root, int data) {
56 if (root == null) {
57 root = new Node(data);
58 return root;
59 }
60
61 if (data < root.data) {
62 root.left = insertNode(root.left, data);
63 } else if (data > root.data) {
64 root.right = insertNode(root.right, data);
65 }
66
67 return root;
68 }
69
70 // Inorder traversal
71 void inorder() {
72 inorderTraversal(root);
73 }
74
75 void inorderTraversal(Node root) {
76 if (root != null) {
77 inorderTraversal(root.left);
78 System.out.print(root.data + " ");
79 inorderTraversal(root.right);
80 }
81 }
82
83 // Preorder traversal
84 void preorder() {
85 preorderTraversal(root);
86 }
87
88 void preorderTraversal(Node root) {
89 if (root != null) {
90 System.out.print(root.data + " ");
91 preorderTraversal(root.left);
92 preorderTraversal(root.right);
93 }
94 }
95
96 // Postorder traversal
97 void postorder() {
98 postorderTraversal(root);
99 }
100
101 void postorderTraversal(Node root) {
102 if (root != null) {
103 postorderTraversal(root.left);
104 postorderTraversal(root.right);
105 System.out.print(root.data + " ");
106 }
107 }
108}xxxxxxxxxx109
}class Main { public static void main(String[] args) { // replace with your Java logic here // Let's create a binary tree BinaryTree tree = new BinaryTree(); // Add nodes to the tree tree.insert(5); tree.insert(3); tree.insert(8); tree.insert(2); tree.insert(4); tree.insert(6); tree.insert(9); // Traverse the tree System.out.println("Inorder traversal:"); tree.inorder(); System.out.println("Preorder traversal:"); tree.preorder(); System.out.println("Postorder traversal:"); tree.postorder(); }}// Binary Tree classclass BinaryTree {OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment