AVL樹的c語言實現

相關推薦

AVL樹的c語言實現

　　導語：C語言的設計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產生少量的機器碼以及不需要任何運行環境支持便能運行的編程語言。下面我們來看看AVL樹的c語言實現，希望對大家有所幫助。

　　AVL樹的c語言實現：在計算機科學中，AVL樹是最先發明的自平衡二叉查找樹。在AVL樹中任何節點的兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是O(log n)。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。

　　1.節點

　　(1)節點的定義

typedef int KeyType;          
typedef struct AvlNode          
{          
   KeyType key;     //數據          
   AvlNode *leftchild;    //左孩子          
   AvlNode *rightchild;   //右孩子          
   AvlNode *parent;    //雙親結點          
   int balance;           //平衡因子          
}AvlNode,*AvlTree;          

　　(2)結點的創建

AvlNode *BuyNode()          
{          
   AvlNode *p =(AvlNode *)malloc(sizeof(AvlNode));          
   if( p != NULL)          
   {          
       p->leftchild = NULL;          
       p->rightchild = NULL;          
       p->parent = NULL;          
       p->balance = 0;          
   }          
   return p;          
}          

　　2.旋轉

　　如果在AVL樹中進行插入或刪除節點后，可能導致AVL樹失去平衡。這種失去平衡的可以概括為4種姿態：左單旋轉，右單旋轉，左平衡，右平衡。(1)左單旋轉：也叫左左旋轉。

【AVL樹的c語言實現】相關文章：

C語言程序的實現09-27

C語言的HashTable簡單實現10-12