8.3 Properties of binary trees Definition of a complete binary tree suppose we number the elements in a full binary tree of height h using the number 1 through 2h-1. We began at level 1 and go down to level h Within levels the elements are numbered left to right. Suppose we delete the k elements numbered 2h-i 1=K<=k, the resulting binary tree is called a complete binary tree
8.3 Properties of binary trees • Definition of a complete binary tree: suppose we number the elements in a full binary tree of height h using the number 1 through 2h -1.We began at level 1 and go down to level h.Within levels the elements are numbered left to right.Suppose we delete the k elements numbered 2h -i, 1<=i<=k,the resulting binary tree is called a complete binary tree
8.3 Properties of binary trees Example of complete binary trees 2)(3) (2 4)(5)(6(4
8.3 Properties of binary trees • Example of complete binary trees 1 2 3 4 5 6 4 2 3 1 2 1
8.3 Properties of binary trees Property 6 Let i, 1=K<-n, be the number assigned to an element of a complete binary tree. The following are true 1).Ifi=l, then this element is the root of the binary tree. If i>l, then the parent of this element has been assigned the number Li/2] 2). If 2i>n, then this element has no left child Otherwise its left child has been assigned the number 2 i
8.3 Properties of binary trees Property 6. Let i, 1<=i<=n,be the number assigned to an element of a complete binary tree. The following are true. 1).If i=1, then this element is the root of the binary tree. If i>1,then the parent of this element has been assigned the number i/2 2).If 2i>n,then this element has no left child. Otherwise,its left child has been assigned the number 2i
8.3 Properties of binary trees 3)If21+I>n, then this element has no right child, Otherwise its right child has been assigned the number 2i+l
8.3 Properties of binary trees 3)If 2i+1>n, then this element has no right child, Otherwise its right child has been assigned the number 2i+1
8.4 Representation of binary tree 1. Formula-Based Representation(array representation The binary tree to be representated is regarded as a complete binary tree with some missing elements
8.4 Representation of binary tree 1.Formula-Based Representation (array representation) • The binary tree to be representated is regarded as a complete binary tree with some missing elements