标签: binary-tree

上面的图片来自"维基百科在AVL树上的条目",维基百科表示这是不平衡的.这棵树怎么还没有平衡？这是文章的引用:

节点的平衡因子是其右子树的高度减去其左子树的高度,并且具有平衡因子1,0或-1的节点被认为是平衡的.具有任何其他平衡因子的节点被视为不平衡,需要重新平衡树.平衡因子或者直接存储在每个节点上,或者从子树的高度计算出来.

左右子树的高度均为4.左侧树的右子树的高度为3,仍然只有1小于4.有人可以解释我缺少的东西吗？

考虑二叉树:

1. Ñ是一个节点,如果Ñ是整数
2. (+ a b)是节点,如果a和b是节点.

我们有以下三个操作:

1. (+ a b) - >(+ b a)
2. (+(+ a b)c) - >(+ a(+ b c))
3. (+ a(+ b c)) - >(+(+ a b)c)- (2.反向)

我需要一种算法来使用这些操作给出给定树的所有可能的排列.任何操作都可以应用于任何子树.对于排列,我的意思是任何具有完全相同的叶子集的树.这可能不是很困难,但我似乎无法弄明白.

[编辑]叶子也可以是名称(即变量),因此不能选择依赖于它们的属性作为整数.树确实代表了总和.

[编辑2]这个练习的要点是通过找到形式A和-A的术语来减少总和,调整树以使它们进入子树(+ A -A)以消除它们.上面的三个操作是我系统中的公理,它们需要一直使用,否则无法证明简化树等于原始树.由于我使用的是Twelf逻辑编程语言,如果我能找出算法来做我最初提出的问题,其余的就很容易了,但是替代解决方案当然是受欢迎的.

有没有一种方法来构建平衡的二叉搜索树？

例:

1 2 3 4 5 6 7 8 9

       5
      / \
     3   etc
    / \
   2   4
  /
 1

我想有一种方法可以做到这一点,而不使用更复杂的自平衡树.否则我可以自己做,但有人可能已经这样做了:)

谢谢你的回答!这是最后的python代码:

def _buildTree(self, keys):
    if not keys:
        return None

    middle = len(keys) // 2

    return Node(
        key=keys[middle],
        left=self._buildTree(keys[:middle]),
        right=self._buildTree(keys[middle + 1:])
        )

现在我有

 private static void iterateall(BinaryTree foo) {
    if(foo!= null){
    System.out.println(foo.node);
    iterateall(foo.left);
    iterateall(foo.right);
   }
  }

你能把它改成Iteration而不是递归吗？

我已经实现了一个二叉搜索树,我想在其插入函数中添加更多功能,使其成为一个自平衡树.我在C#编码.

任何人都可以建议我很好的教程或链接吗？我做了一些搜索并找到了一些链接,但它们都没有足够的描述性.

谢谢.

试图通过网络进行大量探索,但可以得到任何帮助,Everywhere就像在Binary Search树中添加一个节点一样.

问题:请求用于将节点添加到二叉树的算法和代码片段.(或指向我更正网址)

假设:根据我的理解,二叉树和二叉搜索树是不同的？如果我错了,请纠正我.

(请求:如果您正在编写代码片段,请使用适当的变量名称,这有助于理解)

例如:二叉树

5 7 3 x1 x2 x3

                 5

          7               3

   x1       x2       x3       

二进制搜索树5 7 3 2 4 6

                   5
          3               7

   2          4       6       





insert(int key, struct node **root)
{
    if( NULL == *root )`
    {
        *root = (struct node*) malloc( sizeof( struct node ) );`
        (*root)->data = key;
        (*root)->left = NULL;    
        (*root)->right = NULL;  
    }
    else if(key < (*root)->data)
    {
        insert( key, &(*root)->left );
    }
    else if(key …

我在C中的链表的插入方法遇到了一些麻烦.它似乎只在列表的开头添加.我做的任何其他插入都失败了.而这个CodeBlocks调试器很难理解我仍然没有得到它.它永远不会给我价值,只有内存中的地址.无论如何这是我的功能.你有没有看到它失败的原因？

/* function to add a new node at the end of the list */
int addNodeBottom(int val, node *head){

    //create new node
    node *newNode = (node*)malloc(sizeof(node));

    if(newNode == NULL){
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(-1);
    }

    newNode->value = val;

    //check for first insertion
    if(head->next == NULL){
        head->next = newNode;
        printf("added at beginning\n");
    }

    else
    {
        //else loop through the list and find the last
        //node, insert next to it
        node *current = head;
        while(current->next != NULL) …

这是勇敢的脑筋急转弯.我已经好几天了,只是无法提供解决方案.

我想提出这样的事情:

仅使用html,CSS和PHP.

我靠近了,但不是我所期待的.这是PHP中的代码,这是输出.

<table border="0">
<thead>
    <tr>
        <th>Cientoveintiochavos</th>
        <th>Seseintaicuatravos</th>
        <th>Treintaidosavos</th>
        <th>Dieciseisavos</th>
        <th>Octavos</th>
        <th>Cuartos</th>
        <th>Semifinales</th>
        <th>Final</th>
    </tr>
</thead>
<tbody>
<?php for($i=0;$i<256;$i++): ?>
    <tr>
        <?php for($n=0,$c=2;$n<8;$n++,$c*=2): ?>
            <?php 
            /*
            if(false){//$i == 0) {
                $rwspn = $c/2+1; 
                $iter = 0;
            } else {
                $rwspn = $c; 
                $iter = $c;//-$c/2+1;
            } 
            */
            $class = ($i%($c*2))?'par':'impar winner';
            if($i%$c==0):?>
                <td rowspan="<?=$c;?>" class="<?=$class;?>"><span><?php echo genRandomString();?></span></td>
            <?php endif; ?>
        <?php endfor; ?>
    </tr>   
<?php endfor; ?>
</tbody>
</table>

如果有人知道如何表示二叉树或树形图或提出更智能的代码,请告诉我!

考虑以下数组,声称代表了二叉树:

[1,2,5,6,-1,8,11]

鉴于值为-1的索引表示根元素,我在下面的问题:

a)这实际上是如何表示的？

我们应该遵循以下公式(来自此链接的来源)来找出树吗？三个简单的公式允许您从父项的索引转到其子项的索引,反之亦然:

* if index(parent) = N, index(left child) = 2*N+1
* if index(parent) = N, index(right child) = 2*N+2
* if index(child) = N, index(parent) = (N-1)/2 (integer division with truncation)

如果我们使用上面的公式,那么index(root)= 3,index(left child)= 7,它不存在.

b)知道它是否是完整的二叉树是否重要？

我有BinaryTreeNode(int值)及其左右子类和BinaryTree(int rootVal),BinaryTreeNode根,其中rootVal为其值.我开发了一个代码来计算树中的节点数(在BinaryTreeNode类中),但是由于NullPointerException它不起作用:

public int size(){
    if(this == null) {    // base case
        return 0;
    } else {
        return 1 + left.size() + right.size();
    }
}

然而,我发现的另一种解决方案,采用类似的策略,有效:

public int size(BinaryTreeNode refNode){
    if(refNode == null) {    // base case
        return 0;       
    } else {
        return 1 + size(refNode.left) + size(refNode.right); 
    }
}

我已经理解为什么我的代码抛出异常(因为左/右指向null).但我想理解为什么第二种解决方案与准原理相同.先感谢您!