标签: binary-tree

在不使用递归的情况下,对二叉树进行后序遍历的算法是什么？

我想知道是否有人可以帮我修改这个方法来找到二叉搜索树的高度.到目前为止,我的代码看起来像这样.但是,我得到的答案比实际高度大1.然而当我从我的返回语句中删除+1时,它比实际高度小1.我仍然试图用我的头围绕递归这些BST.任何帮助将非常感激.

public int findHeight(){
    if(this.isEmpty()){
        return 0;
    }
    else{
        TreeNode<T> node = root;
        return findHeight(node);
    }
}
private int findHeight(TreeNode<T> aNode){
    int heightLeft = 0;
    int heightRight = 0;
    if(aNode.left!=null)
        heightLeft = findHeight(aNode.left);
    if(aNode.right!=null)
        heightRight = findHeight(aNode.right);
    if(heightLeft > heightRight){
        return heightLeft+1;
    }
    else{
        return heightRight+1;
    }
}

我已经看过我最近读过的几本书中提到的二叉树和二进制搜索,但是由于我还在学习计算机科学,我还没有上一个真正处理算法和数据的课程.结构严肃.

我查看了典型的来源(维基百科,谷歌),大多数关于(特别是)红黑树的实用性和实施​​的描述都是密集且难以理解的.我确信对于具有必要背景的人来说,它是完全合理的,但此刻它几乎就像一本外语.

那么是什么让二进制树在你编程时发现的一些常见任务中有用呢？除此之外,您更喜欢使用哪些树(请包括示例实现)以及为什么？

我理解为什么不能这样做的原因(重新平衡和东西):

iterator i = m.find(33);

if (i != m.end())
  i->first = 22;

但到目前为止,改变密钥的唯一方法(我知道)是从树中删除节点,然后使用不同的密钥插入值:

iterator i = m.find(33);

if (i != m.end())
{
  value = i->second;
  m.erase(i);
  m[22] = value;
}

由于更多原因,这似乎对我来说效率很低:

1. 遍历树三次(+余额)而不是两次(+余额)
2. 还有一个不必要的价值副本
3. 不必要的重新分配,然后重新分配树内的节点

我发现分配和释放是这三者中最差的.我错过了什么或有更有效的方法吗？

更新:我认为,从理论上讲,它应该是可能的,所以我不认为改变不同的数据结构是合理的.这是我想到的伪算法:

1. 找到树中我想要更改其键的节点.
2. 如果从树上分离(不要解除分配)
3. 重新平衡
4. 更改分离节点内的密钥
5. 将节点插回树中
6. 重新平衡

什么是用于测试树是否对称的基础算法.因为它是二叉树,我认为它将是一种递归的排序定义

正式问题如下:

如果二进制树的左右子树是相同的镜像,即二叉树是对称的,则它是自身的镜像.最好用几个例子来解释.

  1
 / \
2   2

真正

   1
  / \
 2   2
  \
   3

假

     1
   /   \
  2     2
 / \   / \
4   3 3   4

真正

       1
     /   \
    2     2 
   / \   / \
  3   4 3   4

假

       1
     /   \
    2     2
   /       \
  3         3

真正

在选择的编程语言中,定义BTree类/ C结构和相关方法以检查树是否是镜像.对于静态类型语言,您可以假设节点值都是整数.

Class/structure definition
BTree {
  BTree left;
  BTree right;
  int value;
}

假设调用者跟踪树的根,并在其上调用函数isMirror().

此外,如果定义一个类,如果数据元素不可公开访问,请确保提供无参数构造函数和getter/setter方法.

这不是作业,这是一个面试问题.

这里的问题是算法应该是恒定的空间.我对如何在没有堆栈的情况下做到这一点非常无能为力,我会发布我使用堆栈编写的内容,但无论如何它都不相关.

这是我尝试过的:我试图进行预订遍历,然后我到了最左边的节点,但我被困在那里.我不知道如何在没有堆栈/父指针的情况下"recurse"备份.

任何帮助,将不胜感激.

(我将它标记为Java,因为这是我很习惯使用的,但它显然是语言无关的.)

我正在网上搜索"内部节点"一词的定义.我找不到简洁的定义.我正在查看的每个源都使用该术语而不定义它,并且使用不会产生对内部节点实际内容的正确定义.

以下是我主要关注的两个地方:http: //planetmath.org/encyclopedia/ExternalNode.html假设内部节点是有两个非空子树的节点,但没有说明原始树是内部的与外部的.

http://www.math.bas.bg/~nkirov/2008/NETB201/slides/ch06/ch06-2.html似乎暗示内部节点只存在于适当的二叉树中,并且不会产生关于它们的有用信息.

实际上是一个内部节点!？

我最近听说过三元搜索,我们将一个数组分成3个部分进行比较.这里将进行两次比较,但它将数组减少到n/3.人们为什么不用这么多？

如果我使用b树实现内存(RAM)搜索操作,那么与二叉树相比,它在缓存或其他一些效果方面会更好吗？

我所知道的是

binary search tress---O(log n)
btrees ---------------O(c log n)

在各种博客上有很多关于这方面的讨论.

我正在看面试问题,最近我遇到了一个问你如何反转一般二叉树的问题,比如从右到左翻转它.

例如,如果我们有二叉树

     6
   /   \
  3     4
 / \   / \
7   3 8   1

扭转它会创造

     6
   /   \
  4     3
 / \   / \
1   8 3   7

我还没有想到如何解决这个问题的良好实现.谁能提供任何好的想法？

谢谢