时间戳

首页 > 解决方案 > 二叉树节点和与父节点的关系

c - 二叉树节点和与父节点的关系

问题描述

我知道如何编写二叉搜索树，并以中序、前序或后序方式遍历它。但是，我想知道如何知道实际节点在哪里：

例如，假设我们有以下值： 70 90 50 60 80 40 所以根将是 70，其右侧为 90，左侧为 50，右侧为 60 到 50，依此类推。

所以如果我要打印这个顺序，它将是 40 50 60 70 80 90，增加了相当多的顺序。我通过在递归遍历函数中这样做：

traverse(root->left);
printf("%d ", root->data);
traverse(root->right);

但这并没有让我知道（据我所知）节点当前在哪里。有没有办法像这样打印树？：

70
50 (70 L) 90 (70 R) // 我们知道节点来自哪个父节点，并且我们知道它是它的左边还是右边。
40 (50 升) 60 (50 右) 80 (90 升)

等等..如果树更大。我真的不知道我会怎么做。我需要将他们与他们的父母联系起来吗？但是，如果我这样做，我怎么知道左右呢？或者我是否需要在迭代器仍在父级时打印子级。先感谢您。

编辑：我通过逐级遍历查找打印树，但我认为我不了解节点的父节点和侧..我正在尝试将一些代码实现为 c 代码，但我总是会崩溃。

标签： ctreebinarystructure

解决方案

似乎您想逐级打印树，即

level 0:   node0
level 1:   node1 (node0 L) node2 (node0 R)
level 2:   ...

因此，您需要一种方法来跟踪当前级别和目标级别（即您要打印的级别）。您还需要一种方法来跟踪“没有更多级别”的时间（即不再打印）。

这可以通过多种方式完成。下面的伪代码应该让您了解一种方法。这不是最有效的方法，但它非常简单。

就像是：

bool btPrintLevel(node* root, int targetlevel, int currentlevel)
{
    if (targetlevel == currentlevel) return false; // no need to go further down in levels

    bool result = false;
    result |= btPrintLevel(root->left, targetlevel, currentlevel + 1);

    // psedo code
    if ((currentlevel + 1 == targetlevel)
    {
        if (childern_exists)
        {
            printChildern(...)
            result = true;
        }
    }
    result |= btPrintLevel(root->right, targetlevel, currentlevel + 1);
    return result;
}

像这样调用：

int level = 0;
while(btPrintLevel(head, level)) ++level;

这个How to print elements from Binary Tree by level in c也可能有帮助。它并不完全符合您的要求，但只需稍作修改即可实现您的目标。

推荐阅读