4.2 Binary Trees

Definition: A binary tree is either empty or consists of a node called the root together with two binary trees called the left subtree and the right subtree.

• If h = height of a binary tree,


max # of leaves = 2^h

max # of nodes = 2^{h + 1} - 1

• A binary tree with height h and 2^{h + 1} - 1 nodes (or 2^h leaves) is called a full binary tree

 

 

Figure 4.4: Examples of binary trees



 
 

Figure 4.5: Level by level numbering of a binary tree


• Figure 4.4 shows several examples of binary trees.
• The nodes of a binary tree can be numbered in a natural way, level by level, left to right. For example, see Figure 4.5.
• A binary tree with n nodes is said to be complete if it contains all the first n nodes of the above numbering scheme. Figure 4.6 shows examples of complete and incomplete binary trees.
• Total number of binary trees having n nodes


= number of stack-realizable permutations of length n

= number of well-formed parentheses (with n left parentheses and n right parentheses)

= $\left(\vphantom{\frac{1}{n+1}}\right.$${\frac{1}{n+1}}$$\left.\vphantom{\frac{1}{n+1}}\right)$$\left(\vphantom{\begin{array}{c}2n \\ n \end{array} }\right.$$\begin{array}{c}2n \\ n \end{array}$$\left.\vphantom{\begin{array}{c}2n \\ n \end{array} }\right)$

Figure 4.6: Examples of complete, incomplete binary trees

Binary Tree Traversal:

1.

Preorder

Visit root, visit left subtree in preorder, visit right subtree in preorder

2.

Postorder

Visit left subtree in postorder, right subtree in postorder, then the root

3.

Inorder

Visit left subtree in inorder, then the root, then the right subtree in inorder

• Figure 4.7 shows several binary trees and the traversal sequences in preorder, inorder, and postorder.
• We can construct a binary tree uniquely from preorder and inorder or postorder and inorder but not preorder and postorder.

Figure 4.7: Binary tree traversals

Data Structures for Binary Trees:

1.

Arrays, especially suited for complete and full binary trees

2.

Pointer-based

Pointer-based Implementation:

typedef struct node-tag {

            item-type info ;

         struct node-tag * left ;

         struct node-tag * right ;

    } node-type ;

node-type * root ; /* pointer to root */

node-type * p ; /* temporary pointer */

void preorder(node-type * root)

    {

            if (root) {

            visit (root) ;

        preorder (root $\rightarrow$ left) ;

        preorder (root $\rightarrow$ right) ;

    }

}

void inorder (node-type * root)

{

            if (root) {

            inorder (root $\rightarrow$ left) ;

                visit (root) ;

            inorder (root $\rightarrow$ right) ;

       }
}

void postorder (node-type * root)

{

        if (root) {

                postorder (root $\rightarrow$ left) ;

                postorder (root $\rightarrow$ right) ;

                        visit (root) ;

        }

}