标签: binary-tree

我知道在二叉搜索树上的有序遍历(VISIT LEFT,VISIT ROOT,VISIT RIGHT)给出了一个排序结果.但我需要在二叉树上进行后序遍历(VISIT LEFT,VISIT RIGHT,VISIT ROOT),结果应该给出排序值.

为了实现这一点,我应该如何构建我的二叉树？

所以,我只是在Reflector周围试图找到HashSet的实现细节(基于这里的另一个问题的答案纯粹的好奇心)并注意到以下内容:

internal class TreeSet<T> : ICollection<T>, IEnumerable<T>, ICollection,
    IEnumerable, ISerializable, IDeserializationCallback

在不深入细节的情况下,它看起来像一个自平衡二进制搜索树.

我的问题是,有没有人知道为什么这堂课internal？仅仅因为其他集合类型在内部使用它并隐藏了BST与普通群众的复杂性......还是我离开了基地？

当要删除的节点有两个子节点时,请考虑BST上的删除过程.假设我总是用在其右子树中保持最小键的节点替换它.

问题是:这个程序是可交换的吗？也就是说,删除x然后y与删除第一个y然后x？

我认为答案是否定的,但我找不到反例,也没有找出任何有效的推理.

编辑:

也许我必须更清楚.

考虑以下transplant(node x, node y)过程:将x替换为y(及其子树).所以,如果我想删除一个有两个子节点的节点(比如说x),我用它右边子树中保存最小键的节点替换它:

y = minimum(x.right)
transplant(y, y.right) // extracts the minimum (it doesn't have left child)
y.right = x.right
y.left = x.left
transplant(x,y)

问题是如何证明上述程序不是可交换的.

它是一个非常普通的二叉树,除了其中一个节点可能为空的事实.

我想找到一种以水平方式输出它的方法(也就是说,根节点在左侧并向右扩展).

我有一些垂直扩展树木的经验(根节点在顶部,向下扩展),但在这种情况下,我不知道从哪里开始.

最好是遵循以下几条规则:

• 如果一个节点只有一个子节点,则可以将其作为冗余跳过(始终显示"终端节点",没有子节点)
• 相同深度的所有节点必须垂直对齐; 所有节点必须位于所有较低深度节点的右侧,并且位于所有较深节点的左侧.
• 节点具有包含其深度的字符串表示.
• 每个"端节点"都有自己独特的线路; 也就是说,行数是树中终端节点的数量,当终端节点在一条线上时,该终端节点之后该行上可能没有其他内容.
• 作为最后一条规则的结果,根节点在左上角或左下角可能会更好; 左上角是首选.

例如,这是一个有效的树,有六个端节点(节点由一个名称及其深度表示):编辑:请参阅问题的底部以获得替代,更容易渲染

        
[a0]-----------[b3]------[c5]------[d8]
    \              \         \----------[e9]
     \              \----[f5]
      \-[g1]--------[h4]------[i6]
            \           \--------------------[j10]
             \-[k3]

它代表垂直的显式二叉树:

0              a
              / \
1            g   *
            / \   \
2          *   *   *
          /     \   \
3        k       *   b
                /   / \
4              h   *   *
              / \   \   \
5            *   *   f   c
            /     \     / \
6          *       i   *   *
          /           /     \
7        *           *       *
        /           / …

假设给出了一个级别顺序遍历输出.如何从填充了正确位置的数据构建二叉树？

请注意,我不是试图从给定的遍历输出中绘制树,而是从数组中读取遍历数据,然后通过C中的实际编码填充二叉树.

例如:

设a [] = {A,B,C,D,E,F,G}; //数组中的遍历输出

所以级别顺序树看起来像这样:

            A
           / \ 
          B   C
        / \  / \
       D   E F  G

假设有一个树节点结构,如下所示:

typedef struct node
{
    char data;
    struct node* left;
    struct node* right;
}tree;

现在我正在尝试读取[]值并对此树进行编码,使其看起来像图.有许多级别顺序遍历的例子,但是在二叉树构造的实际编码中找不到任何相关的东西.这有点像"遍历的逆转".

另请注意,这不是功课,但如果有更多人注意到这一点我没有标记问题.:)

为什么二元树要平衡很重要

问题是找出BST中任何路径上是否存在给定的总和.如果路径意味着根到叶子,那么这个问题很容易,或者如果路径意味着从根到叶子的路径的一部分可能不包括根或叶子,则该问题很容易.但这里变得困难,因为路径可能跨越节点的左右子节点.例如,在给定的图中,在圆圈路径上存在132的总和.我怎样才能找到这样一条路径的存在？使用散列来存储节点下的所有可能的总和是不受欢迎的!

我想使用graphviz绘制二叉树,并且重要的是节点的左子节点出现在右子节点的左侧(duh).如果没有留下的孩子,我想在左边留一个空的空间,以使视觉上清楚正确的孩子是正确的孩子.如果没有合适的孩子,我想做同样的事情(在右边应该有一个空的空间).

例如,我想要类似的东西:

A                     A
  \     instead of    |
    B                 B

我可以确保Graphviz将左侧子项放在右侧,使用ordering ="out",但如果没有左侧子项,则右侧子项可能出现在其父项下方.

如果我添加了一个缺少子节点的虚节点,我得到了正确的布局,但虚拟节点就在图片上(我不想要它们).我尝试使用style ="invis"作为虚拟节点和连接它们的边缘,但是就好像它们不存在于graphviz中一样.我怎样才能解决这个问题？

我试图在c ++中打印如下所示的二叉树,这有点"丢失":

            8
           / \
          /   \
         /     \
        5       10
       / \      / \
      2   6    9   11

我知道如何获得树的高度和每个级别中的节点数,但我无法弄清楚如何在根和第二级之间设置正确的空格数(根下面有3行) 3层,但我相信不是每次都这样,我认为它可能是更高树木高度的3倍).

我想帮助打印行中的这些空格和行之间的行数.谢谢.

我用c ++编写代码

Get height

int tree::getHeight(No *node) {
  if (node == NULL) return 0;
  return 1 + max(getHeight(node->esq), getHeight(node->dir));
}

Get number of nodes per line

void tree::getLine(const No *root, int depth, vector<int>& vals){
    int placeholder = 10;
    if (depth <= 0 && root != nullptr) {
        vals.push_back(root->chave);
        return;
    }
    if (root->esq != nullptr)
       getLine(root->esq, depth-1, vals);
    else …

我正在研究"将分类数组转换为具有最小高度的二进制搜索树",其中提出:

给定排序(递增顺序)数组,将其转换为创建具有最小高度的二叉树.

我无法找到为什么我的递归不会像我预期的那样停止.它应该在7通过时停止,并且不会再打印7.我也找到了类似的答案,它看起来像我的使用相同的策略,但它工作正常.(我不认为我的问题与上面列出的问题重复,但我仍然要感谢你为我们链接它们.他们给了我更多的想法来解决我的问题.)

我的代码如下:

public TreeNode sortedArrayToBST(int[] A) {  
    int len = A.length;
    if(len <= 0){
        return null;
    }

    TreeNode root = new TreeNode(A[(len - 1) / 2]);
    if(len == 1){
        return root;
    }
    else{
        helper(root, A, 0, len - 1);
    }
    return root;
}

public void helper(TreeNode root, int[] A, int leftPoint, int rightPoint){
    if((rightPoint - leftPoint) <= 0){
        return;
    }

    int mid = (rightPoint - leftPoint) / 2 + leftPoint;
    int leftChild = (mid - 1 - leftPoint) …