平衡二叉树和哈夫曼树

平衡二叉树

  • 父节点的左子树和右子树的高度之差不能大于1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
function Node(key) {
       this.key = key;
       this.height = 0;
       this.left = null;
       this.right = null;
   }
   function AVLTree(head) {
       this.root = head;
   }
   AVLTree.prototype.add = function(node, key) {
       if(node == null) {
           return new Node(key);
       }
       if (key < node.key) {
           node.left = this.add(node.left, key);  
       } else {
           node.right = this.add(node.right, key);
       }  
     
       return this.balance(node);
   }
   Node.prototype._getDiffer = function(node) {
       return (node ? node._getHeight(node.right) - node._getHeight(node.left) : 0);
   }
   Node.prototype._getHeight = function(node) {
       return (node ? node.height : -1);
   }
   AVLTree.prototype._fixHeight = function(node) {
       if(node) {
           node.height = ( node._getHeight(node.left) > node._getHeight(node.right) 
               ? node._getHeight(node.left) : node._getHeight(node.right) ) + 1;
       }
   }
   AVLTree.prototype.balance = function(node) {
       this._fixHeight(node);
       if (node._getDiffer(node) == 2) {
           if (node._getDiffer(node.right) < 0) {
               node.right = this.rotateRight(node.right);
           }
           return this.rotateLeft(node);
       }
       if (node._getDiffer(node) == -2) {
           if (node._getDiffer(node.left) > 0) {
               node.left = this.rotateLeft(node.left);
           }
           return this.rotateRight(node);
       }
       return node;
   }
   AVLTree.prototype.rotateRight = function(node) {
       let temp = node.left;
       node.left = temp.right;
       temp.right = node;
       this._fixHeight(temp);
       this._fixHeight(node);
       // console.log(temp);
       return temp;
   }
   AVLTree.prototype.rotateLeft = function(node) {
       let temp = node.right;
       node.right = temp.left;
       temp.left = node;
       this._fixHeight(node);
       this._fixHeight(temp);
       // console.log(temp);
       return temp;
   }
   AVLTree.prototype.getMin = function(node) {
       return (node.left ? this.getMin(node.left) : node);
   }
   AVLTree.prototype.getMax = function(node) {
       return (node.right ? this.getMax(node.right) : node);
   }
   AVLTree.prototype.removeMin = function(node) {
       if (!node.left) {
           return node.right;
       }
       node.left = this.removeMin(node.left);
       return this.balance(node);
   }
   AVLTree.prototype.removeNode = function(node, key) {
       if (!node) {
           return 0;
       }
       if (key < node.key) {
           node.left = this.removeNode(node.left, key);
       } 
       if (key > node.key) {
           node.right = this.removeNode(node.right, key);
       }
       if (key == node.key) {
           let temp = node.left;
           let temp1 = node.right;
           if (!temp1) {
               return temp;
           }
           let min = this.getMin(temp1);
           min.right = this.removeMin(temp1);
           min.left = temp;
           return this.balance(min); 
       }
       return this.balance(node); 
   }
   let head = new Node(1);
   let tree = new AVLTree(head);
   tree.root = tree.add(tree.root, 2);
   // console.log('added 5');
   tree.root = tree.add(tree.root, 3);
   // console.log('added 7');
   tree.root = tree.add(tree.root, 4);
   tree.root = tree.add(tree.root, 5);
   // console.log(tree.root);
   tree.root = tree.add(tree.root, 6);
   // console.log('add 5');
   tree.root = tree.add(tree.root, 7);
   tree.root = tree.add(tree.root, 8);
   tree.root = tree.add(tree.root, 9);
   tree.root = tree.add(tree.root, 10);
   console.log(tree.root);

哈夫曼树

  • 给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function Node(data) {
       this.data = data;
       this.left = this.right = null;
   }
   function createHafumanTree(data) {
       if ( !(data instanceof Array) )
           throw '数据错误';
       var nodes = [];
       for (var i = 0, len = data.length; i < len; i++) {
           nodes.push( new Node(data[i]) );
       }
       while(nodes.length > 1) {
           nodes.sort(function(a, b) {return a.data - b.data });
           var min1 = nodes.shift();
           var min2 = nodes.shift();
           var newNode = new Node(min1.data + min2.data);
           newNode.left = min1;
           newNode.right = min2;
           nodes.unshift(newNode);
       }
       return nodes[0];
   }
   var data = [1, 54, 23, 64, 53, 87, 97];
   var rs = createHafumanTree(data);
   console.log(rs);