大门|大门-CS-2014-（第1组）|问题21-yiteyi-C++库

考虑使用指针表示的根二叉树。确定恰好有4个节点的子树数所需时间的最佳上界O（n） ^A. 洛根 ^B ).那么a+10b的值是________ （A） 1. （B） 11 （C） 12 （D） 21 答复: （A） 说明： 我们可以在O（n）时间内找到具有4个节点的子树。下面是一个简单的方法。 1）以自底向上的方式遍历树，并找到以当前节点为根的子树的大小 2）如果大小变为4，则打印当前节点。

null

下面是C语言的实现

                     #include<stdio.h>                   
                     #include<stdlib.h>                   
                             
                     struct                               Node                   
                     {                   
                                         int                               data;                   
                                         struct                               Node *left, *right;                   
                     };                   
                             
                     // A utility function to create a new Binary Tree Node                   
                     struct                               Node *newNode(                               int                               item)                   
                     {                   
                                         struct                               Node *temp =  (                               struct                               Node *)                               malloc                               (                               sizeof                               (                               struct                               Node));                   
                                         temp->data = item;                   
                                         temp->left = temp->right = NULL;                   
                                         return                               temp;                   
                     }                   
                             
                     int                               print4Subtree(                               struct                               Node *root)                   
                     {                   
                                         if                               (root == NULL)                   
                                         return                               0;                   
                                         int                               l =  print4Subtree(root->left);                   
                                         int                               r =   print4Subtree(root->right);                   
                                         if                               ((l + r + 1) == 4)                   
                                         printf                               (                               "%d "                               , root->data);                   
                                         return                               (l + r + 1);                   
                     }                   
                             
                     // Driver Program to test above functions                   
                     int                               main()                   
                     {                   
                                         struct                               Node *root = newNode(1);                   
                                         root->left = newNode(2);                   
                                         root->right = newNode(3);                   
                                         root->left->left = newNode(4);                   
                                         root->left->right = newNode(5);                   
                                         root->right->left = newNode(6);                   
                                         root->right->right = newNode(7);                   
                                         root->right->left->right = newNode(8);                   
                             
                                         print4Subtree(root);                   
                             
                                         return                               0;                   
                     }                   

这个问题的小测验

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章