CHAPTER 4 8 1 Preliminaries TREES 1. Terminology Pedigree Tree binary tree Lineal Tree
CHAPTER 4 TREES §1 Preliminaries 1. Terminology Lineal Tree Pedigree Tree ( binary tree )
Definition A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of (1) a distinguished node r, called the root (2) and zero or more nonempty(sub)trees T1,., Tk, each of whose roots are connected by a directed edge from r Note Subtrees must not connect together. Therefore every node in the tree is the root of some subtree There are N-1 edges in a tree with N nodes > Normally the root is drawn at the top
【Definition】A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of (1) a distinguished node r, called the root; (2) and zero or more nonempty (sub)trees T1 , , Tk , each of whose roots are connected by a directed edge from r. Note: ➢ Subtrees must not connect together. Therefore every node in the tree is the root of some subtree. ➢ There are edges in a tree with N nodes. ➢ Normally the root is drawn at the top. N − 1
degree of a node: : =number of subtrees of the node. For exam ple, degree(A)=3, degree(F)=0 ③⑦ o degree of a tree: =nomeree degree(node ⑥⑥⑥⑦ For example, degree of this tree= 3 o' parent: : =a node that has subtrees e children ::=the roots of the subtrees of a parent s siblings =children of the same parent leaf terminal node): = a node with degree o(no children)
A B C D E F G H I J K L M degree of a node ::= number of subtrees of the node. For example, degree(A) = 3, degree(F) = 0. degree of a tree ::= For example, degree of this tree = 3. max degree(node ) nodetree leaf ( terminal node ) ::= a node with degree 0 (no children). parent ::= a node that has subtrees. children ::= the roots of the subtrees of a parent. siblings ::= children of the same parent
a' path from n, to nk:: =a(unique) sequence of nodes n1,n2,……, nk such that n; is the parent of n;+ for Isi<k o' length of path: number of edges or⑥⑥⊙⑤ the path o depth of n; :=length of the unique path from the root to n Depth(root=0 a' height of n; : := length of the longest path from n, to a leaf Height(leaf)=0, and height(D)=2 o' height (depth) of a tree : height(root)=depth (deepest leaf) o' ancestors of a node: = all the nodes along the path from the node up to the root. descendants of a node: =all the nodes in its subtrees
A B C D E F G H I J K L M ancestors of a node ::= all the nodes along the path from the node up to the root. descendants of a node ::= all the nodes in its subtrees. depth of ni ::= length of the unique path from the root to ni . Depth(root) = 0. height of ni ::= length of the longest path from ni to a leaf. Height(leaf) = 0, and height(D) = 2. height (depth) of a tree ::= height(root) = depth(deepest leaf). path from n1 to nk ::= a (unique) sequence of nodes n1 , n2 , …, nk such that ni is the parent of ni+1 for 1 i < k. length of path ::= number of edges on the path
2. Implementation 令 List Representation (A) (A(B,C,D)) o@⑦⑦(A(B(E,F,C(G,D(H,J)) (A(B(E(K,L),F),C(G),D(H(M),L,J))) K F C+G 位M D
2. Implementation ❖ List Representation A B C D E F G H I J K L M ( A ) ( A ( B, C, D ) ) ( A ( B ( E, F ), C ( G ), D ( H, I, J ) ) ) ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) A B C D E F G H I J K L M
First Child-NextSibling Representation Element First Child NextSibling B 岛由思 NNI Note: The representation is not unique since the children in a tree can be of any order
❖ FirstChild-NextSibling Representation FirstChild NextSibling Element A B C D E F G H I J K L M N A B C N D E N K N N F N N G H N I N N J N N L N N M Note: The representation is not unique since the children in a tree can be of any order
§2 Binary trees Definition A binary tree is a tree in which no node can have more than two children R R Rotate the first child-Nextsibling tree clockwise by 45 45 由思圈盟思 Element Left left Right Right
§2 Binary Trees 【Definition】A binary tree is a tree in which no node can have more than two children. N A B C N D E N K NN F NN G H N I NN J NN L NN M Rotate the FirstChild-NextSibling tree clockwise by 45. 45 Left Right Element Left Right L R L R
Propert Property 1: at the level I of binary tree, there are at most 2i-Inodes(i2 1) prove using induction Prove: when i=l, there is only root node,21-1=2 0=1 Provided to all j, i>j21, then proposition is right, that is to say there are at most 2j-Inodes at level j. From Induction hypothesis, we know that there are at most 2i-2nodes at level i-1 Since the degree of every node in binary tree is at most 2. so the maximum node value of level l is as twice as the maximum node value of level i-1 namely 2* 2i-2=2 1-1
Property Property 1: at the level I of binary tree, there are at most 2i-1nodes. (i 1) [prove using induction] Prove: when i=1,there is only root node,2i-1=2 0=1 Provided to all j, i>j1,then proposition is right, that is to say there are at most 2j-1nodes at level j. From Induction hypothesis, we know that there are at most 2i-2nodes at level i-1. Since the degree of every node in binary tree is at most 2, so the maximum node value of level I is as twice as the maximum node value of level i-1, namely 2* 2i －2= 2 i-1
Property 2: a binary tree which depth is k has at most 2 K-l nodes(k2 1) Prove: since property 1, maximum node value of a binary tree which depth is k >(the maximum rade vaue g ledi) =∑21=20+21+…+2k1=2k-1
Property 2: a binary tree which depth is k has at most 2 k-1 nodes (k 1) . Prove: since property 1,maximum node value of a binary tree which depth is k = − k i i 1 1 2 ＝2 0 + 21 + … + 2 k-1 = 2 k-1 1 ( ) k i the maximum nodevalueof leveli = ＝
Property 3: to any binary tree T, if number of leaves is no. the number of node (degree of node is 2)is n2, then n0=n2 +1. Prove: if the number of node(degree of node is 1)is nl, the total number of node is n, the total number of edge is e, then as the definition of binary tree, n=n0+n1+n2 e=2n2+nl=n-1 SO, there comes 2n2+nl=n0+nl+n2 n2=n0-1n0=n2+1
Property 3: to any binary tree T, if number of leaves is n0, the number of node (degree of node is 2) is n2, then n0= n2 +1. Prove: if the number of node (degree of node is 1) is n1, the total number of node is n, the total number of edge is e, then as the definition of binary tree, n = n0 + n1 + n2 e = 2n2 + n1 = n – 1 so，there comes 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1