从建立二叉树给定的数据

我无法理解如何建立从给定的一组数字的binary tree ...从建立二叉树给定的数据

30 
15 
4 
NULL 
NULL 
20 
18 
NULL 
19 
NULL 
NULL 
NULL 
35 
32 
NULL 
NULL 
38 
NULL 
NULL

我已经通过我的书不见了，笔记和不能似乎弄明白了。 NULL是什么意思？如果你能给我看一个正确的建树，它会是最有帮助的，我是一个非常有视觉的人。我已经从我的作业中更改了数值和NULL的顺序，所以不要担心我没有从中学习！

来源

2015-11-11 Bob

我想你需要通过地板上建立自己的树。在前两个分支30和15的末尾;在30以下，有4个NULL和15以下的thera是NULL和20。你下降一层：在4下，有18和NULL（NULL和NULL以下），20以下有19和NULL等。意味着分支末尾没有任何东西。 –

这不会是一棵二叉树。 – tekan

如果你只在这里考虑的数字是二叉树应该什么样子：

   +--+ 
       |30| 
      +------------------+ 
      |     | 
     +--+     ++-+ 
     |15|     |35| 
    +------------+   +----------+ 
    |   |  +--+  +--+ 
+-+   +-++  |32|  |38| 
|4|   |20|  +--+  +--+ 
+-+   +--+ 
     +-----+ 
     |18| 
     +---+ 
      | 
      +----+ 
      |19| 
      +--+

现在，如果你去通过列表再次，你会看到NULL分别表示什么时候停止。 30有一个孩子，15，15有一个孩子4，4没有一个孩子（后跟两个NULL S），打算一升上来，15有第二个孩子20，20有孩子：18。 18没有留下子女（以NULL表示），但有一个正确的子女19。它没有任何子女（两个NULL s）。 20也没有任何更多的孩子：NULL导致15的其他孩子：35等

来源

2015-11-11 23:18:29 tekan

这是正确的！ – lrleon

我会假设第一个节点显示树的根节点。

列表中的以下两个节点是即时叶子。

我会假定NULL值表明列表中的前一个节点只有一个叶节点或没有叶节点。

对于树结构中的节点排序，对于它是二叉搜索树，每对叶节点应该大于或小于父节点，并且通常较小的值应该是左手叶节点。这意味着您可以通过从根目录开始并选择较高或较低的叶节点来搜索树，遍历树，直到找到所需的节点。

来源

2015-11-11 23:19:30 EkcenierK

很可能你的问题涉及Łukasiewicz代码。

给定一个二叉树，一个Łukasiewicz码是完整的前序遍历生成的序列，其中内部节点标记为a，外部标记（NULL指针）标记为b。 “a / b”的使用是惯例的问题。你可以使用任何其他符号;比特。

例如，此树

应与您问题相关的树

，具有与卢卡西维茨代码序列如下：

aaabbaababbbaabbabb

考虑绘制与外部节点相同的树。一些诸如

在该图中，每个外部节点绘制的水平条。每个外部节点都是一个NULL指针。

现在进行前序遍历。当您找到外部节点（即空指针）时，您打印NULL和eol。当您找到内部节点（与NULL不同）时，您将输出密钥值加上eol。

您将获得正是您所提供的序列。

因此，任务是从这种卢卡西维奇遍历重建原始的树。这样的任务可以通过这样的例程完成：

Node * to_tree(istream & input) 
{ 
    string val; 
    input >> val; 
    if (val == "NULL") 
    return nullptr; 

    Node * p = new Node; 
    p->get_key() = atoi(val.c_str()); 
    p->left = to_tree(input); 
    p->right = to_tree(input); 

    return p; 
}

如果序列正确生成，那么你可以安全地调用这个函数没有任何风险;它会结束。如果你有兴趣验证输入，那么你可以做一个预处理。你初始化一个计数器为零。每次找到一个密钥时，您加1，当您找到一个NULL时，您减1。正确的序列必须以-1结尾。因此，这是因为n节点的所有二进制树具有n + 1外部节点（或NULL指针）。最后访问的节点是外部的，这是唯一的，最后一次计数器达到-1。瞧

./my-program < my-input

等：

你可以自己日常适应你树的实现，写一个程序：

int main(int, char **) 
{ 
    Node * root = to_tree(cin); 
    return 0; 
}

你编译它，然后你执行！

来源

2015-11-12 19:47:49 lrleon

从建立二叉树给定的数据

回答

相关问题