1、Trees Lecture 8Discrete Mathematical StructuresRooted Tree Let A be a set, and let T be a relation on A. T is a rooted tree if there is a vertex v0 in A with the property that there exists a unique path in T from v0 to every other vertex in A, but no path from v0 to v0.v0Properties of Rooted Tree Le
2、t (T, v0) be a rooted tree. Then (a) There are no cycles in T. (b) v0 is the only root of T. (c) Each vertex other than the root has in-degree one, and the root has in-degree 0v0vpcMore than one path from v0 to v.(a)v0v0A cycle from v0 to v0(b)v0vkw1 ?More path to w1?(c)Drawing a Rooted Tree by Leve
3、lsRootInner nodeBranching nodeLeafLevel 0Level 1Level 2Level 3Height=3Rooted Tree and Family Relations It is easy to describe the family relations， and on the other hand, terms about family relations are used in rooted trees.JohnJohns childJohns parentJohns ancestorsJohns descendantsJohns siblingsSo
4、me Terms about Rooted Tree Ordered tree: the ordering is assumed on vertices in each level; n-tree: every vertex has at most n offspring; Complete n-tree: every vertes, other than leaves, has exactly n offspring Binary tree: 2-treeSubtree of a Rooted Tree If (T,v0) is a rooted tree and vT. Let T(v)
5、be the set of v and all its descendants, then T(v) and all edges with their two ends in T(v) is a tree, with v as its root.(It is called a subtree of (T,v0) ) Proof: There is a path from v to any other vertex in T(v) since they are all the descendants of v; There cannot be more than one path from v
6、to any other vertex w in T(v) , otherwise, in (T,v0), there are more than one path from v0 to w, both through v There cannot be any cycle in T(v), since any cycle in T(v) is also in (T,v0)Subtrees of Binary Tree In a ordered binary tree, a subtree is a left subtree or a right subtree.Even if a verte
7、x has only one offspring, its subtree canbe identified as left or right by its location in the digraph.Left subtreeRight subtreeLabeled Tree: an Example Using rooted tree to represent a arithmetic expressions: branching vertices corresponding operators leaves corresponding operandsjiagb cde f h/+ +* * *+ -n Example: (a*(b+c)+d*(e*f)/(g+(h-i)*j)Positional Trees222233333111LL LLLLLLRRRRR R RRPositional Binary Tree
