打印二叉搜索树中奇数层的偶数个数

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

你可以这样做：

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);
    }
}

Answer 2

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

打印二叉搜索树中奇数层的偶数个数

Print the count of even values at odd levels from a Binary Search Tree

c

binary-search-tree