标签: binary-tree

测试中的一个问题：

设T为 AVL 树， 为x,y树中的两片叶子 ( x != y)。的最大值是多少depth(x) - depth(y)？

A. 0
B. 1
C. 2
D. None of the above

正确的（？）答案是 D。有人可以解释为什么它不是 B，因为 AVL 属性之一是height(a.left) - height(a.right) <= 1每个节点的属性a？

我不是计算机科学学生，所以这不是家庭作业。我正在尝试自己学习这些东西，但我想确保我不会在此过程中养成坏习惯。

基本上，我有一个经典的二叉树，我想计算树的高度（或深度）。

我所说的高度是这样的：

这棵树的高度是3。

这是我想出的蟒蛇：

def height(node):

    #highest one of these two will be returned
    i_left = 0
    i_right = 0

    #if has left, increment and recursively move left
    if node.hasleft():
        i_left += height(node.left)
        i_left += 1

    #if has right, increment and recursively move right
    if node.hasright():
        i_right += height(node.right)
        i_right += 1

    #return the higher value
    if i_right <= i_left:
        return i_left    
    return i_right

这个解决方案很有效，我有点喜欢它，因为它很简单，并且没有很多抽象的东西需要你思考。但是，我确实想知道这是否应该这样做。有什么方法可以改进，或者有没有更可接受的方法来实现高度函数？

我有一个动态数据结构，如下所示：

struct tree_node {
    int y;
    int x;
    struct tree_node *left;
    struct tree_node *right;
    struct tree_node *parent;
};

该结构是二叉树的一个节点，此外每个节点还指向其父节点。现在，使用 I 向二叉树添加节点的经典方法malloc()可以轻松填充二叉树。但是，我在从内存中释放二叉树时遇到问题。

通常，要从二叉树中删除节点，您需要执行后序遍历，然后释放每个节点，如下所示：

void deleteTree(struct tree_node* node)
{
    if (node == NULL) return;

    deleteTree(node->left);
    deleteTree(node->right);

    printf("Deleting node with values [%d][%d]\n", node->y , node-> x);

    free(node -> left);
    free(node -> right);
    free(node -> parent);
    free(node);
    printf("\nNode deleted");
}

但是，当我运行上述函数时，它不会从内存中释放二叉树。当我运行该函数时，它会释放一个叶子，然后当它尝试删除下一个节点时，它会陷入无限循环，我的计算机要么崩溃，要么程序因非描述性错误退出。

终端中的输出如下：

Deleting node with values [11][4]
Node deleted
Deleting node with values [7739840][0]

因此，终端显示它删除了第一个叶子节点，然后尝试从下一个节点获取值，但无法获取（这就是它显示 7739840 的原因）。然后它陷入无限循环，因为它不打印“节点已删除”。

如何正确释放内存？这与我的节点构建方式有关吗？

我正在编写二进制搜索树模板有两个原因 - 学习C++并学习最常见的算法和数据结构.
所以,这里有一个问题 - 只要我想实现迭代器,在我看来,树的结束没有严格的定义.你有什么建议？我该怎么做呢？

二进制数字树,具有节点结构

type def numbernode
{
    unsigned value;
    numbernode * left;
    numbernode * right;
}

如果树不为空,则在最大(numbernode*树)中写入函数的外部指针(到根节点)将返回树中的最大数字.如果树为空,则函数应返回-1.

这是一个测试的练习题,我花了好几个小时试图搞清楚,我需要一些代码帮助!!

这是二叉搜索树的代码

#include<stdio.h>
#include<conio.h>
#include"malloc.h"

struct node
{
    int data;
    struct node* left;
    struct node* right;
};
int size(struct node* n)
{
    if(n==NULL)
       return 0;
    else
       return (size(n->left)+1+size(n->right));
}

int maxdepth(struct node* n)
{
    int ldepth,rdepth;
    if(n==NULL)
    {
       return 0;
    }
    else
    {
       ldepth=maxdepth(n->left);
       rdepth=maxdepth(n->right);
       if(ldepth>rdepth)
          return (ldepth+1);
       else
          return (rdepth+1);
    }
}

int lookup(struct node* node,int target)
{
    if(node==NULL)
       return 0;
    else if(target==node->data)
       return 1;
    else if(target<node->data)
       return(lookup(node->left,target));
    else
       return(lookup(node->right,target));
}

struct node* newnode(int data)
{
     struct node* newnod=(struct node*)malloc(sizeof(struct …

   public void Insert(int value)
    {
        if (value < Data)
        {
            if (LeftNode == null)
            {
                LeftNode = new TreeNode(value);
            }
            else
            {
                LeftNode.Insert(value);
            }
        }
        else if (value > Data)
        {
            if (RightNode == null)
            {
                RightNode = new TreeNode(value);
            }
            else
            {
                RightNode.Insert(value);
            }
        }
    }

我编写了以递归方式在BST中添加元素的方法,它检查要添加小于或大于的值并将其添加到适当的位置,但我想知道迭代方法是如何工作的？我需要为我的BST迭代添加方法.

我很难习惯Haskell中的递归,无论如何有人可以向我解释我将如何解决这个问题.我看过其他一些帖子,但我无法弄明白该怎么做.

我有我的类型

data BST = MakeNode BST String BST
             | Empty              

我不确定如何检查树下每一条路径的组合.

有没有办法以递归方式遍历树并返回一个作用于该递归方法的数组？

所以我最近回答了别人关于这个话题的问题.这个问题可以在这里找到:SO问题.我的解决方案使用了递归范围之外的数组,因此该方法不能(或至少可能不应该)返回数组.但是,有没有办法编写一个遍历树的递归方法,以便返回一个数组？即使编写一个调用递归方法的初始方法也没关系,但我想不出一个好方法.

这是我之前建议的代码:

private List nodeValues = new ArrayList();

public void traversePreRecursive(BinarySearchTreeNode node) 
{
    if (node != null)
    {
        nodeValues.add(node.getValue());
        traversePreRecursive(node.getLeft());
        traversePreRecursive(node.getRight());
    }
}

正如你所看到的那样,ArrayList它超出了递归范围 - 因此返回它并没有多大意义.有一个更好的方法吗？

我收到以下编译错误:

错误:从'const IntervalST '到'IntervalST '的无效转换[-fpermissive]

当我编译我的代码.代码很大但这里是相关部分:

IntervalST类:

template <class Key> class intervalST_const_iterator;

template <class Key> class IntervalST
{
private:
    Interval<Key> *root;

    //friend class intervalST_const_iterator<Key>;//allow the iterator class to access the private section of intervalST

    bool isRed(Interval<Key> *interval);
    Interval<Key> *rotateLeft(Interval<Key> *h);
    Interval<Key> *rotateRight(Interval<Key> *h);
    Interval<Key> *put(Interval<Key> *h,Key lo, Key hi, Key val);
    Interval<Key> *moveRedLeft(Interval<Key> *h);
    Interval<Key> *moveRedRight(Interval<Key> *h);
    Interval<Key> *deleteMin(Interval<Key> *h, Key hi);
    Interval<Key> *balance(Interval<Key> *h);
    Interval<Key> *remove(Interval<Key> *h, Key lo, Key hi);
    Interval<Key> *min(Interval<Key> *h);
    Interval<Key> *addDuplicate(Interval<Key> *h, Key hi); …