8.3 Properties of binary trees Property 1. The drawing of every binary tree with n elements, n>0, has exactly n-1 edges Property 2. The number of elements at level IS at most 21-1
8.3 Properties of binary trees Property 1. The drawing of every binary tree with n elements,n>0,has exactly n-1 edges. Property 2. The number of elements at level i is at most 2i-1 (i>=1)
8.3 Properties of binary trees Property 3. a binary tree of height h, h>=0 has at least h and at most 2h-1 elements in lt proof of property 3 ∑21-202+.+2h1=1*(1-2)(1-2)=2h-1
8.3 Properties of binary trees Property 3. A binary tree of height h, h>=0, has at least h and at most 2h –1 elements in it. proof of property 3: 2 i-1=20+21+……+2h-1=1*(1-2 h )/(1-2)=2h –1 i-1 h
8.3 Properties of binary trees Property 4. The height of a binary tree that contains n. n>=o. element is at most n and at least log2(n+1) proof Since there must be at least one element at each level. the height cannot exceed n From property 3, we know n<=2h-1 so, h>=log2 (n+D), since h is an integer, we get h>log,(n+1)
8.3 Properties of binary trees Property 4.The height of a binary tree that contains n, n>=0, element is at most n and at least log2 (n+1) proof: Since there must be at least one element at each level, the height cannot exceed n. From property 3,we know n<=2h -1, so,h>=log2 (n+1), since h is an integer,we get h>=log2 (n+1)
8.3 Properties of binary trees Property 5. If number of leaves is no, and the number of the 2 degree elements is n, then no=n2+1
8.3 Properties of binary trees Property 5. If number of leaves is n0 ,and the number of the 2 degree elements is n2 , then n0=n2+1
8.3 Properties of binary trees Definition of a full binary tree: a binary tree of height h that contains exactly 2h-1 elements is called a full binary tree
8.3 Properties of binary trees • Definition of a full binary tree : A binary tree of height h that contains exactly 2h -1 elements is called a full binary tree