ツリーの奇数レベルのみを印刷するC++プログラム

これは、ツリーの奇数レベルのみを出力するC++プログラムです。

アルゴリズム

擬似コードを使用した構造と関数：

Begin
   Declare nod as a structure.
      Declare d of integer datatype.
      Declare a pointer l against struct nod.
      Declare a pointer l against struct nod.
   Call function struct nod* newNod(int d).
   Declare struct nod* newNod(int d) function.
      Declare a pointer node against struct node.
      Initialize node = (struct nod*) malloc(sizeof(struct nod)).
      node->d = d
      node->l = NULL
      node->r = NULL
      return node.
   Call function printLevel(struct nod* root, int lvl).
   Declare function printLevel(struct nod* root, int lvl).
      if (root == NULL) then
         return
      if (lvl == 1) then
         print the values of root->d
      else if (lvl > 1)
         call printLevel(root->l, lvl - 1)
         printLevel(root->r, lvl - 1)
   Call function height(struct nod* node).
   Declare function height(struct nod* node) to compute the height of tree.
      if (node == NULL) then
         return 0
      else
         int lhght = height(node->l);
         int rhght = height(node->r);
      if (lhght > rhght) then
         return (lhght + 1)
      else
         return (rhght + 1)
   Declare function printLevelOrder(struct nod* root).
      declare h of the integer datatype.
         initialize h = height(root).
      declare i of the integer datatype.
      for (i = 1; i <= h; i+=2)
      call function printLevel(root, i).
   insert values in the tree.
   Print “Odd numbered Level Order traversal of binary tree is”.
   Call function printLevelOrder(root).
End

例

#include <iostream>
#include<stdlib.h>
using namespace std;
struct nod {
   int d;
   struct nod* l;
   struct nod* r;
};
struct nod* newNod(int d);
struct nod* newNod(int d) {
   struct nod* node = (struct nod*) malloc(sizeof(struct nod));
   node->d = d;
   node->l = NULL;
   node->r = NULL;
   return (node);
}
void printLevel(struct nod* root, int lvl);
void printLevel(struct nod* root, int lvl) {
   if (root == NULL)
      return;
   if (lvl == 1)
      printf("%d ", root->d);
   else if (lvl > 1) {
      printLevel(root->l, lvl - 1);
      printLevel(root->r, lvl - 1);
   }
}
int height(struct nod* node);
int height(struct nod* node) {
   if (node == NULL)
      return 0;
   else {
      int lhght = height(node->l);
      int rhght = height(node->r);
      if (lhght > rhght)
         return (lhght + 1);
      else
         return (rhght + 1);
   }
}
void printLevelOrder(struct nod* root) {
   int h = height(root);
   int i;
   for (i = 1; i <= h; i+=2)
      printLevel(root, i);
}
int main() {
   struct nod *root = newNod(7);
   root->l = newNod(6);
   root->r = newNod(4);
   root->l->l = newNod(3);
   root->l->r = newNod(5);
   root->r->l = newNod(2);
   root->r->r = newNod(1);
   cout<<"Odd numbered Level Order traversal of binary tree is \n";
   printLevelOrder(root);
   return 0;
}

出力

Odd numbered Level Order traversal of binary tree is
7 3 5 2 1