TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Discrete Mathematics Introduction of Trees

Discrete Mathematics Introduction of Trees with introduction, sets theory, types of sets, set operations, algebra of sets, multisets, induction, relations, functions and algorithms etc.

<< Back to DISCRETE

General Trees

A graph which has no cycle is called an acyclic graph. A tree is an acyclic graph or graph having no cycles.

A tree or general trees is defined as a non-empty finite set of elements called vertices or nodes having the property that each node can have minimum degree 1 and maximum degree n. It can be partitioned into n+1 disjoint subsets such that the first subset contains the root of the tree and remaining n subsets includes the elements of the n subtree.

Discrete Mathematics Introduction of Trees

Directed Trees:

A directed tree is an acyclic directed graph. It has one node with indegree 1, while all other nodes have indegree 1 as shown in fig:

Discrete Mathematics Introduction of Trees

The node which has outdegree 0 is called an external node or a terminal node or a leaf. The nodes which have outdegree greater than or equal to one are called internal node.

Discrete Mathematics Introduction of Trees

Ordered Trees:

If in a tree at each level, an ordering is defined, then such a tree is called an ordered tree.

Example: The trees shown in the figures represent the same tree but have different orders.

Discrete Mathematics Introduction of Trees

Properties of Trees:

  1. There is only one path between each pair of vertices of a tree.
  2. If a graph G there is one and only one path between each pair of vertices G is a tree.
  3. A tree T with n vertices has n-1 edges.
  4. A graph is a tree if and only if it a minimal connected.

Rooted Trees:

If a directed tree has exactly one node or vertex called root whose incoming degrees is 0 and all other vertices have incoming degree one, then the tree is called rooted tree.

Note: 1. A tree with no nodes is a rooted tree (the empty tree)
          2. A single node with no children is a rooted tree.

Discrete Mathematics Introduction of Trees

Path length of a Vertex:

The path length of a vertex in a rooted tree is defined to be the number of edges in the path from the root to the vertex.

Example: Find the path lengths of the nodes b, f, l, q as shown in fig:

Discrete Mathematics Introduction of Trees

Solution: The path length of node b is one.
                The path length of node f is two.
                The path length of node l is three
                The path length of the node q is four.


Next TopicBinary Trees




Related Links:


Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf