从二进制搜索树中打印奇数值的计数

Question

我有一个二叉树搜索树，我需要打印在奇数级别上的偶数值的总数。

我有一个按顺序执行遍历的算法，但我不知道如何使它计数树的级别，从而知道给定的偶数值是否在奇数级别。

无序算法

void printInOrder(Node *root)
{
    if (root != NULL)
    {
        printInOrder(root->left);
        printf("%d ", root->key);
        printInOrder(root->right);
    }

(级别计数从根值为零开始)

示例1:

BST

奇数级别的偶数键数：2

示例2：

BST 2

奇数级别的偶数键数：6

我真的迷路了，任何帮助都欢迎。

Answer 1

若要打印处于奇数级别的偶数值的总数，需要保留一个全局变量，该变量将存储偶数节点的计数。您需要遍历树inOrder wise，并且只遍历给定级别的奇数节点。我正在附加下面的代码片段。打印变量c以获得所需的结果。

int c=0; // Maintain a global variable to keep count
int printLevelOrder()
{
   int h = height(root);
  
   for(int i=1;i<=h;i++)   // i=1 -> level 0
   {
      if( (i-1)%2 != 0)   // level start from 0 and height from 1. traverse only for odd levels 
      {
          evenNode(root, i);
      }
    }
    
}

// fn to calculate the height of BST
int height(Node root)
{
    if(root == null)
      return 1;
     else
     {
         int lheight = height(root.left);
         int rheight = height(root.right);

          if(lheight > rheight)
             return lheight;
          else
             return rheight;

      }
}

// traversing at a given level
void evenNode(Node root, int level)
{
   if(root == null)
     return ;
   if(level ==1)
   {
      if(root.data %2 == 0)  // check if bode is even then increase counter.
           c++;
   }
   else if(level > 1)
   {
      evenNode(root.left , level -1);
      evenNode(root.right, level - 1);
   }
}

Answer 2

你可以这样做：

void printInOrder(Node *root, int level)
{
    if (root != NULL)
    {
        if (level & 1) {
            // Do something at odd level only
        }
        printInOrder(root->left, level+1);
        printInOrder(root->right, level+1);
    }
}