Tree is an non-Linear data structure. Its way of representing hierarchical nature of data.
Different Tree Type.
- Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children.
- Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible
- Perfect Binary Tree: A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.
- Balanced Binary Tree: A binary tree is balanced if height of the tree is O(Log n) where n is number of node
- AVL Tree
- Red-Black Tree
- Binary Search Tree:
- Expression Tree:
- Threaded Binary Tree: The idea of threaded binary trees is to make inorder traversal faster and do it without stack and without recursion.
- Single Threaded: Where a NULL right pointers is made to point to the inorder successor (if successor exists)
- Double Threaded: Where both left and right NULL pointers are made to point to inorder predecessor and inorder successor respectively. The predecessor threads are useful for reverse inorder traversal and postorder traversal.
The threads are also useful for fast accessing ancestors of a node.
Different Tree Type.
- Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children.
- Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible
- Perfect Binary Tree: A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.
- Balanced Binary Tree: A binary tree is balanced if height of the tree is O(Log n) where n is number of node
- AVL Tree
- Red-Black Tree
- Binary Search Tree:
- Expression Tree:
- Threaded Binary Tree: The idea of threaded binary trees is to make inorder traversal faster and do it without stack and without recursion.
- Single Threaded: Where a NULL right pointers is made to point to the inorder successor (if successor exists)
- Double Threaded: Where both left and right NULL pointers are made to point to inorder predecessor and inorder successor respectively. The predecessor threads are useful for reverse inorder traversal and postorder traversal.
The threads are also useful for fast accessing ancestors of a node.
0 comments:
Post a Comment