**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.: a parent of a node is its predecessor.__Parent__: a child of a node is its successor.__Child__: a unique node without any predecessor.__Root__: nodes without any children.__Leafs__: given a node A in a tree, the children of A and all descendents of the children of A are descendents of A.__Descendents__

**Binary Trees**

A binary tree is a tree with the following:

Each node can have

**at most two subtrees**and 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

## Comments