标签: binary-tree

如果两个给定的二叉树是相等的 - 在结构和内容中,找到有效的算法是什么？

我正在努力想弄清楚如何为我的班级平衡AVL树.我已经插入了这个:

Node* Tree::insert(int d)
{
    cout << "base insert\t" << d << endl;
    if (head == NULL)
        return (head = new Node(d));
    else
        return insert(head, d);
}

Node* Tree::insert(Node*& current, int d)
{
    cout << "insert\t" << d << endl;
    if (current == NULL)
        current = new Node(d);
    else if (d < current->data) {
        insert(current->lchild, d);
        if (height(current->lchild) - height(current->rchild)) {
            if (d < current->lchild->getData())
                rotateLeftOnce(current);
            else
                rotateLeftTwice(current);
        }
    }
    else if (d > current->getData()) {
        insert(current->rchild, d);
        if (height(current->rchild) …

如何合并2个二叉搜索树,使得结果树包含两个树的所有元素,并保持BST属性.

我看到了如何有效地合并两个BST中提供的解决方案 ？

但是,该解决方案涉及转换为双链表.我想知道是否有一种更优雅的方式可以在没有转换的情况下完成.我想出了以下伪代码.它适用于所有情况吗？我也遇到了第三种情况的问题.

node* merge(node* head1, node* head2) {
        if (!head1)
            return head2;
        if (!head2)
            return head1;

        // Case 1.
        if (head1->info > head2->info) {
            node* temp = head2->right;
            head2->right = NULL;
            head1->left = merge(head1->left, head2);
            head1 = merge(head1, temp);
            return head1;
        } else if (head1->info < head2->info)  { // Case 2
            // Similar to case 1.
        } else { // Case 3
            // ...
        }
}

平衡二叉树和完整二叉树之间有什么区别？
说每个完整的二叉树都是平衡树是真的吗？
反过来怎么样？

我想知道这里是否有人使用跳过列表.它看起来与平衡二叉树具有大致相同的优点,但实现起来更简单.如果你有,你是自己编写的,还是使用预先编写的库(如果有的话,它的名字是什么)？

我正在尝试使用GraphViz重新创建二叉搜索树的示例图.这是它最终应该看起来的样子:

这是我的第一次尝试:

digraph G {
    nodesep=0.3;
    ranksep=0.2;
    margin=0.1;
    node [shape=circle];
    edge [arrowsize=0.8];
    6 -> 4;
    6 -> 11;
    4 -> 2;
    4 -> 5;
    2 -> 1;
    2 -> 3;
    11 -> 8;
    11 -> 14;
    8 -> 7;
    8 -> 10;
    10 -> 9;
    14 -> 13;
    14 -> 16;
    13 -> 12;
    16 -> 15;
    16 -> 17;
}

但不幸的是GraphViz并不关心树的水平位置,所以我得到:

如何添加约束以使顶点的水平位置反映其总排序？

两个二叉树是同构的意味着什么？我一直在网上看,我似乎无法找到明确的解释.

据我所知,如果它们具有相同的形状,则两棵树是同构的.所以我猜两个相同的树,它们可以在节点中包含不同的值.

这不是功课,我不需要回答它,但现在我已经变得痴迷:)

问题是:

• 设计一种算法,将二叉树破坏性地展平为链表,广度优先.好的,够容易的.只需构建一个队列,并做你需要做的事情.
• 那是热身.现在,使用常量存储实现它(递归,如果你能用它来找出答案,那就是对数存储,而不是常数).

大约一年前我在互联网上找到了这个问题的解决方案,但现在我已经忘记了,我想知道:)

据我记忆,这个技巧涉及使用树来实现队列,利用算法的破坏性.链接列表时,您还将项目推入队列.

每次我尝试解决这个问题,我都会丢失节点(比如每次我链接下一个节点/添加到队列中),我需要额外的存储空间,或者我无法弄清楚我需要回到一个复杂的方法具有我需要的指针的节点.

即使链接到原始文章/帖子对我也很有用:)谷歌没有给我带来快乐.

编辑:

Jérémie指出,如果你有一个父指针,有一个相当简单(和众所周知的答案).虽然我现在认为他对包含父指针的原始解决方案是正确的,但我真的想在没有它的情况下解决问题:)

精炼的需求将此定义用于节点:

struct tree_node
{
  int value;
  tree_node* left;
  tree_node* right;
};

给定二叉搜索树和目标值,找到总计达目标值的所有路径(如果存在多个路径).它可以是树中的任何路径.它不必来自根.

例如,在以下二叉搜索树中:

  2
 / \ 
1   3 

当总和应为6时,1 -> 2 -> 3应打印路径.

我使用以下方法遍历*300 000级别的二叉树:

Node* find(int v){
   if(value==v)
      return this;
   else if(right && value<v)
      return right->find(v); 
   else if(left && value>v)
      return left->find(v);
}

但是由于堆栈溢出,我得到了分段错误.关于如何在没有递归函数调用开销的情况下遍历深层树的任何想法？

*"遍历"我的意思是"搜索具有给定值的节点",而不是完整的树遍历.