Assuming that the binary tree adopts a binary linked list storage structure, design an algorithm to find the number of leaf nodes of a certain layer k specified by it.

Hits: 0

Assuming that the binary tree adopts a binary [linked list] storage structure, design an algorithm to find the number of leaf nodes in a certain layer k (k>1) specified by it. Requirements: (1) Give the basic design idea of ​​the algorithm.
(2) Write the [storage structure] Write the [storage structure] code used by the binary tree. (3) According to the design idea, use C or C++ language to describe the algorithm, and give comments on the key points.

// Binary tree data structure.cpp : This file contains the "main" function. Program execution will begin and end here. 
//

#include <iostream>
using namespace std;
#define eletype int

typedef struct BiNode {
    eletype data;
    struct BiNode* lchild, * rchild;
}BiNode, * BiTree;

static  int number = 1 ;
static  int ans = 0 ;

void CreateBiTree(BiTree T) {
    T->data = 1;
    BiTree a = (BiTree)malloc(sizeof(BiNode));
    a->data = 2;
    T->lchild = a;

    BiTree b = (BiTree)malloc(sizeof(BiNode));
    b->data = 3;
    a->lchild = b;

    b->rchild = NULL;

    BiTree c = (BiTree)malloc(sizeof(BiNode));
    c->data = 4;
    b->lchild = c;

    c->lchild = NULL;
    c->rchild = NULL;

    BiTree d = (BiTree)malloc(sizeof(BiNode));
    d->data = 5;
    a->rchild = d;

    d->rchild = NULL;


    BiTree e = (BiTree)malloc(sizeof(BiNode));
    e->data = 6;
    d->lchild = e;

    e->lchild = NULL;
    e->rchild = NULL;

    BiTree f = (BiTree)malloc(sizeof(BiNode));
    f->data = 7;
    T->rchild = f;

    f->rchild = NULL;

    BiTree g = (BiTree)malloc(sizeof(BiNode));
    g->data = 8;
    f->lchild = g;
    g->rchild = NULL;
    g->lchild = NULL;
}

void PreOrderBioTree(BiTree T) {

    if (T) {
        if (num == 3) {
            if (T->lchild == NULL && T->rchild == NULL) {
                ans++;
            }
        }
        num++;
        PreOrderBioTree(T->lchild);
        num++;
        PreOrderBioTree(T->rchild);
    }
    num--;

}

int main()
{
    BiTree T = (BiTree)malloc(sizeof(BiNode));
    T->lchild = NULL;
    T->rchild = NULL;
    CreateBiTree(T);
    PreOrderBioTree(T);
    cout << ans;
    return 0;
}

You may also like...

Leave a Reply

Your email address will not be published.