主页 / 问题 / 993044
Accepted
Aleksey
Asked:2020-06-15 19:51:02 +0000 UTC2020-06-15 19:51:02 +0000 UTC

二叉搜索树。为什么输出不是从小到大排序的？

  • 772

二叉搜索树的输出总是从小到大排序。也就是说，如果将树拉伸成一条直线，则最小值在左侧，最大值在右侧。我已经伤脑筋了，所以这段代码的输出是正确的。现在他把最大值放在根部，然后按降序排列。

#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;
}
c++

1 个回答

  1. Best Answer

    也许您对 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);
}

    结论

        14
      13
  10
8
      7
    6
      4
  3
    1

    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);
}

    结论

        1
  3
      4
    6
      7
8
  10
      13
    14
    • 2

相关问题