2

这里是c中的一个简单的二叉树，但是好像不平衡，怎么让它平衡呢？

代码：

/**
 * binary_tree impl
 */

#include <stdio.h>
#include <stdlib.h>


typedef struct _tnode _tnode;
typedef struct _bin_tree _bin_tree;
struct _tnode {
    int data;
    _tnode *parent;
    _tnode *left;
    _tnode *right;
};

_tnode *new_node(int data) {
    _tnode *node = (_tnode*)malloc(sizeof(_tnode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

_tnode *add(_tnode *top, int new_data, int (*cmpf)(int, int)) {
    if(top == NULL) {
        top = new_node(new_data);
    } else if(cmpf(top->data, new_data)<=0) {
        if(top->left == NULL) 
            top->left = new_node(new_data);
        else
            add(top->left, new_data, cmpf);
    } else {
        if(top->right == NULL) 
            top->right = new_node(new_data);
        else
            add(top->right, new_data, cmpf);
    }
    return top;
}

int cmp_int(int n1, int n2) {
    return n1 - n2;
}

void print_tree(_tnode *top) {
    if(top->left) print_tree(top->left);
    printf("%d\n",top->data);
    if(top->right) print_tree(top->right);
}

int main(int argc, char * argv[]) {
    int i = 0;
    _tnode *top = NULL;
    int arr[] = {6,1,9,3,5,0,2,7};
    int count = sizeof(arr) / sizeof(arr[0]);
    for(i=0; i<count; i++) {
        top = add(top, arr[i], cmp_int);
        printf("add: %d\n", arr[i]);
    }

    print_tree(top);
    return 0;
}
4

1 回答 1

5

基本思路如下。

对于插入，您首先将新节点插入叶子，就像插入非平衡树一样。

然后你沿着树向根部前进，确保对于每个节点，左右子树之间的高度差永远不会超过一个。

如果是，则您“旋转”节点以使差异为1 或更少。例如，考虑以下树，它在添加之前32是平衡的，但现在不是：

      128
     /
   64
  /
32

节点处的深度差32为零，因为两个子树的深度都为零。

节点处的深度差64为 1，因为左子树的深度为 1，而右子树的深度为 0。

128节点处的深度差为2，因为左子树的深度为 2，而右子树的深度为 0。因此需要通过该节点进行旋转。这可以通过128向下推到右子树并调出64：

   64
  /  \
32    128

你又一次有了平衡。

当然，旋转方向取决于左侧或右侧的高度是否过多。

删除有点棘手，因为您不一定像插入一样在叶节点上工作。那里有点复杂，因为它取决于节点是没有孩子（是叶子）、一个孩子还是两个孩子。

1/ 对于叶节点，您可以将其删除，然后在该叶的父节点处开始重新平衡。

2/ 对于一个单子节点，你可以复制子信息（数据和链接）来替换你要删除的那个，然后删除子节点，然后开始重新平衡子信息现在所在的位置。

3/ 对于一个有两个孩子的节点，想法是找到它的直接后继（首先找到右孩子，然后不断地去左孩子，直到没有更多的左孩子）。您还可以找到它的直接前身（从左到右），它也同样有效。

然后将要删除的节点中的数据与后继（或前任）中的数据交换，然后重新应用此规则，直到要删除的节点是叶节点。然后使用与上述 (1) 完全相同的规则删除该叶节点。

这种交换技巧是完全有效的，因为即使交换使两个相邻的项目暂时失序，您删除其中一个项目（2在这种情况下）会自动修复问题：

  2           3           3
 / \   -->   / \   -->   /
1   3       1   2       1
=====       =====       =====
1,2,3       1,3,2       1,3
于 2015-06-03T04:26:49.423 回答