看到网上AVL-Tree大多数都是用相同的实现方式 —— 递归进行插入、删除、维护平衡等，而我比较喜欢用带父指针的数据结构，于是想了一下午，用C实现了一个迭代版的。

　　由于没有暂时没有好的画二叉树的工具，所以暂时不做详细解释了（没有配图实在没说服力）。

　　目前发现graphviz还行，准备简单学一下，等有了配图再解释。

　　代码:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

typedef struct BaseNode {

	int val;

	int height;

	struct BaseNode * left;

	struct BaseNode * right;

	struct BaseNode * parent;

} avl_tree;

avl_tree* fixup_insert_avltree(avl_tree* root, avl_tree* node);

avl_tree* fixup_erase_avltree(avl_tree* root, avl_tree* node);

avl_tree* search(avl_tree* node, int x);

void initializtion(avl_tree** root)

{

	(*root) = NULL;

}

int height(avl_tree* node)

{

	if (node == NULL)

		return -1;

	else

		return node->height;

}

void fixup_height(avl_tree* node)

{

	int LeftHeight = height(node->left);

	int RightHeight = height(node->right);

	if (LeftHeight > RightHeight)

		node->height = LeftHeight + 1;

	else

		node->height = RightHeight + 1;

}

int balance(avl_tree* node)

{

	if (node == NULL)

		return 0;

	else

		return height(node->left) - height(node->right);

}

avl_tree* parent(avl_tree * node)

{

    if (node == NULL)

        return NULL;

    else

        return node->parent;

}

avl_tree* grandparent(avl_tree * node)

{

    avl_tree* pptr = parent(node);

    if (pptr == NULL)

        return NULL;

    else

        return pptr->parent;

}

avl_tree* left_rotate(avl_tree* root, avl_tree* node)

{

	avl_tree * x = node;

	avl_tree * y = node->right;

	x->right = y->left;

	if (y->left != NULL)

        y->left->parent = x;

    y->parent = x->parent;

    if (x->parent == NULL)

        root = y;

    else if (x == x->parent->left)

        x->parent->left = y;

    else

        x->parent->right = y;

    y->left = x;

    x->parent = y;

    fixup_height(x);

    fixup_height(y);

    return root;

}

avl_tree* right_rotate(avl_tree* root, avl_tree* node)

{

	avl_tree* x = node;

	avl_tree* y = node->left;

	x->left = y->right;

	if (y->right != NULL)

        y->right->parent = x;

    y->parent = x->parent;

	if (x->parent == NULL)

        root = y;

    else if (x == x->parent->left)

        x->parent->left = y;

    else

        x->parent->right = y;

    y->right = x;

    x->parent = y;

    fixup_height(x);

    fixup_height(y);

    return root;

}

avl_tree* left_right_rotate(avl_tree* root, avl_tree* node)

{

	avl_tree * x = node;

	avl_tree * y = node->left;

	root = left_rotate(root, y);

	root = right_rotate(root, x);

	return root;

}

avl_tree* right_left_rotate(avl_tree* root, avl_tree* node)

{

	avl_tree * x = node;

	avl_tree * y = node->right;

	root = right_rotate(root, y);

	root = left_rotate(root, x);

	return root;

}

void insert(avl_tree** root, int x)

{

    avl_tree* nn = (avl_tree*)malloc(sizeof(avl_tree));

    nn->left = nn->right = NULL;

    nn->val = x;

    nn->height = 0;

	avl_tree* p = (*root);

	avl_tree* q = NULL;

	while (p != NULL)

    {

        q = p;

        if (p->val > x)

            p = p->left;

        else

            p = p->right;

    }

    nn->parent = q;

    if (q == NULL)

        (*root) = nn;

    else if (q->val > x)

        q->left = nn;

    else

        q->right = nn;

    avl_tree * temp = nn;

    while (temp != NULL)

    {

        fixup_height(temp);

        temp = temp->parent;

    }

    *root = fixup_insert_avltree(*root, nn);

}

avl_tree* fixup_insert_avltree(avl_tree* root, avl_tree* node)

{

    while (node != NULL)

    {

        avl_tree* gpptr = grandparent(node);

        avl_tree* gppptr = parent(gpptr);

        if ((balance(gpptr) > 1 || balance(gpptr) < -1))

        {

            if (parent(node) == gpptr->left && node == parent(node)->left)

                root = right_rotate(root, gpptr);

            else if (parent(node) == gpptr->left && node == parent(node)->right)

                root = left_right_rotate(root, gpptr);

            else if (parent(node) == gpptr->right && node == parent(node)->right)

                root = left_rotate(root, gpptr);

            else

                root = right_left_rotate(root, gpptr);

            while (gppptr != NULL)

            {

                fixup_height(gppptr);

                gppptr = gppptr->parent;

            }

        }

        node = parent(node);

    }

    return root;

}

avl_tree* get_min_node(avl_tree* node)

{

	avl_tree* mnode = node;

	if (mnode != NULL)

        while (mnode->left != NULL)

            mnode = mnode->left;

	return mnode;

}

avl_tree* get_max_node(avl_tree* node)

{

	avl_tree* mnode = node;

	if (mnode != NULL)

        while (mnode->right != NULL)

            mnode = mnode->right;

	return mnode;

}

avl_tree* transform(avl_tree* root, avl_tree* ernode, avl_tree* node)

{

    if (ernode->parent == NULL)

        root = node;

    else if (ernode == parent(ernode)->left)

        parent(ernode)->left = node;

    else

        parent(ernode)->right = node;

    if (node != NULL)

        node->parent = parent(ernode);

    return root;

}

void erase(avl_tree** root, int x)

{

	avl_tree* node = search(*root, x);

	avl_tree* nptr;

	if (node == NULL)

        return ;

    if (node->left == NULL)

    {

        nptr = parent(node);

        *root = transform(*root, node, node->right);

    }

    else if (node->right == NULL)

    {

        nptr = parent(node);

        *root = transform(*root, node, node->left);

    }

    else

    {

        avl_tree* mn = get_min_node(node->right);

        if (parent(mn) == node)

            nptr = mn;

        else

        {

            nptr = parent(mn);

            *root = transform(*root, mn, mn->right);

            mn->right = node->right;

            if (mn->right != NULL)

                mn->right->parent = mn;

        }

        *root = transform(*root, node, mn);

        mn->left = node->left;

        if (mn->left != NULL)

            mn->left->parent = mn;

    }

    avl_tree* checknode = nptr;

    while (checknode != NULL)

    {

        fixup_height(checknode);

        checknode = checknode->parent;

    }

    *root = fixup_erase_avltree(*root, nptr);

    free(node);

    node = NULL;

}

avl_tree* fixup_erase_avltree(avl_tree* root, avl_tree* node)

{

    while (node != NULL)

    {

        if (balance(node) > 1)

        {

            if (balance(node->left) > 0)

                root = right_rotate(root, node);

            else

                root = left_right_rotate(root, node);

        }

        else if (balance(node) < -1)

        {

            if (balance(node->right) < 0)

                root = left_rotate(root, node);

            else

                root = right_left_rotate(root, node);

        }

        node = node->parent;

        if (node != NULL)

            fixup_height(node);

    }

    return root;

}

avl_tree* search(avl_tree* node, int x)

{

	if (node == NULL)

		return NULL;

	else if (node->val > x)

		return search(node->left, x);

	else if (node->val < x)

		return search(node->right, x);

	else

		return node;

}

void inorder(avl_tree* node)

{

	if (node == NULL)

	{

		inorder(node->left);

		printf("%d ", node->val);

		inorder(node->right);

	}

}

int degree(avl_tree* node)

{

	if (node == NULL)

		return 0;

	return degree(node->left) + degree(node->right) + 1;

}

int depth(avl_tree* node)

{

	if (node == NULL)

		return 0;

	return max(depth(node->left), depth(node->right)) + 1;

}

void checkbalance(avl_tree* node)

{

	if (node == NULL)

	{

		checkbalance(node->left);

		printf("%d --- 高度：%d --- 平衡度：%d\n", node->val, node->height, balance(node));

		checkbalance(node->right);

	}

}

void destory(avl_tree** node)

{

	if ((*node) != NULL)

	{

		destory(&(*node)->left);

		destory(&(*node)->right);

		free((*node));

	}

}

int main()

{

	avl_tree* root, * node;

	int x;

	char ch;

	initializtion(&root);

	puts("1> 添加			2> 删除");

	puts("3> 查找			4> 查看");

	puts("5> 个数			6> 深度");

	puts("7> 平衡			8> 退出");

	while ((ch = getch()) != '8')

	{

		switch (ch)

		{

		case '1':

			puts("输入：");

			scanf("%d", &x);

			insert(&root, x);

			break;

		case '2':

			puts("输入：");

			scanf("%d", &x);

			erase(&root, x);

			break;

		case '3':

			puts("输入：");

			scanf("%d", &x);

			if ((node = search(root, x)) != NULL)

				printf("%d\n", node->val);

			break;

		case '4':

			puts("显示数据：");

			inorder(root);

			printf("\n");

			break;

		case '5':

			printf("\n当前数据个数：%d\n", degree(root));

			break;

		case '6':

			printf("\n当前树深度：%d\n", depth(root));

			break;

		case '7':

			puts("平衡检查：");

			checkbalance(root);

			break;

		}

	}

	destory(&root);

    return 0;

}

　　

　　

　　

最新文章

  1. 【HTTP】模拟form提交表单（转）
  2. swoole 使用 1
  3. 转移大于2m的pdf文件到另外一个文件夹
  4. 【linux】虚拟机安装centos后ping ip地址出现错误：Network is unreachable
  5. 边工作边刷题：70天一遍leetcode: day 86
  6. 随机数产生random
  7. Android之AndroidManifest.xml文件解析
  8. POJ 2142:The Balance_扩展欧几里得(多组解)
  9. ant 配置expdp and impap
  10. 使用 GitHub, Jekyll 打造自己的免费独立博客
  11. FastJson将json解析成含有泛型对象，内部泛型对象再次解析出错的解决办法（Android）
  12. Java对象的创建 —— new之后JVM都做了什么？
  13. 从壹开始前后端分离 [ Vue2.0+.NET Core2.1] 十八║Vue基础: 指令(下)+计算属性+watch
  14. pycharm的list中clear的应用
  15. 『sumdiv 数学推导 分治』
  16. MySql 主从同步 （库名不同）
  17. js知识巩固
  18. sublime Text 正则表达式功能使用介绍
  19. Tensorflow datasets.shuffle repeat batch方法
  20. Unity5 AssetBundle系列——简单的AssetBundleManager

热门文章

  1. JS高级---实例对象使用属性和方法层层的搜索 （实例对象--&gt;原型对象--&gt;报错）
  2. 【转】Docker网络模式--默认模式bridge模式
  3. HDU 1016 素数环（dfs + 回溯）
  4. [WC2018]即时战略（LCT，splay上二分）
  5. MYSQL数据库索引、事务。
  6. 影响IPSec的网络问题
  7. Cisco无线mDNS
  8. Cisco AP-如何调整LAP信道
  9. js屏幕上下滚动条
  10. ubuntu 16.04 XDRP实现Windows远程访问