Уровень печати и узлы из двоичного дерева поиска - PullRequest
Новая
       8

Уровень печати и узлы из двоичного дерева поиска

0 голосов
/ 11 апреля 2019

Мне нужно выполнить обход по порядку бинарного дерева поиска, и мне нужно распечатать все узлы и уровень, на котором они находятся, но я не могу придумать, как это сделать.

Например:

Если у меня есть это BST , результат будет: 

4 #1
5 #0
9 #1
7 #2
10 #2
18 #3

Это то, что я получил:

Это структура, которую я использую: 

struct tree {
    int number;
    tree *izq;
    tree *der;
};

typedef struct tree *bst;

И эту функцию я пытаюсь реализовать: 

void printTree(bst node) {
    if (node==NULL) {
        return;
    }
    else {
        if (node->left != NULL) {
            printTree(node->left);
        }
        printf("%d", node->number);
        if (node->right !=NULL) {
            printTree(node->right);
        }
    }
}

У кого-нибудь есть идеи? Спасибо:)

Ответы [ 2 ]

1 голос
/ 11 апреля 2019

Я реализовал это с помощью Java, но я думаю, что вы можете легко преобразовать его в C: 

private static void printWithLevels(TreeNode node) {
    printWithLevels(node, 0);
}

private static void printWithLevels(TreeNode node, int level) {
    if (node == null) return;

    System.out.println(node.value + "(" + level + ")");

    printWithLevels(node.left, level + 1);
    printWithLevels(node.right, level + 1);
}

Чтобы мое решение было полным, это моя простая / быстрая реализация TreeNode: 

private static class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
0 голосов
/ 11 апреля 2019

предупреждение 

struct tree {
    int number;
    tree *izq;
    tree *der;
};

должно быть 

struct tree {
    int number;
    struct tree *izq;
    struct tree *der;
};

потому что случай, когда узел имеет значение NULL, проверяется в начале, вы можете упростить: 

void printTree(bst node) {
    if (node != NULL) {
      printTree(node->izq);
      printf("%d", node->number);
      printTree(node->der);
    }
}

добавление уровня: 

void printTree(bst node, int lvl) {
    if (node != NULL) {
      printTree(node->izq, lvl + 1);
      printf("%d #%d\n", node->number, lvl);
      printTree(node->der, lvl + 1);
    }
}

и вы звоните на корневом уровне с уровнем 0

Создание полной программы: 

#include <stdio.h>
#include <stdlib.h>

struct tree {
    int number;
    struct tree *izq;
    struct tree *der;
};

typedef struct tree *bst;

void printTree(bst node, int lvl) {
    if (node != NULL) {
      printTree(node->izq, lvl + 1);
      printf("%d #%d\n", node->number, lvl);
      printTree(node->der, lvl + 1);
    }
}

struct tree * mk(int v, struct tree * l, struct tree * r)
{
  struct tree * t = malloc(sizeof(struct tree));

  t->number = v;
  t->izq = l;
  t->der = r;

  return t;
}

int main()
{
  struct tree * r = mk(5, mk(4, NULL, NULL), mk(9, mk(7, NULL, NULL), mk(10, NULL, mk(18, NULL, NULL))));

  printTree(r, 0);
}

Компиляция исполнения: 

pi@raspberrypi:/tmp $ gcc -pedantic -Wall -Wextra c.c
pi@raspberrypi:/tmp $ ./a.out
4 #1
5 #0
7 #2
9 #1
10 #2
18 #3
...