【DataStructure】Description and Introduction of Tree

【Description】

At ree is a nonlinear data structure that models a hierarchical organization. The characteristic eatures are that each element may have several successors (called its “children”) and every element except one (called the “root”) has a unique predecessor (called its “parent”). Trees are common in computer science: Computer file systems are trees, the inheritance structure for Java classes is a tree, the run-time system of method invocations during the execution of a Java program is a tree, the classification of Java types is a tree, and the actual syntactical definition of the Java programming language itself forms a tree.

【Theorem】

Ø 

Ø 

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc3hiMDg0MTkwMTExNg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">

【TreesType】

Ø decision tree

A decision tree is a tree diagram that summarizes all the differents possible stages of a process that solve a problem by means of sequence of decisions. Rach internal node is a labeled with a question, each arc is laeled with an answer to its question, and each leaf node is labeled with the solution to the problem.

Five coins that appear identical are to be tested to determine which one of them is counterfeit. The only feature that distinguishes that the counterfeit coins is that it weights less than that the legitimate coins.

Ø transition diagram

A transition diagram is a tree or graphj whose internal nodes represent different states or situations that may occur during a multistage process. As in a decision tree, each leaf represents a diffenert outcome from the process. Each branch is labeled with the conditional probability that the resulting child event will occur., given that the parent event has occurred.

Ø Orredered trees

Here is the recursive definition of an ordered tree:

Anordered treeis either the empty set or a pair T= (r, S), where ris a node 

andSis a sequence of disjoint ordered trees, none of which contains r.

The node ris called the rootof the tree T, and the elements of the sequence Sare its subtrees.

【Traversal Algorithms】

A traversal algorithm is a method for processing a data structure that applies a given operation to each element of the structure. For example, if the operation is to print the contents of the element, then the traversal would print every element in the structure. THe process of applying the operation to the each element is called visiting the element. So executing the traversal algorithm causes each element in the structure to be visited.There are three common algorithms for traversing a general tree.

Ø Level order traversal

Thelevel order traversalalgorithm visits the root, then visits each element on the first level,

then visits each element on the second level, and so forth, each time visiting all the elements on one level before going down to the next level. If the tree is drawn in the usual manner with its root at the top and leaves near the bottom, then the level order pattern is the same left-to-right top-to-bottom pattern that you follow to read English text.

The level order traversal of the tree shown in above figure would visit the nodes in the following order: a, b,c,d, e, f, g, h,i,j, k, l, m.

Ø The preorder traversal

The preorder traversal algorithm visits the root first and then does a preorder traversal recursively to each subtree in order.

The preorder traversalof the tree shown in above figure would visit the nodes in this order: a,b,e, h,i,f, c, d, g, j, k,l, m.

Ø The postorder traversal

The postorder traversal algorithm does a postorder traversal recursively to each subtree before visiting the root.

The postorder traversal of the tree shown in figure would visit the nodes in the following order: h,i,e,f,b,c,j,k,l,m,g,d,a