Two special forms of binary tree Definition 1 Full Binary Tree A binary tree of depth k is called for full binary tree. if it has 2k-1 nodes 6 8)9 3 Full Binary Tree
Definition 1 :Full Binary Tree A binary tree of depth k is called for full binary tree, if it has 2 k -1 nodes . Two special forms of binary tree 6 2 1 4 5 7 3 8 9 10 11 12 13 14 15 Full Binary Tree
Definition 2 Complete Binary Tree If the height of a binary tree is h, then it has h levels Except the level h, number of node of the other levels all reaches the largest Level h lack several continuous nodes from right to left, then this is complete binary tree Complete binary tree→ ③o⑩ Not complete binary tree
2 1 4 5 3 6 7 2 1 4 5 6 3 Not complete binary tree Definition 2 Complete Binary Tree If the height of a binary tree is h, then it has h levels. Except the level h, number of node of the other levels all reaches the largest. Level h lack several continuous nodes from right to left, then this is complete binary tree. 6 2 1 4 5 7 3 8 9 10 11 12 Complete binary tree
Property 4: the depth of complete binary tree, which has n(n≥0) nodes, is llog2(n)」+1 Prove: If the depth of complete binary tree is h then according to property 2 and the definition of complete binary tree, there comes 2-1-1<n≤2-1or2-1sn<2h Logarithm is h-1< log2n s h, since h is integer, so there comes h=Llog2(n)]+1
Property 4: the depth of complete binary tree, which has n (n 0) nodes, is log2(n) ＋1 Prove: If the depth of complete binary tree is h, then according to property 2 and the definition of complete binary tree, there comes 2 h－1 - 1 < n 2 h－1 or 2 h－1 n < 2h Logarithm is h－1 < log2n h，since h is integer, so there comes h = log2(n) ＋1
Property 5: If there is an n nodes complete binary tree, we encode the node from top to bottom, left to right using 0,1, 2, .,n-1, then there comes such relations: If i=0, then I has no parents. If i>0, then the parents of i are (i-1)/2 If 2*i+l<n, then the left child of I is 2*i+l, if 2* i+2<n, then the right child of l is 2*1+2 f node number is even, and i:=0 then left brother is i-1 If node number is odd, and il=n-1, then right brother is i+1 Node I is in level log2(i+1) 689
Property 5: If there is an n nodes complete binary tree, we encode the node from top to bottom, left to right using 0,1,2,…,n-1, then there comes such relations: If i=0, then I has no parents. If i>0, then the parents of i are (i -1)/2 . If 2*i+1 < n, then the left child of I is 2*i+1, if 2*i+2 < n, then the right child of I is 2*i+2. If node number is even, and i!=0, then left brother is i-1. If node number is odd, and i!=n-1, then right brother is i+1. Node I is in level log2(i+1) . 0 7 1 2 3 4 5 6 8 9
Storage structure of binary tree Sequence implementation 2 3 3 80 619 10 234567890123406780d90 Complete binary tree Commom binary tree
Complete binary tree Commom binary tree Storage structure of binary tree 1 1 2 3 4 5 6 7 8 910 9 1 2 3 4 0 5 6 7 8 0 0 910 2 4 8 9 10 5 6 7 3 1 2 3 4 5 6 7 8 ▪Sequence implementation 109