Chinaunix首页 | 论坛 | 博客
  • 博客访问: 245193
  • 博文数量: 49
  • 博客积分: 110
  • 博客等级: 民兵
  • 技术积分: 510
  • 用 户 组: 普通用户
  • 注册时间: 2013-01-13 00:59
个人简介

make it run,make it better,make it fast. https://github.com/liulanghaitun

文章分类

全部博文(49)

文章存档

2023年(1)

2022年(2)

2020年(4)

2019年(4)

2017年(15)

2016年(3)

2014年(3)

2013年(14)

分类: LINUX

2017-10-29 21:18:47


点击(此处)折叠或打开

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

  3. #define height(avl_node) (avl_node ? avl_node->avl_height : -1)
  4. #define max(left,right) (left > right ? left : right)

  5. typedef struct avl_tree_node {
  6.     int avl_data;
  7.     struct avl_tree_node *avl_left;
  8.     struct avl_tree_node *avl_right;
  9.     struct avl_tree_node *avl_parent;
  10.     int avl_height;
  11. } avl_tree_node_t;

  12. avl_tree_node_t* avl_find_node(avl_tree_node_t *root, int data)
  13. {
  14.     if (root == NULL) return NULL;
  15.     if (data < root->avl_data)
  16.         return avl_find_node(root->avl_left, data);
  17.     else if (data > root->avl_data)
  18.         return avl_find_node(root->avl_right, data);
  19.     else
  20.         return root;
  21. }

  22. void avl_update_height(avl_tree_node_t *root)
  23. {
  24.     root->avl_height = 1 + max(height(root->avl_left), height(root->avl_right));
  25. }

  26. avl_tree_node_t* avl_rotate_right(avl_tree_node_t *root)
  27. {
  28.     avl_tree_node_t *left_root = root->avl_left;
  29.     if (root->avl_parent) {
  30.         if (root->avl_parent->avl_left == root) root->avl_parent->avl_left = left_root;
  31.         else root->avl_parent->avl_right = left_root;
  32.     }
  33.     left_root->avl_parent = root->avl_parent;
  34.     root->avl_left = left_root->avl_right;
  35.     if (root->avl_left) root->avl_left->avl_parent = root;
  36.     left_root->avl_right = root;
  37.     root->avl_parent = left_root;

  38.     avl_update_height(root);
  39.     avl_update_height(left_root);
  40.     return left_root;
  41. }

  42. avl_tree_node_t* avl_rotate_left(avl_tree_node_t *root)
  43. {
  44.     avl_tree_node_t *right_root = root->avl_right;
  45.     if (root->avl_parent) {
  46.         if (root->avl_parent->avl_right == root) root->avl_parent->avl_right = right_root;
  47.         else root->avl_parent->avl_left = right_root;
  48.     }
  49.     right_root->avl_parent = root->avl_parent;
  50.     root->avl_right = right_root->avl_left;
  51.     if (root->avl_right) root->avl_right->avl_parent = root;
  52.     right_root->avl_left = root;
  53.     root->avl_parent = right_root;

  54.     avl_update_height(root);
  55.     avl_update_height(right_root);
  56.     return right_root;
  57. }

  58. avl_tree_node_t* avl_create_node(int data, avl_tree_node_t *parent)
  59. {
  60.     avl_tree_node_t *avl_node = (avl_tree_node_t *)malloc(sizeof(avl_tree_node_t));
  61.     if(avl_node) {
  62.         avl_node->avl_data = data;
  63.         avl_node->avl_parent = parent;
  64.         avl_node->avl_height = 0;
  65.         avl_node->avl_left = NULL;
  66.         avl_node->avl_right = NULL;
  67.     }
  68.     return avl_node;
  69. }

  70. avl_tree_node_t* avl_balance(avl_tree_node_t *root)
  71. {
  72.     if (height(root->avl_left) - height(root->avl_right) > 1) {
  73.         if (height(root->avl_left->avl_left) > height(root->avl_left->avl_right)) {
  74.             root = avl_rotate_right(root);
  75.         } else {
  76.             avl_rotate_left(root->avl_left);
  77.             root = avl_rotate_right(root);
  78.         }
  79.     } else if (height(root->avl_right) - height(root->avl_left) > 1) {
  80.         if (height(root->avl_right->avl_right) > height(root->avl_right->avl_left)) {
  81.             root = avl_rotate_left(root);
  82.         } else {
  83.             avl_rotate_right(root->avl_right);
  84.             root = avl_rotate_left(root);
  85.         }
  86.     }
  87.     return root;
  88. }

  89. avl_tree_node_t* avl_find_max_node(avl_tree_node_t* root)
  90. {
  91.     if(root)
  92.     {
  93.         if(root->avl_right)
  94.         {
  95.             return avl_find_max_node(root->avl_right);
  96.         }
  97.     }
  98.     return root;
  99. }

  100. avl_tree_node_t* avl_find_min_node(avl_tree_node_t* root)
  101. {
  102.     if(root)
  103.     {
  104.         if(root->avl_left)
  105.         {
  106.             return avl_find_min_node(root->avl_left);
  107.         }
  108.     }
  109.     return root;
  110. }

  111. avl_tree_node_t* avl_delete_node(avl_tree_node_t* root, int data)
  112. {
  113.     avl_tree_node_t* current = NULL;
  114.     if(root)
  115.     {
  116.         if(data < root->avl_data)
  117.         {
  118.             root->avl_left = avl_delete_node(root->avl_left,data);
  119.         }else if(data > root->avl_data)
  120.         {
  121.             root->avl_right = avl_delete_node(root->avl_right,data);
  122.         }else{
  123.             if(root->avl_right)
  124.             {
  125.                 current = avl_find_min_node(root->avl_right);
  126.                 root->avl_data = current->avl_data;
  127.                 root->avl_right = avl_delete_node(root->avl_right,root->avl_data);
  128.             }else if(root->avl_left)
  129.             {
  130.                 current = avl_find_max_node(root->avl_left);
  131.                 root->avl_data = current->avl_data;
  132.                 root->avl_left = avl_delete_node(root->avl_left,root->avl_data);
  133.             }else{
  134.                 free(root);
  135.                 root = NULL;
  136.                 return NULL;
  137.             }
  138.         }
  139.        avl_update_height(root);
  140.        root = avl_balance(root);
  141.     }
  142.     return root;
  143. }

  144. avl_tree_node_t* avl_insert_node(avl_tree_node_t* root, int data)
  145. {
  146.     avl_tree_node_t* current = root;
  147.     if(current) {
  148.         while (current->avl_data != data) {
  149.             if (data < current->avl_data) {
  150.                 if (current->avl_left) current = current->avl_left;
  151.                 else {
  152.                     current->avl_left = avl_create_node(data, current);
  153.                     current = current->avl_left;
  154.                 }
  155.             } else if (data > current->avl_data) {
  156.                 if (current->avl_right) current = current->avl_right;
  157.                 else {
  158.                     current->avl_right = avl_create_node(data, current);
  159.                     current = current->avl_right;
  160.                 }
  161.             } else return root;
  162.         }

  163.         do {
  164.             current = current->avl_parent;
  165.             avl_update_height(current);
  166.             current = avl_balance(current);
  167.         } while (current->avl_parent);
  168.     }else{
  169.         current = avl_create_node(data,NULL);
  170.     }
  171.     return current;
  172. }

  173. void avl_print_tree_indent(avl_tree_node_t *node, int indent)
  174. {
  175.     int ix;
  176.     for (ix = 0; ix < indent; ix++) printf(" ");
  177.     if (!node) printf("Empty child\n");
  178.     else {
  179.         printf("node: %d; height: %d\n", node->avl_data, node->avl_height);
  180.         avl_print_tree_indent(node->avl_left, indent + 4);
  181.         avl_print_tree_indent(node->avl_right, indent + 4);
  182.     }
  183. }

  184. void avl_print_tree(avl_tree_node_t* avl_tree, int data , int direction)
  185. {
  186.     if(avl_tree) {
  187.         if(direction==0)
  188.             printf("%2d is root\n", avl_tree->avl_data);
  189.         else
  190.             printf("%2d is %2d's %6s child\n", avl_tree->avl_data, data, direction==1?"right" : "left");

  191.         avl_print_tree(avl_tree->avl_left, avl_tree->avl_data, -1);
  192.         avl_print_tree(avl_tree->avl_right,avl_tree->avl_data, 1);
  193.     }
  194. }

  195. void avl_print_order(avl_tree_node_t *node)
  196. {
  197.     if(node) {
  198.         avl_print_order(node->avl_left);
  199.         printf("(%d,%d) ",node->avl_data,node->avl_height);
  200.         avl_print_order(node->avl_right);
  201.     }
  202. }

  203. void avl_delete_tree(avl_tree_node_t* root)
  204. {
  205.     if(root) {
  206.         avl_delete_tree(root->avl_left);
  207.         avl_delete_tree(root->avl_right);
  208.         free(root);
  209.     }
  210. }

  211. int main(int argc, char *argv[])
  212. {
  213.     static int data[]= {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
  214.     avl_tree_node_t* root = NULL;
  215.     int index = 0;
  216.     for(; index < sizeof(data)/sizeof(data[0]); index++) {
  217.         root = avl_insert_node(root,data[index]);
  218.     }
  219.     avl_print_tree_indent(root, 0);
  220.     avl_print_order(root);
  221.     printf("\r\n");
  222.     avl_print_tree(root,root->avl_data,0);
  223.     avl_tree_node_t* find_node = avl_find_node(root,12);
  224.     printf(find_node?"find success!\r\n":"find failed!\r\n");
  225.     printf("max_value==%d\r\n",avl_find_max_node(root)->avl_data);
  226.     printf("min_value==%d\r\n",avl_find_min_node(root)->avl_data);
  227.     avl_delete_node(root,8);
  228.     avl_print_order(root);
  229.     printf("\r\n");
  230.     avl_print_tree(root,root->avl_data,0);
  231.     printf("\r\n");
  232.     avl_delete_tree(root);
  233.     return 0;
  234. }
参考链接:

http://www.cnblogs.com/skywang12345/p/3576969.html
阅读(1905) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~