Trees
Previous data structures (e.g. lists, stacks, queues) have a linear structure.
Linear structures represent one-to-one relation between data elements.
Trees have a nested or a hierarchical structure.
Hierarchical structures represent one-to-many relation between data elements.
Examples of situations were one-to-many relations exist… these can be represented as trees.
Relation between a parent and his children.
Relation between a person and books he owns.
Relation between a football team and the players on the team.
Card catalog in a library.
A tree is represented as a set of nodes connected by edges.
Trees: Comparison with Lists
A List A Tree
1. Unique first element. 1. Unique first node called root.
2. Unique last element. 2. Each node has successors, called its children.
3. Each element, other than the 3. Each node has one predecessor, called parent.
first and the last, has a unique 4. Leafs have no children.
predecessor and a unique 5. Root has no parent.
successor.
Trees: More Terminology
Simple path: a sequence of distinct nodes in the tree.
Path length: number of nodes in a path.
Siblings: two nodes that have the same parent.
Ancestors: given a node A in a tree, the parent of the node A and the ancestors of the parent of A, are ancestors of A.
Parent: a parent of a node is its predecessor.
Child: a child of a node is its successor.
Root: a unique node without any predecessor.
Leafs: nodes without any children.
Descendents: given a node A in a tree, the children of A and all descendents of the children of A are descendents of A.
Binary Trees
A binary tree is a tree with the following:
Each node can have at most two subtreesand therefore at most two children.
Each subtree is identified as being either the left subtree or the right subtree of the parent.
It may be empty
Nodes in a binary tree may be composite e.g. of variable type ‘Type’.
ADT Binary Tree
Elements: The elements are nodes, each node contains the following data type: Type and has LeftChild and RightChild references.
Structure: hierarchical structure; each node can have two children: left or right child; there is a root node and a current node.
Domain: the number of nodes in a binary tree is bounded; domain contains empty tree, trees with one element, two elements, …
Operations:
1.Method Traverse (Order ord)
requires: Binary Tree (BT) is not empty.
input: ord.
results: Each element in the tree is processed exactly once by a user supplied procedure. The order in which nodes are processed depends on the value of ord (Order = {preorder, postorder, inorder})
preorder: each node processed before any node in either of its subtrees.
inorder: each node is processed after all its nodes in its left subtree and before any node in its right subtree.
postorder: each node is processed after all its nodes in both of its subtrees.
output: none.
Tree Traversals
To traverse a tree means to process (e.g. printing it) each element in the tree.
Tree traversals
n! ways of traversing a tree of n nodes.
pre-order, in-order, post-order ß three natural traversals orders.
List traversals
n! ways of traversing a list of n nodes.
front-to-back, or back-to-front. ß two natural traversals orders.
Example:
Ref: https://en.wikipedia.org/wiki/Tree_traversal
ADT Binary Tree: Implementation
Get In touch with Realcode4you to get any help related to Java Data Structure.
Contact Us! or send your requirement details:
realcode4you@gmail.com