Please enable JavaScript.
Coggle requires JavaScript to display documents.
binary tree, full binary tree, complete binary tree, perfect binary tree -…
binary tree
BST traverse method: inorder, preorder, postorder
full binary tree -> internal nodes always have 2 children, leaves can be in any level
complete binary tree -> all levels except the last one are completely filled, in the last level leaves are filled from left to right without gaps
perfect binary tree -> both a full tree and complete tree, max nodes for a given height
-
-
-
-
Given N node, always have N+1 null left+right pointers
full binary tree
-
node number must be odd: 1, 3, 5, 7, ...
add 2 child nodes -> internal node plus 1, and external nodes plus 1
total node number = internal + external
= 2 internal + 1
= 2 * external - 1
internal num = floor( total / 2 )
external num = ceiling(total / 2)
-
-
complete binary tree
1 based numbering
internal node num = floor(N / 2)
external node num = ceiling(N / 2)
left child index = 2 parent index
right child index = 2 parent index + 1
parent index = floor(child index / 2)
-
leaf node index starts from floor(N/2) + 1, ... , N
-
perfect binary tree
nodes number: N (N is always odd)
internal nodes number: N/2
external nodes number: N/2 + 1
N = 2 * internalNo + 1
ExternalNo = InternalNo + 1
height: h = logN
h = floor(log(external)) + 1