Data Structure & Algorithm in Java

  1. Home
  2. Docs
  3. Data Structure & Alg...
  4. Trees
  5. Introduction of Tree

Introduction of Tree

Here is the detailed explanation of Introduction of Tree:

A tree is a connected, undirected graph with no cycles.

• This means that it is possible to travel from any vertex in the tree to any other vertex by following the edges of the tree, but there is no path that starts and ends at the same vertex and follows only distinct edges.

• The tree consisting of a single vertex with no edges is called the trivial tree or the degenerate tree.

→ Properties of Trees:

  • There is only one path between each pair of vertices of a tree.
  • A tree T with n vertices has n-1 edges.
  • In any tree G, there are at least two pendant vertices
  • A forest G with n vertices has n-k edges, where k is the number of components of G.

→ Tree Terminologies:

Treedatastructure 1

Node: Each data item in a tree is called a node. It is the basic structure in a tree.

• Root: The root is the top data item (node) in a tree. It has no parent nodes.

• Degree of a node: The degree of a node is the number of child nodes that it has.

• Terminal node(s): A terminal node is a node that has no child nodes.

• Non-terminal node(s): A non-terminal node is a node that has at least one child node.

• Siblings: Two nodes are siblings if they have the same parent node.

• Level: The level of a node is the number of edges from the root node to that node.

• Edge: An edge is a connection between two nodes in a tree.

• Path: A path is a sequence of nodes and edges that connects two nodes in a tree.

• Depth: The depth of a node is the length of the longest path from the root node to that node.

• Forest: A forest is a set of two or more disjoint trees.

→ Rooted Trees:

A rooted tree is a tree in which one vertex is designated as the root.

They are often used to represent hierarchical data structures, such as file systems, family trees, and organization charts. They can also be used to represent search algorithms, such as binary search trees.

  • Binary Search Tree
  • Decision Tree
  • Game Tree
  • Prefix Codes

Binary Search Tree:

A binary search tree (BST) is a type of data structure that maintains sorted order for elements, allowing for efficient insertion, deletion, and lookup operations.

Note: The binary tree is so named because each node can have at most two child nodes.

Strictly Binary Tree:

A binary tree is called strictly binary tree if every non-leaf node in a binary tree has non-empty left and right sub-tree.

Complete(Full) Binary Tree:

A strictly binary tree in which all the leaf nodes lies on same level is called complete binary tree.

Decision Tree:

A decision tree is a tree-like graph or model that uses a branching process to help make decisions.

• Each internal node in the tree represents a decision, and each branch represents a possible outcome of that decision. The leaf nodes of the tree represent the final outcomes of the decision process.

Game Tree:

A game tree is a tree-like graph that represents all possible moves in a game.

• The nodes of the tree represent the game states, and the edges of the tree represent the moves that can be made from one state to another.

Prefix Codes:

A prefix code is a code in which no codeword is a prefix of any other codeword. This means that no codeword can be formed by simply adding more bits to another codeword.

Prefix codes are often used to encode data in a way that is efficient and minimizes the number of bits required. For example, prefix codes are used to encode text in Morse code and Huffman coding.

• One way to construct a prefix code is to use a binary tree. Each node in the tree represents a codeword, and the path from the root node to a leaf node represents the codeword for that leaf node.


How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *