# General Trees & Binary Trees In Java Data Structure

**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