Chương trình C++ in chỉ các cấp độ lẻ của cây

Đây là chương trình C++ in chỉ các cấp độ lẻ của một cây.

Thuật toán

Cấu trúc và hàm với mã giả:

Begin
    Khai báo nod là một cấu trúc.
        Khai báo d kiểu nguyên.
        Khai báo con trỏ l trỏ đến cấu trúc nod.
        Khai báo con trỏ r trỏ đến cấu trúc nod.
    Gọi hàm struct nod* newNod(int d).
    Khai báo hàm struct nod* newNod(int d).
        Khai báo con trỏ node trỏ đến struct node.
        Khởi tạo node = (struct nod*) malloc(sizeof(struct nod)).
        node->d = d
        node->l = NULL
        node->r = NULL
        return node.
    Gọi hàm printLevel(struct nod* root, int lvl).
    Khai báo hàm printLevel(struct nod* root, int lvl).
        if (root == NULL) then return
        if (lvl == 1) then in giá trị root->d
        else if (lvl > 1)
            gọi printLevel(root->l, lvl - 1)
            printLevel(root->r, lvl - 1)
    Gọi hàm height(struct nod* node).
    Khai báo hàm height(struct nod* node) tính chiều cao cây.
        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)
    Khai báo hàm printLevelOrder(struct nod* root).
        khai báo h kiểu nguyên.
        khởi tạo h = height(root).
        khai báo i kiểu nguyên.
        for (i = 1; i <= h; i+=2)
            gọi hàm printLevel(root, i).
    Chèn giá trị vào cây.
    In "Odd numbered Level Order traversal of binary tree is".
    Gọi hàm 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;
}

Kết quả

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