treedot.h
#include <stdio.h>
#include <string.h>
static void print_tree(FILE* f, tree* root) {
fprintf(f, " %d;n", root->key);
if (root->left) {
fprintf(f, " %d:sw->%d:n ;n",
root->key,
root->left->key);
print_tree(f, root->left);
} else {
fprintf(f, " {node[style=invis, width=.1]; il_%d; }n", root->key);
fprintf(f, " %d:sw->il_%d [style=invis];n", root->key, root->key);
}
if (root->right) {
fprintf(f, " %d:se->%d:n ;n",
root->key,
root->right->key);
print_tree(f, root->right);// segfault here according to backtrace
} else {
fprintf(f, " {node[style=invis, width=.1]; ir_%d; }n", root->key);
fprintf(f, " %d:se->ir_%d [style=invis];n", root->key, root->key);
}
}
static void tree2dot(tree *root, const char *filename) {
if (!root)
return;
char fullname[80] = {0};
strcpy(fullname, filename);
strcat(fullname, ".dot");
FILE* f = fopen(fullname, "w");
fprintf(f, "digraph %s {n", filename);
fprintf(f, " node [shape=circle]n");
fprintf(f, "nodesep=0.4;nranksep=0.5;nsplines=polylinen");
print_tree(f, root);
fprintf(f, "}n");
fclose(f);
}
avl.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <unistd.h>
typedef struct tree {
int key;
int height;
struct tree *left, *right;
} tree;
#include "tree2dot.h"
int max(int a, int b){
return a > b ? a : b;
}
tree *new_node(int key){
tree *node = malloc(sizeof *node);
node->key = key;
node->left = node->right = NULL;
node->height = 1;
return node;
}
int height(tree *t)
{
return t ? t->height : 0;
}
int bfactor(tree *t){
return height(t->left) - height(t->right);
}
void fixheight(tree *t){
t->height = 1 + max(height(t->left), height(t->right));
}
tree *rotateleft(tree *a){
tree *b = a->right;
a->right = b->left;
b->left = a;
fixheight(a);
fixheight(b);
return b;
}
tree *rotateright(tree *a){
tree *b = a->left;
a->left = b->right;
b->right = a;
fixheight(a);
fixheight(b);
return b;
}
tree *balance(tree *a){
fixheight(a);
if (bfactor(a) == -2) {
if (bfactor(a->right) > 0) {
a->right = rotateright(a->right);
fprintf(stderr, "big rotate right at %dn",a->key);
} else
fprintf(stderr, "rotateleft at %dn",a->key);
return rotateleft(a);
}
if (bfactor(a) == 2) {
if (bfactor(a->left) < 0) {
a->left = rotateleft(a->left);
fprintf(stderr, "big rotate left at %dn",a->key);
} else
fprintf(stderr, "rotateright at %dn",a->key);
return rotateright(a);
}
return a;
}
tree *insert(tree *t, int key){
if (!t)
return new_node(key);
else if (t->key > key)
t->left = insert(t->left, key);
else
t->right = insert(t->right, key);
return balance(t);
}
bool is_leaf(tree *t){
return !t->left && !t->right;
}
tree *single_child(tree *t){
if (t->left) {
if (t->right)
return NULL;
else
return t->left;
}
else if (t->right)
return t->right;
else
return NULL;
}
// Find the inorder successor assuming the right child exists.
tree *find_next(tree *t){
assert(t->right);
tree *p = t->right;
while (p->left)
p = p->left;
return p;
}
tree *delete(tree *p, int key){
assert(p);
if (p->key == key) {
tree *c;
if (is_leaf(p)) {
free(p);
return NULL;
} else if ((c = single_child(p))) {
free(p);
return c;
} else {
// Find the inorder successor. Would be beneficial to alternate with
// predecessor.
tree *n = find_next(p);
n->left = p->left;
n->right = p->right;
free(p); // balance!
return balance(n);
}
} else if ((p)->key > key)
p->left = delete(p->left, key);
else
p->right = delete(p->right, key);
return balance(p);
}
void rmtree(tree *t){
if (!t)
return;
rmtree(t->left);
rmtree(t->right);
free(t);
}
int main(void){
int key;
tree *root = NULL;
int n_el = 0;
char action;
while (1 == scanf(" %c", &action)) {
switch (action) {
case 'i':
scanf("%d", &key);
root = insert(root, key);
tree2dot(root, "avl");
n_el++;
break;
case 'd':
scanf("%d", &key);
root = delete(root, key);
tree2dot(root, "avl");
n_el--;
break;
default:
assert(false && "Unknown action");
}
}
tree2dot(root, "avl");
rmtree(root);
return 0;
}
tree2dot.h包含要转换为graphviz表示的代码。avl.c是AVL树实现。如果我删除有两个孩子的密钥，则在tree2dot.h中的第20行发生分割错误
我猜是堆栈溢出(avl.dot的大小约为48MiB(。删除密钥肯定是错误的
但是从树中删除有什么错误？如何修复？
编辑：
(gdb) backtrace
#0 0x00007ffff7aa6705 in new_do_write (fp=0x555555559690,
data=0x555555559920 "dth=.1]; ir_3; }n 3:se->ir_3 [style=invis];n 44:se->44:n ;n 44;n 44:sw->0:n ;n 0;n {node[style=invis, width=.1]; il_0; }n 0:sw->il_0 [style=invis];n 0:se->3:n ;n 3;n {node[style=invis, width"..., to_do=to_do@entry=4096) at fileops.c:441
#1 0x00007ffff7aa8509 in _IO_new_do_write (to_do=4096, data=<optimized out>, fp=<optimized out>) at fileops.c:430
#2 _IO_new_do_write (fp=<optimized out>, data=<optimized out>, to_do=4096) at fileops.c:430
#3 0x00007ffff7aa7a8f in _IO_new_file_xsputn (n=35, data=<optimized out>, f=0x555555559690) at libioP.h:839
#4 _IO_new_file_xsputn (f=0x555555559690, data=<optimized out>, n=35) at fileops.c:1204
#5 0x00007ffff7a7bb11 in _IO_vfprintf_internal (s=0x555555559690, format=0x555555556020 " {node[style=invis, width=.1]; il_%d; }n",
ap=ap@entry=0x7fffff7ff5e0) at ../libio/libioP.h:839
#6 0x00007ffff7a84534 in __fprintf (stream=<optimized out>, format=<optimized out>) at fprintf.c:32
#7 0x000055555555525f in print_tree (f=0x555555559690, root=0x555555559670) at tree2dot.h:12
#8 0x000055555555523f in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:10
#9 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#10 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#11 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#12 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#13 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#14 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#15 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#16 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#17 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#18 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#19 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#20 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#21 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#22 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#23 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#24 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#25 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#26 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#27 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
--Type <RET> for more, q to quit, c to continue without paging--c
#28 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#29 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
...
#261965 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#261966 0x00005555555552cf in print_tree (f=0x555555559690, root=0x5555555598e0) at tree2dot.h:20
#261967 0x0000555555555447 in tree2dot (root=0x5555555598e0, filename=0x55555555618f "avl") at tree2dot.h:40
#261968 0x0000555555555b0a in main () at avl.c:185
我不应该在树中创建任何循环，所以添加检查
因此更换
n->left = p->left;
n->right = p->right;
带有
if(p->left!=n)n->left = p->left;//no cycles in
else n->left = NULL;
if(p->right!=n)n->right = p->right;
else n->right = NULL;
似乎奏效了。