[小明学算法]8.二叉平衡树

参考:http://www.cppblog.com/cxiaojia/archive/2014/03/02/187776.html
  1 #include<iostream>
  2 using namespace std;
  3 
  4 template<class T>
  5 class BTreeNode
  6 {
  7 public:
  8     //值
  9     T Data;
 10     //高度
 11     int Height;
 12     //左右节点
 13     BTreeNode* Left;
 14     BTreeNode* Right;
 15 };
 16 
 17 template<class T>
 18 class BTree
 19 {
 20 
 21 public:
 22     //构造
 23     BTree() :Root(NULL){};
 24     //插入
 25     void Insert(BTreeNode<T>* &node, T data);
 26     //查找
 27     void Search(T data);
 28     //删除
 29     //TODO
 30     //中序遍历
 31     void Show(BTreeNode<T> *node);
 32     void Show1(BTreeNode<T> *node);
 33     //根节点
 34     BTreeNode<T>* Root;
 35 private:
 36 
 37     //左旋
 38     BTreeNode<T>* RotateLeft(BTreeNode<T>* node);
 39     BTreeNode<T>* DoubleRotateLeft(BTreeNode<T>* node);
 40     //右旋
 41     BTreeNode<T>* RotateRight(BTreeNode<T>* node);
 42     BTreeNode<T>* DoubleRotateRight(BTreeNode<T>* node);
 43     //高度
 44     int GetHeight(BTreeNode<T>* node);
 45     //大值
 46     int Max(int a, int b)
 47     {
 48         return a > b ? a : b;
 49     }
 50 };
 51 template<class T>
 52 void BTree<T>::Show(BTreeNode<T> *node)
 53 {
 54     if (node == NULL)
 55         return;
 56     
 57     printf("Data:%d Height:%d
", node->Data, node->Height);
 58     Show(node->Left);
 59     Show(node->Right);
 60 }
 61 template<class T>
 62 void BTree<T>::Show1(BTreeNode<T> *node)
 63 {
 64     if (node == NULL)
 65         return;
 66     Show1(node->Left);
 67     printf("Data:%d Height:%d
", node->Data, node->Height);
 68     
 69     Show1(node->Right);
 70 }
 71 
 72 template<class T>
 73 void BTree<T>::Insert(BTreeNode<T>* &node, T data)
 74 {
 75     
 76     if (node == NULL)
 77     {
 78         node = new BTreeNode<T>();
 79         node->Data = data;
 80         node->Height = 1;
 81         return ;
 82         
 83     }
 84 
 85     //如果已经插入过了
 86     if (node->Data == data)
 87     {
 88         return;
 89     }
 90 
 91     if (node->Data > data)
 92     {
 93         //插入到左侧了
 94         Insert(node->Left, data);
 95         if (GetHeight(node->Left) - GetHeight(node->Right) > 1)
 96         {
 97             //左侧的左侧 即LL
 98             if (data < node->Left->Data)
 99                 node = RotateRight(node);
100             else// 左侧的右侧 LR
101                 node = DoubleRotateRight(node);
102         }
103     }
104 
105     if (node->Data < data)
106     {
107         Insert(node->Right, data);
108         //插入后,若右侧不平衡了
109         if (GetHeight(node->Right) - GetHeight(node->Left)>1)
110         {
111             //RR
112             if (data > node->Right->Data)
113                 node = RotateLeft(node);
114             else
115                 node = DoubleRotateLeft(node);
116         }
117     }
118     if (node->Left!=NULL)
119     node->Left->Height = Max(GetHeight(node->Left->Left), GetHeight(node->Left->Right)) + 1;
120     if (node->Right != NULL)
121     node->Right->Height = Max(GetHeight(node->Right->Left), GetHeight(node->Right->Right)) + 1;
122     node->Height = Max(GetHeight(node->Left), GetHeight(node->Right))+1;
123 }
124 
125 template<class T>
126 int BTree<T>::GetHeight(BTreeNode<T>* node)
127 {
128     if (node != NULL)
129         return node->Height;
130 
131     return 0;
132 }
133 
134 template<class T>
135 BTreeNode<T>* BTree<T>::RotateLeft(BTreeNode<T>* node)
136 {
137     BTreeNode<T>* rightChild = node->Right;
138     if (rightChild != NULL)
139     node->Right = rightChild->Left;
140     rightChild->Left = node;
141 
142     return rightChild;
143 }
144 
145 template<class T>
146 BTreeNode<T>* BTree<T>::DoubleRotateLeft(BTreeNode<T>* node)
147 {
148     //先右旋子节点
149     return RotateLeft(RotateRight(node->Right));
150 }
151 
152 template<class T>
153 BTreeNode<T>* BTree<T>::RotateRight(BTreeNode<T>* node)
154 {
155     BTreeNode<T>* leftChild = node->Left;
156 
157     if (leftChild!=NULL)
158     node->Left = leftChild->Right;
159     leftChild->Right = node;
160 
161     return leftChild;
162 }
163 
164 template<class T>
165 BTreeNode<T>* BTree<T>::DoubleRotateRight(BTreeNode<T>* node)
166 {    
167     return RotateRight(RotateLeft(node->Left));
168 }
169 
170 
171 
172 void main()
173 {
174     BTree<int> tree;
175     for (int i = 0; i < 13; i++)
176     {
177         tree.Insert(tree.Root, rand()%100);
178     }
179 
180     tree.Show(tree.Root);
181 
182     int a;
183     cin >> a;
184 }
View Code