Data Structures Interview # 5 — Common Operations on binary Trees (Recursive Implementation)

Data Structures Interview # 5 — Common Operations on binary Trees (Recursive Implementation)

Note: There are related exercises in the interview book, but the idea is relatively unclear, and there are typesetting mistakes. The author has rewritten the relevant books and his own views for your reference.

Reprint please indicate the: blog.csdn.net/wojiushiwo9… * * * *

Basic operation of binary tree (recursive implementation)

Binary tree is the focus of the written test and interview, including the type of multiple choice questions – before, middle and after the solution of the ergodic results. Baidu’s written test last year (autumn 2011) examined the non-recursive implementation of post-ordered traversal of binary trees.

The author first of the following often test several topics on the implementation of recursive algorithm analysis as follows:

The core of recursion is to iterate over the root node and recurse the left and right child nodes in the same way until they are empty!

1. Middle root traversal

// Middle order: left -> root -> right

  template<typename elemType>
       voidbinaryTreeType<elemType>::inorder(nodeType<elemType> *p)
       {
              if( p ! =NULL )
              {
                     inorder(p->llink);
                     cout << p->info << "";
                     inorder(p->rlink); }}Copy the code

\

2. Root traversal first

// Preorder: root -> left -> right [recursive implementation]

 template<typename elemType>
       voidbinaryTreeType<elemType>::preorder(nodeType<elemType> *p)
       {    
              if( p ! =NULL )
              {
                     cout << p->info << "";
                     preorder(p->llink);
                     preorder(p->rlink); }}Copy the code

\

3. Back-root traversal

// Back order: left -> right -> root

 template<typename elemType>
       voidbinaryTreeType<elemType>::postorder(nodeType<elemType> *p)
       {
              if( p ! =NULL )
              {
                     postorder(p->llink);
                     postorder(p->rlink);
                     cout << p->info << ""; }}Copy the code

\

4.// Find the height of the tree! [Recursive implementation]

// equals the maximum height of the left and right subtrees +1

      template<typename elemType>
       intbinaryTreeType<elemType>::height(nodeType<elemType> *p)
       {
              if( p == NULL)
              {
                     return 0;
              }
              else
              {
                     return 1 + max( height(p->llink),height(p->rlink)); // Add the root node layer 1..}}/ / auxiliary Max
       template<typename elemType>
       int binaryTreeType<elemType>::max(int x, int y)
       {
              return ( x >= y ? x : y );
       }
Copy the code

5./ All/node number statistics [recursive implementation]

   template<typename elemType>
       int binaryTreeType<elemType>::nodeCount(nodeType<elemType>*p)
       {    
              if(p == NULL)
              {
                     return 0;
              }
              else
              {
                     return 1 + nodeCount(p->llink) +nodeCount(p->rlink); }}Copy the code

\

6.// Number of leaf nodes

// The left and right subtrees are empty.

     template<typename elemType>
       intbinaryTreeType<elemType>::leavesCount(nodeType<elemType> *p)
       {
              if(p == NULL)
              {
                     return 0;
              }
              else if(p->llink == NULL && p->rlink ==NULL)
              {
                     return 1; //
              }
              else
              {
                     return leavesCount(p->llink) +leavesCount(p->rlink); }}Copy the code

\

7. Determine whether two binary trees are equal

The left subtree of binary tree 1 from the root node is identical with the right subtree of binary tree 2 from the root node, or vice versa.

Here are five cases.

template<typename elemType>
       boolbinaryTreeType<elemType>::beTreesEqual(nodeType<elemType> *first,nodeType<elemType> *second)
       {
              bool isFirstTreeNull = (first == NULL);
              bool isSecondTreeNull = (second == NULL);
 
              //case1: both are different.
              if(isFirstTreeNull ! = isSecondTreeNull) {return false;
              }
              //case2: both are non-empty.
              if(isFirstTreeNull == true &&isSecondTreeNull==true)
              {
                     return true;
              }
              //case3: neither is empty, but the node values of both are not equal
              //case4: Both are not empty, but the node value is equal, need to consider the left and right branches of the case...
              if(! isFirstTreeNull && ! isSecondTreeNull) {if(first->info ! = second->info)// Whether the values of the nodes are equal
                     {
                            return false;
                     }
                     else
                     {
                            return((beTreesEqual(first->llink,second->llink) &&beTreesEqual(first->rlink,second->rlink))
                                      ||(beTreesEqual(first->llink,second->rlink) &&beTreesEqual(first->rlink,second->llink)));
                     }//
              }//end if
              return false;
       }
Copy the code

Advice:

1. Code is not the goal, but the main idea to analyze the problem;

2. You can draw a binary tree sketch structure, and then according to the program to read the code, and then clear your mind, and then write the code is king!

3. The author also has shortcomings in the above aspects, and I hope to discuss with you!