) + 1;
376 ? ? ? ? }
377 ? ? }
378 ? ? else{
379 ? ? ? ? return -1;
380 ? ? }
381 }
382?
383 static void tree_height(BTree *BT, BTNode *phead)
384 {//遍历求树中每个节点的高度
385 ? ? if(phead == NULL)
386 ? ? ? ? return;
387?
388 ? ? tree_node_height(BT, phead);
389 ? ? if(phead->lchild != NULL)
390 ? ? ? ? tree_node_height(BT, phead->lchild);
391 ? ? if(phead->rchild != NULL)
392 ? ? ? ? tree_node_height(BT, phead->rchild);
393 }
394?
395 static int max_height(int height1, int height2)
396 {//求两个高度的最大值
397 ? ? if(height1 > height2)
398 ? ? ? ? return height1;
399 ? ? else
400 ? ? ? ? return height2;
401 }
402?
403 static BTNode *singleRotateLL(BTree *BT, BTNode *phead)
404 {//不平衡情况为左左的单旋转操作
405 ? ? BTNode *temp;
406?
407 ? ? if(phead == NULL)
408 ? ? ? ? return 0;
409?
410 ? ? temp = phead->lchild;
411 ? ??
412 ? ? if(temp->rchild != NULL){
413 ? ? ? ? phead->lchild = temp->rchild;
414 ? ? ? ? phead->lchild->height = tree_node_height(BT, phead->lchild);
415 ? ? }
416 ? ? else
417 ? ? ? ? phead->lchild = NULL;
418?
419 ? ? temp->rchild = phead;
420 ? ? if(temp->rchild->data == BT->phead->data){
421 ? ? ? ? BT->phead = temp;
422 ? ? }
423 ? ? phead = temp;
424 ? ? temp->rchild->height = tree_node_height(BT, temp->rchild);
425 ? ? temp->height = tree_node_height(BT, temp);
426 ? ? phead->height = tree_node_height(BT, phead);
427 ? ??
428 ? ? return phead;
429 }
430?
431 static BTNode *singleRotateRR(BTree *BT, BTNode *phead)
432 {//不平衡情况为右右的单旋转操作
433 ? ? BTNode *temp;
434?
435 ? ? if(phead == NULL)
436 ? ? ? ? return 0;
437?
438 ? ? temp = phead->rchild;
439?
440 ? ? if(temp->lchild != NULL){
441 ? ? ? ? phead->rchild = temp->lchild;
442 ? ? ? ? phead->rchild->height = tree_node_height(BT, phead->rchild);
443 ? ? }
444 ? ? else
445 ? ? ? ? phead->rchild = NULL;
446?
447 ? ? temp->lchild = phead;
448 ? ? if(temp->lchild->data == BT->phead->data){
449 ? ? ? ? BT->phead = temp;
450 ? ? }
451 ? ? phead = temp;
452 ? ? temp->lchild->height = tree_node_height(BT, temp->lchild);
453 ? ? temp->height = tree_node_height(BT, temp);
454 ? ? phead->height = tree_node_height(BT, phead);
455?
456 ? ? return phead;
457 }
458 static BTNode *doubleRotateLR(BTree *BT, BTNode *phead)
459 {//不平衡情况为左右的双旋转操作
460 ? ? BTNode *temp;
461?
462 ? ? if(phead == NULL)
463 ? ? ? ? return 0;
464?
465 ? ? temp = phead->lchild; ? ?
466 ? ? phead->lchild = singleRotateRR(BT, temp);
467 ? ? temp = phead;
468 ? ? phead = singleRotateLL(BT, temp);
469?
470 ? ? return phead;
471 }
472?
473 static BTNode *doubleRotateRL(BTree *BT, BTNode *phead)
474 {//不平衡情况为右左的双旋转操作
475 ? ? BTNode *temp;
476?
477 ? ? if(phead == NULL)
478 ? ? ? ? return 0;
479?
480 ? ? temp = phead->rchild;
481 ? ? phead->rchild = singleRotateLL(BT, temp);
482 ? ? temp = phead;
483 ? ? phead = singleRotateRR(BT, temp);
484?
485 ? ? return phead;
486 }
487?
488 int main(int argc, char* argv[])
489 {//测试
490 ? ? BTree testtree;
491 ? ? testtree.init = tree_init;
492 ? ? testtree.init(&testtree, 9);
493?
494 ? ? testtree.add(&testtree, testtree.phead, 4);
495 ? ? testtree.add(&testtree, testtree.phead, 5);
496 ? ? testtree.add(&testtree, testtree.phead, 6);
497 ? ? testtree.add(&testtree, testtree.phead, 1);
498 ? ? testtree.add(&testtree, te