标签: binary-tree

我有一个看起来像(A(B(CD))(E(F)))的列表代表这个树:

      A
    /  \
  B      E
 / \    /
C   D  F

如何将其打印为(ABECDF)？

这是我管理的:

((lambda(tree) (loop for ele in tree do (print ele))) my-list)

但它打印:

A
(B (C D))
(E (F))
NIL

我对Common LISP很新,所以可能会有我应该使用的功能.如果是这样的话,那就让我开心吧.

谢谢.

我正在寻找大量的树数据结构,这真的令人困惑.就像我理解基本的二进制树(也是它的众多实现,如BST红黑树等)但我真正需要的是关于N'ary树的一些信息.我需要研究各种类型的N'ary树以及它们的性能比较.我见过的唯一N'ary树是B +树.我需要知道哪棵是最快的N'Ary树.即最明智的时间复杂度,空间复杂性是没有问题的.

我无法理解这个maxDepth代码.任何帮助,将不胜感激.这是我遵循的片段示例.

int maxDepth(Node *&temp)
{
  if(temp == NULL)
  return 0;

 else
{
 int lchild = maxDepth(temp->left);
 int rchild = maxDepth(temp->right);

 if(lchild <= rchild)
 return rchild+1;

 else
  return lchild+1;

 }

}

基本上,我理解的是函数递归调用自身(对于每个左右情况),直到它到达最后一个节点.一旦它,它返回0然后它做0 + 1.那么前一个节点是1 + 1.然后下一个是2 + 1.如果有一个包含3个左子节点的bst,则int lchild将返回3.而额外的+ 1是根节点.所以我的问题是,所有这些+1来自哪里.它在最后一个节点返回0,但为什么它在左/右子节点上升时返回0 + 1等？我不明白为什么.我知道它做到了,但为什么呢？

我正在尝试一种迭代方法来查找二叉搜索树的高度/深度.基本上,我尝试使用广度优先搜索来计算深度,方法是使用队列存储树节点并仅使用整数来保存树的当前深度.树中的每个节点都排队,并检查子节点.如果存在子节点,则增加深度变量.这是代码:

public void calcDepthIterative() {
    Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
    TreeNode node = root;
    int level = 0;
    boolean flag = false;

    nodeQ.add(node);
    while(!nodeQ.isEmpty()) {
        node = nodeQ.remove();
        flag = false;
        if(node.leftChild != null) {
            nodeQ.add(node.leftChild);
            flag = true;
        }

        if(node.rightChild != null) {
            nodeQ.add(node.rightChild);
            flag = true;
        }
        if(flag) level++;
    }
    System.out.println(level);

}

但是,该代码并不适用于所有情况.例如,对于以下树:

     10
   /    \
  4      18
   \    /  \
    5  17   19

它将深度显示为3,而不是2.我使用此页面中的想法使用额外的队列来存储当前深度的替代版本.我想避免使用额外的队列,所以我试图优化它.这是有效的代码,尽管使用了额外的Queue.

public void calcDepthIterativeQueue() {
    Queue<TreeNode> nodeQ = new LinkedList<TreeNode>();
    Queue<Integer> lenQ …

我一直在寻找如何计算二进制搜索树的高度,我的研究引导我进行以下实现.我仍然试图解决为什么它应该工作,但我也不确定为什么它不起作用.这是我的身高功能.

int BinaryTreeNode::height() const {
    int lefth = left->height();
    int righth = right->height();
    if(lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

这是节点的我的类定义

class BinaryTreeNode {
  public:
    Data * nodeData;
    BinaryTreeNode * left;
    BinaryTreeNode * right;

当我尝试运行它时,程序会锁定并崩溃.我错过了一些明显的东西吗

编辑:为什么不这样做？

int BinaryTreeNode::height() const {
    int l = 0;
    if (left != NULL) {
        left->height();
    }
    int r = 0;
    if (right != NULL) {
        right->height();
    }
    if (l > r) {
        return l + …

typedef struct _Tree{
    int val;
    struct _Tree *left;
    struct _Tree *right;
}Tree;

这是Tree一个指针吗？它是否指向val的地址？

如果我定义的话怎么Tree *node样？是node指向地址的指针Tree吗？

如果我们想插入val,我们应该使用insert(&node)或insert(node)？

void insert_Tree(Tree **root, int key){
if((*root) == NULL){
    (*root) = (Tree *)malloc(sizeof(Tree));
    (*root)->val = key;
    (*root)->left = NULL;
    (*root)->right = NULL;
    cout<<"insert data "<<key<<endl;
}else if(key< (*root)->val){
    insert_Tree(&(*root)->left, key);
    cout<<"go left"<<endl;
}else{
    insert_Tree(&(*root)->right, key);
    cout<<"go right"<<endl;
}
}
int main(){

Tree *root = NULL;
insert_Tree(&root, 10);
insert_Tree(&root, 20);
insert_Tree(&root, 5); …

有可能计算出有多少节点有任意二叉树吗？叶子数和每片叶子的深度是已知的(实际上是霍夫曼树).

我需要它,以便能够在实际构建树之前为树分配所需的内存,并避免以后重新分配内存.

我不认为我正确地遍历它并且当它需要返回一个新列表时它返回空.我已经被困了一段时间,仍然需要做所有其他的遍历.将为所需的输出提供单元测试,但我的单元测试可能是错误的.

def inorder(self):

    print("in INOrDER is entered")
    temp = [None]


    if self.__left:
        temp = temp.append(self.__left)
        return self.__left.inorder() 
    elif self.__right: 
        temp = temp.append(self.__right)
        return self.__right.inorder() 
    return temp


def test_inorder(self):
    bt = family_tree()
    bt.add(20, "melanie")
    bt.add(10, "edwin")
    bt.add(30, "junior")
    bt.add(25, "dora")
    bt.add(35, "kate")
    x = bt.inorder()

    expected = '''(10, 'edwin'),(20, 'melanie'),(25, 'dora'),(30, 'junior'),(35, 'kate')'''
    self.assertEquals(str(x), expected)
    t = family_tree(bt)
    self.assertEquals(str(t), expected)

我在一本书中看到了这个问题（破解编码面试）。建议的代码是：

public boolean isBalanced(Node root) {

    if(root == null)
        return true;

    int leftHeight = getHeight(root.left);
    System.out.println("left height: " + leftHeight);
    int rightHeight = getHeight(root.right);
    System.out.println("right height: " + rightHeight);
    int diff = Math.abs(leftHeight - rightHeight);

    // check if difference in height is more than 1
    if (diff > 1)
        return false;

    // check if left and right subtrees are balanced
    else 
        return isBalanced(root.left) && isBalanced(root.right);

我不明白的部分是为什么我们需要返回isBalanced（root.left）&& isBalanced（root.right）。仅检查高度并在高度大于1时返回false，否则返回true是否足够？

给定一棵树的有序和有序遍历，如何以非递归方式重构该树。

例如：

重建下面的树

                     1
       2                             3
 4           5                6             7
                  8                     9

给定

有序遍历：4，2，5，8，1，6，3，9，7

预遍遍历：1、2、4、5、8、3、6、7、9

注意：有很多关于递归实现的参考。例如，可以从给定的有序遍历和预序遍历引用构造树。但是，这里的目的是要找到非递归实现。