c - 从二叉搜索树中打印奇数级别的偶数计数

Question

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

我有一个算法可以按顺序进行遍历，但我不知道如何让它计算树的级别以了解给定的偶数值是否处于奇数级别。

中序算法

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

（级别计数从零开始，根所在的位置）
示例 1：

BST

奇数级的偶数键数：2

示例 2：

英国夏令时 2

奇数级的偶数键数：6

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

标签： cbinary-search-tree

Answer 1

要打印奇数级别的偶数值的总数，您需要保留一个全局变量，该变量将存储偶数节点的计数。您需要按顺序遍历树，并且只遍历奇数节点的给定级别。我附上下面的代码片段。打印变量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);
   }
}