Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 248

//R is pointing to the in-order successor of T;
//P is its parent
left(R) = left(T)
left(P) = right(R)
right(R) = right(T)
return R
} //end deleteNode

T

R

P

R

Suppose we call deleteNode with a pointer to the node L (Figure 8-9 ) as argument. The function will delete L and
return a pointer to the following tree:

N

R

J

T

P

Since L was the right subtree of H , we can now set the right subtree of H to point to N , the root of this tree.

8.12 An Array as a Binary Tree Representation
A complete binary tree is one in which every nonleaf node has two nonempty subtrees and all leaves are at the same
level. Figure 8-11 shows some complete binary trees.

C

G

E

A

A

N

B A

F

C

B

Figure 8-11. Complete binary trees

The first is a complete binary tree of height 1, the second is a complete binary tree of height 2, and the third is a
complete binary tree of height 3. For a complete binary tree of height n , the number of nodes in the tree is 2 n - 1.
Consider the third tree. Let's number the nodes as shown in Figure 8-12 .