Binary Tree Representation
struct node
{
int data;
struct node *left;
struct node *right;
};
Applications of Trees
Tree Traversal - inorder, preorder and postorder
struct node {
int data;
struct node* left;
struct node* right;
}
- A linked list is a chain of nodes connect through "next" pointers.
- A tree is similar, but each node can be connected to multiple nodes.
- When we talk about the tree, mostly we mean binary tree, that is a structure that has two children, left and right.
- A node of a binary tree is represented by a structure containing a data part and two pointers to other structures of the same type.
- Example:
struct node
{
int data;
struct node *left;
struct node *right;
};
- A special pointer called ROOT points to the node that is the parent of all the other nodes.
- Also, the nodes that don't have any children have their left and right pointers point to NULL.
Applications of Trees
- Trees and their variants are an extremely useful data structure with lots of practical applications.
- Binary Search Trees(BSTs) are used to quickly check whether an element is present in a set or not.
- Heap is a kind of tree that is used for heap sort.
- A modified version of tree called Tries is used in modern routers to store routing information.
- Most popular databases use B-Trees and T-Trees, which are variants of the tree structure we learned above to store their data
- Compilers use a syntax tree to validate the syntax of every program you write.
Tree Traversal - inorder, preorder and postorder
- Traversing a tree means visiting every node in the tree.
- You might for instance want to add all the values in the tree or find the largest one.
- For all these operations, you will need to visit each node of the tree.
- Linear data structures like arrays, stacks, queues and linked list have only one way to read the data.
- But a hierarchical data structure like a tree can be traversed in different ways.
- Let's think about how we can read the elements of the tree in the image shown above.
- Starting from top, Left to right: 1 -> 12 -> 5 -> 6 -> 9
- Starting from bottom, Left to right: 5 -> 6 -> 12 -> 9 -> 1
- Although this process is somewhat easy, it doesn't respect the hierarchy of the tree, only the depth of the nodes.
- Instead, we use traversal methods that take into account the basic structure of a tree i.e.
struct node {
int data;
struct node* left;
struct node* right;
}
- The struct node pointed to by left and right might have other left and right children so we should think of them as sub-trees instead of sub-nodes.
- Example:
- According to this structure, every tree is a combination of
- A node carrying data
- Two subtrees
- Remember that our goal is to visit each node, so we need to visit all the nodes in the subtree, visit the root node and visit all the nodes in the right subtree as well.
- Depending on the order in which we do this, there can be three types of traversal.
- Inorder traversal: First, visit all the nodes in the left subtree, Then the root node, Visit all the nodes in the right subtree.
- inorder(root->left)
- display(root->data)
- inorder(root->right)
- Preorder traversal: Visit root node, Visit all the nodes in the left subtree, Visit all the nodes in the right subtree.
- display(root->data)
- preorder(root->left)
- preorder(root->right)
- Postorder traversal: visit all the nodes in the left subtree, visit all the nodes in the right subtree, visit the root node.
- postorder(root->left)
- postorder(root->right)
- display(root->data)
- We traverse the left subtree first. We also need to remember to visit the root node and the right subtree when this tree is done.
- Example:
- Answer:
Inorder traversal 5 ->12 ->6 ->1 ->9 -> Preorder traversal 1 ->12 ->5 ->6 ->9 -> Postorder traversal 5 ->6 ->12 ->9 ->1 ->
Tags:
data structure
