Đây là một chương trình C ++ để chỉ in các Mức được Đánh số Lẻ của Cây.
Thuật toán
Cấu trúc và chức năng với mã giả:
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
Ví dụ
#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;
} Đầu ra
Odd numbered Level Order traversal of binary tree is 7 3 5 2 1