[数据结构与算法]平衡二叉树实现

3.用二叉树被每个结点的空指针引出一个虚结点,其值为特定值#,处理二叉树为本来二叉树的恢弘二叉树,扩展二叉树做到一个遍历序列确定一棵二叉树

出于程序太长,分成了几局部,后面附上源码。

2.面前先后遍历:先走访根结点,前序遍历左子树,前序遍历右子树;中左右

 

  

 1 package tree.avl;
 2 
 3 import java.util.Iterator;
 4 import java.util.Random;
 5 
 6 public class AVLTreeTest {
 7     public static void main(String[] args) {
 8         AVLTree myTree = new AVLTree();
 9         Random random = new Random();
10         System.out.print("随机产生的节点为:");
11         int num = 0;
12         //直到树的节点数为n止
13         while (myTree.size() < 10) {
14             num = new Integer(random.nextInt(100));
15             myTree.add(num);
16             System.out.print(num + " ");
17         }
18         System.out.println("");
19         if (myTree.isAVL()) {
20             System.out.println("这棵平衡二叉树的总节点数:" + myTree.size());
21             System.out.println("这棵平衡二叉树的高度是:" + myTree.height());
22             System.out.println("在树中查找 " + num + " 节点:"
23                     + myTree.contains(new Integer(num)));
24             System.out.println("在树中查找 100 节点:" + myTree.contains(new Integer(100)));
25             System.out.print("中序遍历:");
26             Iterator itr = myTree.iterator();
27             while (itr.hasNext()) {
28                 System.out.print(itr.next() + " ");
29             }
30             System.out.println("");
31 
32             myTree.remove(num);
33             System.out.print("删除节点 " + num + " 后遍历:");
34             itr = myTree.iterator();
35             while (itr.hasNext()) {
36                 System.out.print(itr.next() + " ");
37             }
38             System.out.println("");
39 
40             System.out.println("使用迭代器删除所有节点");
41             itr = myTree.iterator();
42             while (itr.hasNext()) {
43                 itr.next();
44                 itr.remove();
45             }
46             System.out.println("删除后树的总节点数:" + myTree.size());
47         } else {
48             System.out.println("failure");
49         }
50     }
51 }

1.使用递归的规律,只不过当原先打印结点的地方,改成为了转移结点,给结点赋值的操作
if(ch==’#’){*T=NULL;}else{malloc();(*T)->data=ch;createFunc((*T)->lchild);createFunc((*T)->rchild);}

  1     /**
  2      * 删除节点后平衡调整实现
  3      * 
  4      * @param elem 被删除节点的数据域
  5      * @param ancestor 被删除节点的祖先节点,从父节点向上迭代
  6      */
  7     protected void fixAfterDeletion(E elem, Entry<E> ancestor) {
  8 
  9         boolean heightHasDecreased = true;//树的高度是否还需要减小
 10 
 11         /*
 12          * 1、如果删除的是根节点,则ancestor为空,此时不需调整了,直接退出
 13          * 2、如果删除的不是根节点,且根节点都已调整,则退出
 14          * 3、如果删除的不是根节点,且树的高度不需再减小(heightHasDecreased为false),退出
 15          */
 16         while (ancestor != null && heightHasDecreased) {
 17 
 18             int comp = elem.compareTo(ancestor.elem);
 19 
 20             /*
 21              * 当要删除的节点有左右子树时,comp就会等于0,比如下面要删除33这个节点,删除方法deleteEntry
 22              * 会用36替换掉33节点中的数据的elem,删除后会调用fixAfterDeletion(p.elem, p.parent)方
 23              * 法来调整平衡因子,p又是指向的36,所以p.elem与p.parent.elem是相等的,都是36
 24              * 
 25              *            82
 26              *           /L\
 27              *         42   95
 28              *        /=\   R\
 29              *       33 48   96
 30              *      /=\  /=\
 31              *     29 36 43 75
 32              */
 33 
 34             //从ancestor的右子树中删除节点
 35             if (comp >= 0) {
 36                 // ancestor 的平衡因子为 '='
 37                 if (ancestor.balanceFactor == '=') {
 38 
 39                     /* 删除15       调整因子
 40                      *      20       →           20
 41                      *      /L\                  /L\
 42                      *   → 10 50                10 50
 43                      *     /=\                  /L
 44                      *    5  15                5
 45                      */
 46                     ancestor.balanceFactor = 'L';
 47                     heightHasDecreased = false;
 48 
 49                 } // ancestor 的平衡因子为 'R'
 50                 else if (ancestor.balanceFactor == 'R') {
 51                     /* 删除15       调整因子                    下次循环调整20的因子
 52                      *      20       →         → 20 ← ancestor   → ...
 53                      *      /L\                  /L\
 54                      *   → 10 50                10 50
 55                      *     /R\ R\               /=\ R\
 56                      *    5  15 60              5 18 60
 57                      *        R\
 58                      *         18
 59                      */
 60                     ancestor.balanceFactor = '=';
 61                     ancestor = ancestor.parent;
 62 
 63                 }// ancestor 的平衡因子为 'L'
 64                 else if (ancestor.balanceFactor == 'L') {
 65                     // ancestor 的左子节点平衡因子为 '='
 66                     if (ancestor.left.balanceFactor == '=') {
 67 
 68                         /* 删除60       调整因子              绕50右旋
 69                          *      20       →     → 20         →        20
 70                          *      /R\              / \                 /R\
 71                          *     10 50 ← ancestor 10 50 ←             10 45
 72                          *     /L /L\           /  /L\              /L /R\
 73                          *    5  45 60         5  45 60            5  35 50 ← 
 74                          *      /=\              /R\                     /L
 75                          *     35 48            35 48                   48
 76                          */
 77                         ancestor.left.balanceFactor = 'R';
 78                         ancestor.balanceFactor = 'L';
 79                         rotateRight(ancestor);
 80                         heightHasDecreased = false;
 81 
 82                     }// ancestor 的左子节点平衡因子为 'L' 
 83                     else if (ancestor.left.balanceFactor == 'L') {
 84 
 85                         /* 删除60       调整因子           绕50右旋   下次循环调整20的因子
 86                          *      20       →     → 20     →    20 ← p     → ...
 87                          *      /R\              / \         /R\
 88                          *     10 50 ← ancestor 10 50 ←     10 45
 89                          *     /L /L\           /  /=\      /L /=\
 90                          *    5  45 60         5  45 60    5  35 50 ← ancestor
 91                          *      /L               /=              =
 92                          *     35               35                      
 93                          */
 94                         Entry<E> p = ancestor.parent;
 95                         ancestor.balanceFactor = '=';
 96                         ancestor.left.balanceFactor = '=';
 97                         rotateRight(ancestor);
 98                         ancestor = p;
 99 
100                     } // ancestor 的左子节点平衡因子为 'R'
101                     else if (ancestor.left.balanceFactor == 'R') {
102 
103                         Entry<E> p = ancestor.parent;
104 
105                         // ancestor 的左子节点的右子节点的平衡因子为 'L'
106                         if (ancestor.left.right.balanceFactor == 'L') {
107 
108                             /* 删除60        调整因子               
109                              *      20        →       20             
110                              *      /R\               / \
111                              *    10   50 ← ancestor 10  50 ← ancestor
112                              *    /L\   /L\          / \  /R\
113                              *   5  12 45 60        5  12 45 70
114                              *  /L    /R\  R\      /     /=\  
115                              * 3     42 48  70    3     42 48  
116                              *          /L                 /= 
117                              *         46                 46
118                              *         
119                              *  绕45左旋         绕50右旋           下次循环调整20的因子
120                              *    →     20       →         20 ← p      → ...
121                              *          /R\                /R\
122                              *         10  50 ←          10   48
123                              *         /L\  /R\          /L\   /=\
124                              *        5 12 48 70        5  12 45 50 ← ancestor
125                              *       /L   /=           /L    /=\  R\
126                              *      3    45           3     42 46  70
127                              *          /=\
128                              *         42 46
129                              */
130                             ancestor.balanceFactor = 'R';
131                             ancestor.left.balanceFactor = '=';
132 
133                         }// ancestor 的左子节点的右子节点的平衡因子为 'R' 
134                         else if (ancestor.left.right.balanceFactor == 'R') {
135 
136                             /* 删除60        调整因子               
137                              *      20        →       20             
138                              *      /R\               / \
139                              *    10   50 ← ancestor 10  50 ← 
140                              *    /L\   /L\          / \  /=\
141                              *   5  12 45 60        5  12 45 70
142                              *  /L    /R\  R\      /     /L\  
143                              * 3     42 48  70    3     42 48  
144                              *           R\                 =\ 
145                              *            49                 49
146                              *         
147                              *  绕45左旋         绕50右旋           下次循环调整20的因子
148                              *    →     20       →         20 ← p      → ...
149                              *          /R\                /R\
150                              *         10  50 ←          10   48
151                              *         /L\  /=\          /L\   /=\
152                              *        5 12 48 70        5  12 45 50 ← ancestor
153                              *       /L   /=\          /L    /L  /=\
154                              *      3    45 49        3     42  49 70
155                              *          /L
156                              *         42 
157                              */
158                             ancestor.balanceFactor = '=';
159                             ancestor.left.balanceFactor = 'L';
160 
161                         }// ancestor 的左子节点的右子节点的平衡因子为 '=' 
162                         else {
163                             /* 删除60        调整因子               
164                              *      20        →       20             
165                              *      /R\               / \
166                              *    10   50 ← ancestor 10  50 ← 
167                              *    /L\   /L\          / \  /=\
168                              *   5  12 45 60        5  12 45 70
169                              *  /L    /R\  R\      /     /=\  
170                              * 3     42 48  70    3     42 48  
171                              *          /=\                /=\ 
172                              *         46 49              46 49
173                              *         
174                              *  绕45左旋         绕50右旋           下次循环调整20的因子
175                              *    →     20       →         20 ← p      → ...
176                              *          /R\                /R\
177                              *         10  50 ←          10   48
178                              *         /L\  /=\          /L\   /=\
179                              *        5 12 48 70        5  12 45  50 ← ancestor
180                              *       /L   /=\          /L    /=\   /=\
181                              *      3    45 49        3     42 46 49 70
182                              *          /=\
183                              *         42 46
184                              */
185                             ancestor.balanceFactor = '=';
186                             ancestor.left.balanceFactor = '=';
187 
188                         }
189                         ancestor.left.right.balanceFactor = '=';
190                         rotateLeft(ancestor.left);
191                         rotateRight(ancestor);
192                         ancestor = p;
193                     }
194                 }
195 
196             }
197             //从ancestor的左子树中删除节点,与上面是对称的
198             else if (comp < 0) {
199 
200                 if (ancestor.balanceFactor == '=') {
201 
202                     ancestor.balanceFactor = 'R';
203                     heightHasDecreased = false;
204                 } else if (ancestor.balanceFactor == 'L') {
205 
206                     ancestor.balanceFactor = '=';
207                     ancestor = ancestor.parent;
208 
209                 } else if (ancestor.balanceFactor == 'R') {
210 
211                     if (ancestor.right.balanceFactor == '=') {
212 
213                         ancestor.balanceFactor = 'R';
214                         ancestor.right.balanceFactor = 'L';
215                         rotateLeft(ancestor);
216                         heightHasDecreased = false;
217 
218                     } else if (ancestor.right.balanceFactor == 'R') {
219 
220                         Entry<E> p = ancestor.parent;
221                         ancestor.balanceFactor = '=';
222                         ancestor.right.balanceFactor = '=';
223                         rotateLeft(ancestor);
224                         ancestor = p;
225 
226                     } else if (ancestor.right.balanceFactor == 'L') {
227 
228                         Entry<E> p = ancestor.parent;
229                         if (ancestor.right.left.balanceFactor == 'R') {
230 
231                             ancestor.balanceFactor = 'L';
232                             ancestor.right.balanceFactor = '=';
233 
234                         } else if (ancestor.right.left.balanceFactor == 'L') {
235 
236                             ancestor.balanceFactor = '=';
237                             ancestor.right.balanceFactor = 'R';
238 
239                         } else {
240 
241                             ancestor.balanceFactor = '=';
242                             ancestor.right.balanceFactor = '=';
243 
244                         }
245                         ancestor.right.left.balanceFactor = '=';
246                         rotateRight(ancestor.right);
247                         rotateLeft(ancestor);
248                         ancestor = p;
249 
250                     }
251                 }
252             }
253         }
254     }
255 
256     public boolean contains(E o) {
257 
258         Entry<E> e = root;
259 
260         int comp;
261 
262         while (e != null) {
263 
264             comp = o.compareTo(e.elem);
265             if (comp == 0)
266                 return true;
267             else if (comp < 0)
268                 e = e.left;
269             else
270                 e = e.right;
271 
272         }
273         return false;
274     }
275 
276     //验证树是否是平衡二叉树
277     public boolean isAVL() {
278 
279         return checkAVL(root);
280 
281     }
282 
283     /**
284      * 验证指定的树是否是平衡二叉树
285      * @param p
286      * @return
287      */
288     public static <E extends Comparable<E>> boolean checkAVL(Entry<E> p) {
289 
290         if (p == null)
291             return true;
292         //左子树与右子树绝对值不能超过 1,并且左右子树也是平衡二叉树
293         return (Math.abs(h(p.left) - h(p.right)) <= 1 && checkAVL(p.left) && checkAVL(p.right));
294 
295     }
296 
297     /**
298      * 求指定节点的高度
299      * @param <E>
300      * @param p
301      * @return
302      */
303     protected static <E extends Comparable<E>> int h(Entry<E> p) {
304 
305         if (p == null)
306             return -1;
307         return 1 + Math.max(h(p.left), h(p.right));
308     }
309 
310     /**
311      * 树的高度
312      * @return
313      */
314     public int height() {
315 
316         return h(root);
317 
318     }
319 
320     //树的高度非递归求法
321     public int heightIter() {
322 
323         int height = -1;
324         for (Entry<E> temp = root; temp != null; height++)
325             if (temp.balanceFactor == 'L')
326                 temp = temp.left;
327             else
328                 temp = temp.right;
329         return height;
330     }
331 
332     @Override
333     public Iterator<E> iterator() {
334         return new TreeIterator();
335     }
336 
337     @Override
338     public int size() {
339         return size;
340     }
341 }

  

 

 

  1 package tree.avl;
  2 
  3 import java.util.AbstractSet;
  4 import java.util.Iterator;
  5 
  6 /**
  7  * 平衡二叉搜索(排序)树
  8  * 
  9  * @author jzj
 10  * @data 2009-12-25
 11  */
 12 public class AVLTree<E extends Comparable<E>> extends AbstractSet<E> {
 13     private Entry<E> root;//根节点
 14     private int size;//树节点个数
 15 
 16     private static class Entry<E> {
 17         E elem;//数据域
 18         Entry<E> parent;//父节点
 19         Entry<E> left;//左节点
 20         Entry<E> right;//右节点
 21         /*
 22          * 树的平衡因子,等号表示左子树和右子树有同样的高度。如果L,左子树比右子树高1。如果为R,则意味着右
 23          * 子树比左高1。刚创建时是平衡的,所以为=
 24          *             50
 25          *             /R\
 26          *            20  80
 27          *            /L  /R\
 28          *           10  70 100
 29          *           =   =  /=\
 30          *                 92 103
 31          *                 =  =
 32          */
 33         char balanceFactor = '=';
 34 
 35         //构造函数只有两个参数,左右节点是调用add方法时设置
 36         public Entry(E elem, Entry<E> parent) {
 37             this.elem = elem;
 38             this.parent = parent;
 39         }
 40     }
 41 
 42     private class TreeIterator implements Iterator<E> {
 43 
 44         private Entry<E> lastReturned = null;
 45         private Entry<E> next;
 46 
 47         TreeIterator() {
 48 
 49             next = root;
 50             if (next != null)
 51                 while (next.left != null)
 52                     next = next.left;
 53 
 54         }
 55 
 56         public boolean hasNext() {
 57 
 58             return next != null;
 59 
 60         }
 61 
 62         public E next() {
 63 
 64             lastReturned = next;
 65             next = successor(next);
 66             return lastReturned.elem;
 67 
 68         }
 69 
 70         public void remove() {
 71 
 72             if (lastReturned.left != null && lastReturned != null)
 73                 next = lastReturned;
 74             deleteEntry(lastReturned);
 75             lastReturned = null;
 76 
 77         }
 78     }
 79 
 80     /**
 81      * 左旋转:结果就是将p移到它的左子节点的位置,而p的右子节点被移到该元素原来位置
 82      * @param p 旋转元素
 83      */
 84     private void rotateLeft(Entry<E> p) {
 85         /*
 86         * 围绕50左旋转:
 87         *p → 50                 90
 88         *     \                 /\
 89         * r → 90      →       50 100
 90         *      \
 91         *     100
 92         * 
 93         * 围绕80左旋转:r的左子树变成p的右子树。因为位于r的左子树上的任意一个元素值大于p且小于r,所以r的左子
 94         * 树可以成为p的右子树这是没有问题的。其实上面也发生了同样的现象,只是r的左子树为空罢了
 95         *  p → 80                  90
 96         *      /\                  /\ 
 97         *     60 90 ← r     →     80 120
 98         *        /\               /\   /
 99         *      85 120           60 85 100
100         *          /
101         *         100
102         * 
103         * 围绕80在更大范围内旋转:元素不是围绕树的根旋转。旋转前后的树都是二叉搜索树。且被旋转元素80上的所
104         * 有元素在旋转中不移动(50、30、20、40这四个元素还是原来位置)
105         *       50                         50
106         *       / \                        / \
107         *     30   80 ← p                 30  90
108         *     /\   /\                     /\  / \
109         *   20 40 60 90 ← r      →      20 40 80 120
110         *            /\                       /\   /
111         *           85 120                  60 85 100
112         *              /
113         *             100
114         * 
115         * 节点数据结构:
116         *  +------------------+
117         *  | elem | p | l | r |
118         *  +------------------+
119         *  
120         *    +------------------+
121         *    | 50 |NULL|NULL| r |
122         *    +------------------+
123         *                 ↖⑥ ↘④
124         *         +---------------+
125         *         |80| p | l  | r |   ← p 
126         *         +---------------+
127         *         ↗       ↙     ↖③ ↘①      
128         *  +----------------+ +---------------+
129         *  |60| p |NULL|NULL| |90| p |  l | r |   ← r
130         *  +----------------+ +---------------+
131         *                     ↗②       ↙⑤    ↖↘ 
132         *              +----------------+ +---------------+
133         *              |85| p |NULL|NULL| |90| p | l |NULL|
134         *              +----------------+ +---------------+
135         *                                  ↗      ↙  
136         *                           +-----------------+
137         *                           |100| p |NULL|NULL|
138         *                           +-----------------+
139         */
140 
141         Entry<E> r = p.right;//旋转元素的右子节点
142         //把旋转元素的右子节点的左子节点接到旋转元素的右子树
143         p.right = r.left;//①
144         //如果旋转元素的右子节点存在左子节点的话,同时修改该节点的父节指针指向
145         if (r.left != null) {
146             //把旋转元素的右子节点的左子节点的父设置成旋转元素
147             r.left.parent = p;//②
148         }
149         //将旋转元素的右子节点的父设置成旋转元素的父,这里有可以p为根节点,那么旋转后p就成根节点
150         r.parent = p.parent;//③
151 
152         //如果旋转元素为根元素,则旋转后,旋转元素的右子节点r将成为根节点
153         if (p.parent == null) {
154             root = r;
155         }//否则p不是根节点,如果p是他父节点的左节点时
156         else if (p.parent.left == p) {
157             //让p的父节点的左指针指向r
158             p.parent.left = r;
159         }//否则如果p是他父节点的右节点时
160         else {
161             //让p的父节点的右指针指向r
162             p.parent.right = r;//④
163         }
164         //让旋转元素的左节点指向旋转元素p
165         r.left = p;//⑤
166         //让旋转元素的父节点指向旋转元素右节点r
167         p.parent = r;//⑥
168     }
169 
170     /**
171      * 右旋转:结果就是将p移到它的右子节点的位置,而p的左子节点被移到该元素原来位置
172      * 与左旋转是完全对称的,将左旋转中的lef与rigth互换即可得到,这里就不详细解释了
173      * @param p 旋转元素
174      */
175     private void rotateRight(Entry<E> p) {
176 
177         /*
178         * 围绕100右旋转:
179         *  p → 100              90
180         *       /               /\
181         * l → 90      →       50 100
182         *     /
183         *    50
184         * 
185         * 围绕80右旋转:l的右子树变成p的左子树。因为位于l的右子树上的任意一个元素值小于p且小于l,所以l的右
186         * 子树可以成为p的左子树这是没有问题的。其实上面也发生了同样的现象,只是l的右子树为空罢了
187         * 
188         *  p → 80                  60
189         *      /\                  /\ 
190         * l → 60 90         →     50 80
191         *     /\                   \  /\
192         *    50 70                55 70 90   
193         *     \   
194         *     55
195         */
196 
197         Entry<E> l = p.left;
198         p.left = l.right;
199         if (l.right != null) {
200             l.right.parent = p;
201         }
202         l.parent = p.parent;
203 
204         if (p.parent == null) {
205             root = l;
206         } else if (p.parent.right == p) {
207             p.parent.right = l;
208         } else {
209             p.parent.left = l;
210         }
211         l.right = p;
212         p.parent = l;
213     }
214 
215     /**
216      * AVLTree类的add方法类似于BinSerrchTree类的add方法,但是沿着根向下前进到插入点时,需记录这样一个被插
217      * 入Entry对象最近的祖先:该祖先的平衡因子balanceFactor值是L或R(即不歼),且让ancestor指向这个祖先节
218      * 点,该祖先节有什么用呢,从ancestor的子开始到新增节点路径上的所有祖先节点都是平衡,这些祖先节点会因为
219      * 新增节点而变得不平衡了,需要重新调整平衡因子,这个分界点在调整平衡因子时非常有用
220      * 
221      * @param elem 要新增元素的数据域
222      * @return
223      */
224     public boolean add(E elem) {
225         //如果树为空,则直接插入
226         if (root == null) {
227             root = new Entry<E>(elem, null);
228             size++;
229             return true;
230         } else {
231             Entry<E> tmp = root;//新增节点的父节点,从根节点下面开始找插入点
232             Entry<E> ancestor = null;//平衡因子不为 = 的最近祖先节点
233             int comp; //比较结果
234             while (true) {//死循环,直接找到插入点退出循环
235                 comp = elem.compareTo(tmp.elem);
236                 //如果已存在该元素,则直接返回失败
237                 if (comp == 0) {
238                     return false;
239                 }
240 
241                 //记录不平衡的祖先节点
242                 if (tmp.balanceFactor != '=') {
243                     //如果哪个祖先节点不平衡,则记录,当循环完后,ancestor指向的就是最近一个
244                     //不平衡的祖先节点
245                     ancestor = tmp;
246                 }
247 
248                 //如果小于当前比较节点,则在其左边插入
249                 if (comp < 0) {
250 
251                     //如果左子树不为空,继续循环在左边找插入点
252                     if (tmp.left != null) {
253                         tmp = tmp.left;
254                     } else {//否则插入
255                         tmp.left = new Entry<E>(elem, tmp);
256                         //插入后要进行平衡调整
257                         fixAfterInsertion(ancestor, tmp.left);
258                         size++;
259                         return true;
260                     }
261                 } else {//在右边插入
262 
263                     //如果右子树不为空,继续循环在右边找插入点
264                     if (tmp.right != null) {
265                         tmp = tmp.right;
266                     } else {//否则插入
267                         tmp.right = new Entry<E>(elem, tmp);
268                         //插入后要进行平衡调整
269                         fixAfterInsertion(ancestor, tmp.right);
270                         size++;
271                         return true;
272                     }
273                 }
274 
275             }
276         }
277     }
278 
279     /**
280      * 当新增节点后,会改变某些节点的平衡因子,所以添加节点后需重新调整平衡因子
281      * 
282      * 根据前人们的分析与研究,可分为6种情况
283      * 
284      * @param ancestor 新增元素的最近一个不平衡的祖先节点
285      * @param inserted 新增元素
286      */
287     protected void fixAfterInsertion(Entry<E> ancestor, Entry<E> inserted) {
288         E elem = inserted.elem;
289 
290         if (ancestor == null) {
291             /*
292              * 情况1:ancestor的值为null,即被插入Entry对象的每个祖先的平衡因子都是 =,此时新增节点后
293              * ,树的高度不会发生变化,所以不需要旋转,我们要作的就是调整从根节点到插入节点的路径上的所有
294              * 节点的平衡因子罢了
295              * 
296              *                       新增55后调整
297              *             50            →           50
298              *             /=\                       /R\
299              *           25   70                   25   70
300              *          /=\   /=\                 /=\   /L\
301              *         15 30 60 90               15 30 60 90
302              *         =  =  =   =               =  =  /L =
303              *                                        55
304              *                                        =
305              */
306             //根节点的平衡因子我们单独拿出来调整,因为adjustPath的参数好比是一个开区间,它不包括两头参数
307             //本身,而是从nserted.paraent开始到to的子节点为止,所以需单独调整,其他分支也一样
308             if (elem.compareTo(root.elem) < 0) {
309                 root.balanceFactor = 'L';
310             } else {
311                 root.balanceFactor = 'R';
312             }
313             //再调用adjustPath方法调整新增节点的父节点到root的某子节点路径上的所有祖先节点的
314             //平衡因子
315             adjustPath(root, inserted);
316         } else if ((ancestor.balanceFactor == 'L' && elem.compareTo(ancestor.elem) > 0)
317                 || (ancestor.balanceFactor == 'R' && elem.compareTo(ancestor.elem) < 0)) {
318             /*
319              * 情况2:
320              * ancestor.balanceFactor的值为 L,且在ancestor对象的右子树插入,或ancestor.balanceFac
321              * tor的值为 R,且在ancestor对象的左子树插入,这两插入方式都不会引起树的高度发生变化,所以我们
322              * 也不需要旋转,直接调整平衡因子即可
323              *                      新增55后调整
324              *  ancestor → 50           →              50
325              *            /L\                         /=\
326              *          25   70                     25   70
327              *         /R\   /=\                   /R\   /L\
328              *        15 30 60 90                 15 30 60 90
329              *           /L                          /L /L
330              *          28                          28 55
331              *                      新增28后调整
332              *  ancestor → 50            →             50
333              *            /R\                         /=\
334              *          25   70                     25   70
335              *         /=\   /L\                   /R\   /L\
336              *        15 30 60 90                 15 30 60 90
337              *              /L                       /L /L
338              *             55                       28 55
339              */
340             //先设置ancestor的平衡因子为 平衡
341             ancestor.balanceFactor = '=';
342             //然后按照一般策略对inserted与ancestor间的元素进行调整
343             adjustPath(ancestor, inserted);
344         } else if (ancestor.balanceFactor == 'R'
345                 && elem.compareTo(ancestor.right.elem) > 0) {
346             /*
347              * 情况3:
348              * ancestor.balanceFactor的值为 R,并且被插入的Entry位于ancestor的右子树的右子树上, 此
349              * 种情况下会引起树的不平衡,所以先需绕ancestor进行旋转,再进行平衡因子的调整
350              *
351              * 新增93                          先调整因子再绕70左旋
352              *   →         50                    →           50
353              *            /R\                                /R\
354              *          25   70  ← ancestor                25  90
355              *         /L    /R\                          /L   /=\
356              *        15    60 90                        15  70   98
357              *        =     =  /=\                       =  /=\   /L
358              *                80  98                       60 80 93
359              *                =   /=                       =  =  =
360              *                   93
361              *                   =
362              */
363             ancestor.balanceFactor = '=';
364             //围绕ancestor执行一次左旋
365             rotateLeft(ancestor);
366             //再调整ancestor.paraent(90)到新增节点路径上祖先节点平衡
367             adjustPath(ancestor.parent, inserted);
368         } else if (ancestor.balanceFactor == 'L'
369                 && elem.compareTo(ancestor.left.elem) < 0) {
370             /*
371              * 情况4:
372              * ancestor.balanceFactor的值为 L,并且被插入的Entry位于ancestor的左子树的左子树上,
373              * 此种情况下会引起树的不平衡,所以先需绕ancestor进行旋转,再进行平衡因子的调整
374              * 
375              * 新增13                         先调整因子再绕50右旋
376              *   →         50 ← ancestor        →            20
377              *            /L\                                /=\
378              *          20   70                            10   50
379              *         /=\   /=\                          /R\   /=\
380              *        10 30 60 90                        5  15 30  70
381              *       /=\ /=\=  =                         = /L /=\  /=\
382              *      5 15 25 35                            13 25 35 60 90
383              *      = /= = =                              =  =  =  =  = 
384              *       13         
385              *       =        
386              */
387             ancestor.balanceFactor = '=';
388             //围绕ancestor执行一次右旋
389             rotateRight(ancestor);
390             //再调整ancestor.paraent(20)到新增节点路径上祖先节点平衡
391             adjustPath(ancestor.parent, inserted);
392         } else if (ancestor.balanceFactor == 'L'
393                 && elem.compareTo(ancestor.left.elem) > 0) {
394             /*
395              * 情况5:
396              * ancestor.balanceFactor的值为 L,并且被插入的Entry位于ancestor的左子树的右子树上。此
397              * 种情况也会导致树不平衡,此种与第6种一样都需要执行两次旋转(执行一次绕ancestor的左子节点左
398              * 旋,接着执行一次绕ancestor执行一次右旋)后,树才平衡,最后还需调用 左-右旋 专有方法进行平衡
399              * 因子的调整
400              */
401             rotateLeft(ancestor.left);
402             rotateRight(ancestor);
403             //旋转后调用 左-右旋 专有方法进行平衡因子的调整
404             adjustLeftRigth(ancestor, inserted);
405         } else if (ancestor.balanceFactor == 'R'
406                 && elem.compareTo(ancestor.right.elem) < 0) {
407 
408             /*
409              * 情况6:
410              * ancestor.balanceFactor的值为 R,并且被插入的Entry位于ancestor的右子树的 左子树上,此
411              * 种情况也会导致树不平衡,此种与第5种一样都需要执行两次旋转(执行一次绕ancestor的右子节点右旋
412              * ,接着执行一次绕ancestor执行一次左旋)后,树才平衡,最后还需调用 右-左旋 专有方法进行平衡因
413              * 子的调整
414              */
415             rotateRight(ancestor.right);
416             rotateLeft(ancestor);
417             //旋转后调用 右-左旋 专有方法进行平衡因子的调整
418             adjustRigthLeft(ancestor, inserted);
419         }
420     }

图片 1

  1     /**
  2      * 调整指定路径上的节点的平衡因子
  3      * 
  4      * 注,指定的路径上的所有节点一定是平衡的,因此如果被插入元素小于某个祖先节点,
  5      * 则这个祖先节点新的平衡因子是 L,反之为 R。
  6      * 
  7      * @param inserted 从哪里元素开始向上调整,但不包括该,即从父开始)
  8      * @param to 直到哪个元素结束,但不包括该元素,一般传进来的为ancestor
  9      */
 10     protected void adjustPath(Entry<E> to, Entry<E> inserted) {
 11         E elem = inserted.elem;
 12         Entry<E> tmp = inserted.parent;
 13         //从新增节点的父节点开始向上回溯调整,直到结尾节点to止
 14         while (tmp != to) {
 15             /*
 16              * 插入30,则在25右边插入,这样父节点平衡会被打破,右子树就会比左子树高1,所以平衡因子为R;祖
 17              * 先节点50的平衡因子也被打破,因为在50的左子树上插入的,所以对50来说,左子树会比右子树高1,所
 18              * 以其平衡因子为L
 19              *    50                      50
 20              *    /=\       插入30        /L\
 21              *   25  70       →         25  70
 22              *   =   =                   R\  =
 23              *                            30
 24              *                            = 
 25              */
 26             //如果新增元素比祖先节点小,则是在祖先节点的左边插入,则自然该祖先的左比右子树会高1            
 27             if (elem.compareTo(tmp.elem) < 0) {
 28 
 29                 tmp.balanceFactor = 'L';
 30             } else {
 31                 //否则会插到右边,那么祖先节点的右就会比左子树高1
 32                 tmp.balanceFactor = 'R';
 33             }
 34             tmp = tmp.parent;//再调整祖先的祖先
 35         }
 36     }
 37 
 38     /**
 39      * 进行 左-右旋转 后平衡因子调整
 40      * 分三种情况
 41      * @param ancestor
 42      * @param inserted
 43      */
 44     protected void adjustLeftRigth(Entry<E> ancestor, Entry<E> inserted) {
 45         E elem = inserted.elem;
 46         if (ancestor.parent == inserted) {
 47             /*
 48              * 第1种,新增的节点在旋转完成后为ancestor父节点情况:
 49              * 
 50              * 新增40                          绕30左旋                绕50右旋
 51              *   →      50 ← ancestor         →         50         →
 52              *          /L                              /L         
 53              *         30                              40  
 54              *         =\                             /=
 55              *          40                           30
 56              *          =                            =
 57              *          
 58              *                    调整平衡因子
 59              *          40            →            40
 60              *          /=\                        /=\
 61              *         30 50                      30 50
 62              *         =  L                       =   =
 63              *         
 64              * 注,这里的 左-右旋 是在fixAfterInsertion方法中的第5种情况中完成的,在这里只是平衡因子的
 65              * 调整,图是为了好说明问题而放在这个方法中的,下面的两个分支也是一样      
 66              */
 67             ancestor.balanceFactor = '=';
 68         } else if (elem.compareTo(ancestor.parent.elem) < 0) {
 69             /*
 70              * 第2种,新增的节点在旋转完成后为不为ancestor父节点,且新增节点比旋转后ancestor的父节点要小
 71              * 的情况
 72              * 
 73              * 由于插入元素(35)比旋转后ancestor(50)的父节点(40)要小, 所以新增节点会在其左子树中
 74              * 
 75              * 新增35                         绕20左旋
 76              *   →      50 ← ancestor        →                 50
 77              *          /L\                                    /L\
 78              *        20   90                                40   90
 79              *       /=\   /=\                              /=\   /=\
 80              *     10  40 70  100                          20 45 70 100
 81              *    /=\  /=\=   =                            /=\    
 82              *   5  15 30 45                              10  30   
 83              *   =  =  =\ =                              /=\   =\
 84              *          35                              5  15   35
 85              *          =                               =  =    =
 86              *          
 87              *  绕50右旋                      调整平衡因子
 88              *     →        40                →                40
 89              *              /=\                                /=\
 90              *             20  50                            20   50
 91              *            /=\  /L\                          /=\   /R\
 92              *          10 30 45 90                        10 30 45  90
 93              *         /=\  =\   /=\                      /=\  R\    /=\
 94              *        5  15  35 70 100                   5  15  35  70  100
 95              *        =  =   =  =  =                     =  =   =   =   =
 96              *          
 97              */
 98             ancestor.balanceFactor = 'R';
 99             //调整ancestor兄弟节点到插入点路径上节点平衡因子
100             adjustPath(ancestor.parent.left, inserted);
101         } else {
102             /*
103              * 第2种,新增的节点在旋转完成后为不为ancestor父节点,且新增节点比旋转后ancestor的父节点要大的
104              * 情况
105              * 
106              * 由于插入元素(42)比旋转后ancestor(50)的父节点(40)要大,所以新增节点会在其右子树中
107              * 
108              * 新增42                           绕20左旋
109              *   →      50 ← ancestor          →               50
110              *          /L\                                    /L\
111              *        20   90                                40   90
112              *       /=\   /=\                              /=\    /=\
113              *     10  40 70  100                          20  45 70 100
114              *    /=\  /=\=   =                           /=\  /=
115              *   5  15 30 45                             10 30 42  
116              *   =  =  =  /=                             /=\=  =
117              *           42                             5  15   
118              *           =                              =  =    
119              *          
120              * 绕50右旋                        调整平衡因子
121              *   →          40                 →               40
122              *              /=\                                /=\
123              *             20  50                            20   50
124              *            /=\  /L\                          /L\   /=\
125              *          10 30 45 90                        10 30 45  90
126              *         /=\   /=  /=\                      /=\    /L  /=\
127              *        5  15 42  70 100                    5 15  42  70 100
128              *        =  =  =   =  =                      =  =  =   =  =
129              *          
130              */
131             ancestor.parent.left.balanceFactor = 'L';
132 
133             ancestor.balanceFactor = '=';
134             //调整ancestor节点到插入点路径上节点平衡因子
135             adjustPath(ancestor, inserted);
136         }
137     }
138 
139     /**
140      * 进行 右-左旋转 后平衡因子调整
141      * 
142      * 与adjustLeftRigth方法一样,也有三种情况,这两个方法是对称的
143      * @param ancestor
144      * @param inserted
145      */
146     protected void adjustRigthLeft(Entry<E> ancestor, Entry<E> inserted) {
147         E elem = inserted.elem;
148         if (ancestor.parent == inserted) {
149             /*
150              * 第1种,新增的节点在旋转完成后为ancestor父节点情况: 
151              * 
152              * 新增40                          绕50右旋                绕30左旋 
153              *   →       30 ← ancestor        →        30          →
154              *           R\                            R\         
155              *            50                            40  
156              *           /=                              =\
157              *          40                                50
158              *          =                                 =
159              *          
160              *          40         调整平衡因子         40
161              *          /=\           →            /=\
162              *         30 50                      30  50
163              *         R  =                       =   =
164              *         
165              * 注,这里的 右-左旋 是在fixAfterInsertion方法中的第6种情况中完成的,这里只是 平衡因子的调
166              * 整,图是为了好说明问题而放在这个方法中的,下面的两个分支也是一样      
167              */
168             ancestor.balanceFactor = '=';
169         } else if (elem.compareTo(ancestor.parent.elem) > 0) {
170             /*
171              * 第2种,新增的节点在旋转完成后为不为ancestor父节点,且新增节点比旋转后
172              * ancestor的父节点要大的情况
173              * 
174              * 由于插入元素(73)比旋转后ancestor(50)的父节点(70)要大, 所以新增节点会
175              * 在其右子树中
176              * 
177              * 新增73                          绕90右旋
178              *   →       50 ← ancestor       →                  50
179              *          /R\                                    /R\
180              *        20   90                                20   70
181              *       /=\   /=\                              /=\   /=\
182              *     10  40 70  95                          10  40 65 90
183              *     =   = /=\  /=\                         =   =  =  /=\ 
184              *          65 75 93 97                                75  95
185              *          =  /= =  =                                 /=  /=\
186              *            73                                      73  93 97
187              *            =    
188              *                          
189              * 绕50左旋                       调整平衡因子
190              *   →          70                →                70
191              *              /=\                                /=\
192              *            50   90                            50   90
193              *           /R\   /=\                          /L\   /=\
194              *          20 65 75  95                       20 65 75  95
195              *         /=\ =  /=  /=\                     /=\ =  /L  /=\
196              *        10  40 73  93 97                   10  40 73  93 97
197              *        =   =   =   =  =                   =   =  =   =   =
198              *          
199              */
200             ancestor.balanceFactor = 'L';
201             adjustPath(ancestor.parent.right, inserted);
202         } else {
203             /*
204              * 第2种,新增的节点在旋转完成后为不为ancestor父节点,且新增节点比旋转后ancestor的父节点要小
205              * 的情况
206              * 
207              * 由于插入元素(73)比旋转后ancestor(50)的父节点(70)要大, 所以新增节点会在其右子树中
208              * 
209              * 新增63                          绕90右旋
210              *   →       50 ← ancestor       →                 50
211              *          /R\                                    /R\
212              *        20   90                                20   70
213              *       /=\   /=\                              /=\   /=\
214              *     10  40 70  95                          10  40 65 90
215              *     =   = /=\  /=\                         =   =  /= /=\ 
216              *          65 75 93 97                             63 75 95
217              *          /= =  =  =                              =  =  /=\
218              *         63                                            93 97
219              *         =                                             =  =
220              *                          
221              * 绕50左旋                       调整平衡因子
222              *   →          70                →                70
223              *              /=\                                /=\
224              *            50   90                            50   90
225              *           /R\   /=\                          /=\   /R\
226              *         20  65 75 95                       20  65 75 95
227              *        /=\  /= =  /=\                     /=\  /L    /=\
228              *       10 40 63   93 97                   10 40 63   93 97
229              *       =  =  =    =  =                    =  =  =    =  =         
230              */
231             ancestor.parent.right.balanceFactor = 'R';
232             ancestor.balanceFactor = '=';
233             adjustPath(ancestor, inserted);
234         }
235     }
236 
237     /**
238      * 删除指定节点
239      * 
240      * @param elem
241      * @return boolean
242      */
243     public boolean remove(E elem) {
244         Entry<E> e = getEntry(elem);
245         if (e == null)
246             return false;
247         deleteEntry(e);
248         return true;
249     }
250 
251     private Entry<E> getEntry(E e) {
252         Entry<E> tmp = root;
253         int c;
254         while (tmp != null) {
255             c = e.compareTo(tmp.elem);
256             if (c == 0) {
257                 return tmp;
258             } else if (c < 0) {
259                 tmp = tmp.left;
260             } else {
261                 tmp = tmp.right;
262             }
263         }
264         return null;
265     }
266 
267     private void deleteEntry(Entry<E> p) {
268         if (p.left != null && p.right != null) {
269 
270             Entry<E> s = successor(p);
271 
272             p.elem = s.elem;
273 
274             p = s;
275         }
276 
277         if (p.left == null && p.right == null) {
278 
279             if (p.parent == null) {
280                 root = null;
281             } else if (p == p.parent.left) {
282                 p.parent.left = null;
283             } else {
284                 p.parent.right = null;
285             }
286 
287         } else {
288 
289             Entry<E> rep;
290             if (p.left != null) {
291                 rep = p.left;
292             } else {
293                 rep = p.right;
294             }
295 
296             rep.parent = p.parent;
297 
298             if (p.parent == null) {
299                 root = rep;
300             } else if (p == p.parent.left) {
301                 p.parent.left = rep;
302             } else {
303                 p.parent.right = rep;
304             }
305 
306         }
307         fixAfterDeletion(p.elem, p.parent);
308 
309         p.parent = null;
310         p.left = null;
311         p.right = null;
312 
313         size--;
314     }
315 
316     /**
317      * 查找指定节点的中序遍历序列的直接后继节点,此方法的实现与二叉搜索树类(BinSearchTree.java)的此方法是
318      * 一样的,具体的思路请参考二叉搜索树类中的相应方法
319      * 
320      * @param e 需要查找哪个节点的直接后继节点
321      * @return Entry<E> 直接后继节点
322      */
323     private Entry<E> successor(Entry<E> e) {
324         if (e == null) {
325             return null;
326         }//如果待找的节点有右子树,则在右子树上查找
327         else if (e.right != null) {
328             //默认后继节点为右子节点(如果右子节点没有左子树时即为该节点)
329             Entry<E> p = e.right;
330             while (p.left != null) {
331                 //注,如果右子节点的左子树不为空,则在左子树中查找,且后面找时要一直向左拐
332                 p = p.left;
333             }
334             return p;
335         }//如果待查节点没有右子树,则要在祖宗节点中查找后继节点 
336         else {
337 
338             //默认后继节点为父节点(如果待查节点为父节点的左子树,则后继为父节点)
339             Entry<E> p = e.parent;
340             Entry<E> c = e;//当前节点,如果其父不为后继,则下次指向父节点
341             //如果待查节点为父节点的右节点时,继续向上找,一直要找到c为左子节点,则p才是后继
342             while (p != null && c == p.right) {
343                 c = p;
344                 p = p.parent;
345             }
346             return p;
347         }
348     }
<?php
class BinTree{
        public $data;
        public $left;
        public $right;
}
//前序遍历生成二叉树
function createBinTree(){
        $handle=fopen("php://stdin","r");
        $e=trim(fgets($handle));
        if($e=="#"){
                $binTree=null;
        }else{
                $binTree=new BinTree();
                $binTree->data=$e;
                $binTree->left=createBinTree();
                $binTree->right=createBinTree();
        }   
        return $binTree;
}    

$tree=createBinTree();

var_dump($tree);

A
B
#
D
#
#
C
#
#
object(BinTree)#1 (3) {
  ["data"]=>
  string(1) "A"
  ["left"]=>
  object(BinTree)#2 (3) {
    ["data"]=>
    string(1) "B"
    ["left"]=>
    NULL
    ["right"]=>
    object(BinTree)#3 (3) {
      ["data"]=>
      string(1) "D"
      ["left"]=>
      NULL
      ["right"]=>
      NULL
    }
  }
  ["right"]=>
  object(BinTree)#4 (3) {
    ["data"]=>
    string(1) "C"
    ["left"]=>
    NULL
    ["right"]=>
    NULL
  }
}
 1 /**
 2  * 平衡二叉搜索(排序)树
 3  * 
 4  * 平衡二叉搜索树双称为AVL树,它也是一棵二叉搜索树,是对二叉搜索树的一种改进,或都是具有下列性质的二叉树:它
 5  * 的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。
 6  * 
 7  * 平衡因子(Balance Factor,BF)定义为该节点的左子树的深度减去其右子树的深度,则平衡二叉树上所有节点的平
 8  * 衡因子只可能是-1、0和1。只要树上有一个节点的平衡因子的绝对值大于1,则该二叉树就是不平衡的了。
 9  * 
10  * 使用二叉排序树保持平衡的基本思想是:每当在二叉排序树中插入一个节点时,首先检查是否因插入而破坏了平衡,若
11  * 是,则找出其中的最小不平衡二叉树,在保持二叉排序树特性的情况下,调整最小不平衡子s树中节点之间的关系,以达
12  * 到新的平衡。所谓最小不平衡子树指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
13  * 
14  * 对于平衡二叉搜索树,保持树的平衡的基本机制就是旋转。旋转是对树的元素顺序进行调节。旋转的目的是消除由于临
15  * 时插入和删除对树的平衡产生的影响。
16  * 
17  * 有四种旋转:
18  * 1)绕某元素左旋转
19  *          80 ← p                    90
20  *          /\                        /\
21  *         60 90 ← r        →        80 120
22  *            /\                     /\  /
23  *          85 120                 60 85 100
24  *              /
25  *             100          
26  *             
27  * 2)绕某元素右旋转
28  *      p → 100                        85
29  *          /\                         /\
30  *     l → 85 120          →         60 100
31  *         /\                         \  /\
32  *        60 90                      80 90 120
33  *         \
34  *         80
35  * 
36  * 3)绕某元素的左子节点左旋转,接着再绕该元素自己右旋转。此情况下就是 左旋与右旋 的结合,具体操作时可以分
37  * 解成这两种操作,只是围绕点不一样而已
38  * 
39  * 先绕100的左子节点80左旋转,接着再绕100左旋转
40  * 
41  *                左旋                   右旋
42  *         100     →     p → 100         →         90
43  *         /\                 /\                   /\
44  *    p → 80 120        l → 90 120                80 100
45  *        /\                 /                    /\   \
46  *       60 90 ← r          80                   60 85 120
47  *          /               /\
48  *         85              60 85
49  *         
50  * 4)绕某元素的右子节点右旋转,接着再绕该元素自己左旋转。此情况下就是 右旋与左旋 的结合,具体操作时可以分解
51  * 成这两种操作,只是围绕点不一样而已
52  * 
53  * 先绕80的右子节点80右旋转,接着再绕80左旋转
54  *                     右旋               左旋
55  *          80          →      80 ← p     →       85
56  *          /\                 /\                 /\
57  *         60 100 ← p         60 85 ← r         80 100
58  *            /\                 \              /  /\
59  *       l → 85 120               100          60 90 120
60  *            \                   /\
61  *            90                 90 120
62  *            
63  * 平衡二叉树实现类 AVLTree 中的很多方法与排序二叉树是一新的,详细请参考 BinSearchTree 类中相应方法
64  * 
65  * AVLTree中的Entry对象与BinSearchTree中的Entry对象是有区别的,所以AVLTree类不能是BinSearchTree的
66  * 了类,虽然很多的方法是一样的(如:contains、getEntry、successor、iterator),还有一些方法(add、de
67  * leteEntry)只是在操作后增加了节点平衡因子调整动作,但不能直接继承于它。
68  * 
69  * 二叉搜索树与平衡二叉搜索树没有在Java集合框架中实现,但RED-BLACK树在TreeMap实现过,当然TreeSet也是,
70  * 因为它是基于TreeMap实现的,TreeSet对象基本上就是一个忽略了每个元素值部分的TreeMap对象。
71  * 
72  */

测试:

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图