Двоичное дерево поиска. Почему вывод не упорядочен от меньшего к большему?

104

16 февраля 2021, 19:40

Вывод двоичного дерева поиска всегда упорядочен от наименьшего к большему. То есть если дерево растянуть в прямую линию, слева будет наименьшее значение, справа наибольшее значение. Уже сломал голову чтобы вывод у данного кода был верен. Сейчас он в корень ставит максимальное и вперед по убывающей.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
struct BinTree{
    int value;
    BinTree* left;
    BinTree* right;
};
void newBinTree(int val, BinTree** Tree) { // пам1 знач, пам2 указ на указ
    if ((*Tree) == NULL){ // пам2 нулл? ...
        (*Tree) = new BinTree;
        (*Tree)->value = val;
        (*Tree)->left = (*Tree)->right = NULL; // полям left и right присвоить null
        return;
    }
    if (val > (*Tree)-> value){ // если переданное больше предыдущего
        newBinTree(val, &(*Tree)->right); // поместить его в право, передается параметр, и второй параметр ссылка на добавляемый и в право
    } else {
        newBinTree(val, &(*Tree) -> left); // иначе в левый
    }
}
void Print(BinTree**Tree, int l){ // печать дерева , первый пам это узел, второй пам ?
    int i; // ???
    if (*Tree != NULL) { // если узер не null
        Print(&((**Tree).right), l + 1); // вызываем функцию принт, передаем ей узел справа, второй пам ?
        for (i = 1; i <= l; i++){ // ???
            cout << " ";
        }
        cout << (**Tree).value << endl; // вывод значения дерева
        Print(&((**Tree).left), l + 1);// вывод левого
    }
}
int main() {
     BinTree* Tree = NULL; // создаем указатель на структуру и присваиваем ему null (ноль) по умолчанию, в tree хранится адрес указателя
     vector<int> result;
     vector<int> numbers = {8, 3, 10, 1, 6, 14, 4, 7, 13};
     for(auto k : numbers) {
        newBinTree(k, &Tree); // после первой итерации tree будет уже объект корень
        }
     Print(&Tree, 0);
return 0;
}

Answer 1

Возможно, у вас что то не так с ньюансами C++, так как я реализовал то же самое на C# и оно работает. Вот пример

public class TreeNode
{
    public TreeNode Left;
    public TreeNode Right;
    public int V;
}
TreeNode BuildTree(TreeNode root, int v)
{
    if (root == null) return new TreeNode() {V = v};
    if(root.V < v) root.Right = BuildTree(root.Right, v);
    else root.Left = BuildTree(root.Left, v);
    return root;
}
void Print(TreeNode root, int level = 0)
{
    if (root == null) return;
    Print(root.Right, level+1);
    Console.WriteLine($"{new String('\t', level)}{root.V}");    
    Print(root.Left, level+1);
}

Запускаю вот так

void Main()
{
    TreeNode root = null;
    var data = new[] {8, 3, 10, 1, 6, 14, 4, 7, 13};
    foreach(var v in data)
        root = BuildTree(root, v);          
    Print(root);
}

Вывод

UPD

для InOrder обхода, надо сначала левый узел пройти, потом текущий, потом правый.

Само дерево выглядит так:

Код InOrder обхода

void Print(TreeNode root, int level = 0)
{
    if (root == null) return;
    Print(root.Left, level+1);
    Console.WriteLine($"{new String('\t', level)}{root.V}");    
    Print(root.Right, level+1);
}