#include
#include
struct node {
int value;
node *lchild;
node *rchild;
};
node *find(node *head, int x)
{
if(x == head->value) return head;
node *pre;
while(head) {
if(x == head->value) return pre;
else if(x > head->value) {
pre = head;
head = head->rchild;
}
else if(x < head->value) {
pre = head;
head = head->lchild;
}
}
return NULL;
}
void insert(node *head, int x)
{
node *p = find(head, x);
if(p != NULL) return;
while(head) {
if(x > head->value) {
if(head->rchild == NULL) {
node *p = (node*)malloc(sizeof(node));
p->lchild = p->rchild = NULL;
p->value = x;
head->rchild = p;
return;
} else {
head = head->rchild;
}
} else {
if(head->lchild == NULL) {
node *p = (node*)malloc(sizeof(node));
p->lchild = p->rchild = NULL;
head->lchild = p;
p->value = x;
return;
} else {
head = head->lchild;
}
}
}
}
void del(node *&head, int x)
{
// printf("%d\n", x);
node *p = find(head, x);
if(p == NULL) return;
else if(p == head) {
if(p->rchild->lchild == NULL) {
head->rchild->lchild = head->lchild;
head = head->rchild;
free(p);
} else {
node *m = p->rchild->lchild;
while(m->lchild->lchild != NULL) {
m = m->lchild;
}
node *n = m->lchild;
m->lchild = n->rchild;
n->lchild = p->lchild;
n->rchild = p->rchild;
head = n;
free(p);
}
return;
}
node *q,*m,*n;
if(x > p->value) {
q = p->rchild;
if(q->rchild == NULL) {
p->rchild = q->lchild;
free(q);
}
else if(q->rchild->lchild == NULL) {
p->rchild = q->rchild;
p->rchild->lchild = q->lchild;
} else {
m = q->rchild->lchild;
while(m->lchild->lchild != NULL) {
m = m->lchild;
}
n = m->lchild;
m->lchild = n->rchild;
n->lchild = q->lchild;
n->rchild = q->rchild;
p->rchild = n;
free(q);
}
}
else {
q = p->lchild;
if(q->lchild == NULL) {
p->lchild = q->rchild;
free(q);
} else if(q->lchild->rchild == NULL) {
p->lchild = q->lchild;
p->lchild->rchild = q->rchild;
} else {
m = q->lchild->rchild;
while(m->rchild->rchild != NULL) {
m = m->rchild;
}
n = m->rchild;
m->rchild = n->lchild;
n->lchild = q->lchild;
n->rchild = q->rchild;
p->lchild = n;
free(q);
}
}
}
void inorder(node *root)
{
if(root != NULL) {
inorder(root->lchild);
printf("%d ", root->value);
inorder(root->rchild);
}
}
int depth(node *root)
{
int lcd,rcd;
if(root == NULL) return 0;
else {
lcd = depth(root->lchild);
rcd = depth(root->rchild);
if(lcd>rcd) return lcd+1;
else return rcd+1;
}
}
int main()
{
node *head = (node*)malloc(sizeof(node));
head->value = 55;
head->lchild = head->rchild = NULL;
for(int i=1; i<100; ++i) {
insert(head, i);
}
for(int i=54; i<=55; ++i) {
del(head, i);
}
int dep = depth(head);
printf("dep = %d\n", dep);
inorder(head);
return 0;
}
//带父节点的二叉搜索树的插入和删除
#include
#include
struct node {
int value;
node *lchild;
node *rchild;
node *parent;
};
node *find(node *head, int x)
{
if(head == NULL) return NULL;
while(head) {
if(x == head->value) return head;
else if(x > head->value) {
head = head->rchild;
}
else if(x < head->value) {
head = head->lchild;
}
}
return NULL;
}
void insert(node *head, int x)
{
node *p = find(head, x);
if(p != NULL) return;
while(head) {
if(x > head->value) {
if(head->rchild == NULL) {
node *p = (node*)malloc(sizeof(node));
p->lchild = p->rchild = NULL;
p->value = x;
p->parent = head;
head->rchild = p;
return;
} else {
head = head->rchild;
}
} else {
if(head->lchild == NULL) {
node *p = (node*)malloc(sizeof(node));
p->lchild = p->rchild = NULL;
p->value = x;
p->parent = head;
head->lchild = p;
return;
} else {
head = head->lchild;
}
}
}
}
void del(node *&head, int x)
{
node *p = find(head, x);
if(p == NULL) return;
else if(p == head) {
if(p->rchild == NULL) {
head = p->lchild;
free(p);
} else if(p->rchild->lchild == NULL) {
p->rchild->lchild = p->lchild;
if(p->lchild != NULL) p->lchild->parent = p->rchild;
head = p->rchild;
free(p);
} else {
node *q = p->rchild;
while(q->lchild != NULL) {
q = q->lchild;
}
q->parent->lchild = q->rchild;
if(q->rchild != NULL) q->rchild->parent = q->parent;
q->rchild = p->rchild;
if(p->rchild != NULL) p->rchild->parent = q->rchild;
q->lchild = p->lchild;
if(p->lchild != NULL) p->lchild->parent = q->lchild;
q->parent = p->parent;
p->parent->rchild = q;
head = q;
free(p);
}
return;
}
if(p == p->parent->rchild) {
if(p->rchild == NULL) {
p->parent->rchild = p->lchild;
if(p->lchild != NULL) p->lchild->parent = p->parent;
free(p);
} else if(p->rchild->lchild == NULL) {
p->rchild->lchild = p->lchild;
if(p->lchild != NULL) p->lchild->parent = p->rchild;
p->parent->rchild = p->rchild;
p->rchild->parent = p->parent;
free(p);
} else {
node *q = p->rchild;
while(q->lchild != NULL) {
q = q->lchild;
}
q->parent->lchild = q->rchild;
if(q->rchild != NULL) q->rchild->parent = q->parent;
q->rchild = p->rchild;
if(p->rchild != NULL) p->rchild->parent = q->rchild;
q->lchild = p->lchild;
if(p->lchild != NULL) p->lchild->parent = q->lchild;
q->parent = p->parent;
p->parent->rchild = q;
free(p);
}
} else {
if(p->lchild == NULL) {
p->parent->lchild = p->rchild;
p->rchild->parent = p->parent;
free(p);
} else if(p->lchild->rchild == NULL) {
p->lchild->rchild = p->rchild;
if(p->rchild != NULL) p->rchild->parent = p->lchild;
p->parent->lchild = p->lchild;
p->lchild->parent = p->parent;
free(p);
} else {
node *q = p->lchild;
while(q->rchild != NULL) {
q = q->rchild;
}
q->parent->rchild = q->lchild;
if(q->lchild != NULL) q->lchild->parent = q->parent;
q->rchild = p->rchild;
if(p->rchild != NULL) p->rchild->parent = q->rchild;
q->lchild = p->lchild;
if(p->lchild != NULL) p->lchild->parent = p->lchild;
q->parent = p->parent;
p->parent->lchild = q;
free(p);
}
}
}
void inorder(node *root)
{
if(root != NULL) {
inorder(root->lchild);
printf("%d ", root->value);
inorder(root->rchild);
}
}
int depth(node *root)
{
int lcd,rcd;
if(root == NULL) return 0;
else {
lcd = depth(root->lchild);
rcd = depth(root->rchild);
if(lcd>rcd) return lcd+1;
else return rcd+1;
}
}
int main()
{
node *head = (node*)malloc(sizeof(node));
head->value = 55;
head->lchild = head->rchild = NULL;
for(int i=1; i<100; ++i) {
insert(head, i);
}
for(int i=54; i<56; ++i) {
del(head, i);
}
int dep = depth(head);
printf("dep = %d\n", dep);
inorder(head);
return 0;
}
//在测试程序中，树的高度达到了54，这表明树非常的不平衡，普通二叉树在不断的插入和删除后会变得极其不平横，所以后面将会用到平衡二叉树。
//插入比较简单，删除要分几种情况：
1:删除节点为顶点节点，且没有右节点
2:删除节点为顶点节点，且删除节点的右节点的左节点为空
3:删除节点为顶点节点，且删除节点的右节点的左节点不为空
4:删除节点不为顶点节点，为父节点的右节点，且没有右节点
5:删除节点不为顶点节点，为父节点的右节点，且删除节点的右节点的左节点为空
6:删除节点不为顶点节点，为父节点的右节点，且删除节点的右节点的左节点不为空
...为父节点的左节点的情况类同
阅读(1754) | 评论(0) | 转发(0) |
