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