簡介

二元樹 (Binary Tree) 是資料結構中樹狀結構的一種，也是常使用的一種資料結構，很多其他的樹種也是基於二元樹發展出來，所以是很重要的一種資料結構。

定義

二元樹顧名思義是指每個節點都最多只能有兩個分支，所以會看起來這樣：
二元樹

而比較嚴謹的定義如下：

  1. 每個節點最多有兩個子節點。
  2. 子節點有左右之分。

當然原來樹的定義也是要繼承下來。

在二元樹中也定義了一些專有名詞，解釋如下：

完滿二元樹 (Full Binary Tree)

或翻譯滿二元樹，每個節點有 0 或 2 個子節點。也稱作嚴格二元樹 (Strictly Binary Tree)、正規二元樹 (Proper Binary Tree) 或 2-tree。範例如下：
完滿二元樹 (Full Binary Tree)

大多數的中文資料對完滿二元樹的定義相當於英文的完美二元樹。

完全二元樹 (Complete Binary Tree)

除了最後一階層之外的階層都必須填滿，而最後一階層的節點必須由左至右填入。範例如下：
完全二元樹 (Complete Binary Tree)

完美二元樹 (Perfect Binary Tree)

同時滿足完滿二元樹的條件，並且所有的葉節點都在同一個階層。範例如下：
完美二元樹 (Perfect Binary Tree)

在這個定義下可以得知，完美二元樹也必定是完全二元樹。另外他也同時具有下面數學特性：

一棵深度為 d 的完美二元樹，其節點數為2d - 1。

歪斜二元樹 (Skewed Binary Tree)

或翻譯作偏斜二元樹，都所有節點都只有同一邊的子節點的時候，就稱為歪斜二元樹，都只有左子節點的時候稱為左歪斜二元樹；都只有右子節點的時候稱為右歪斜二元樹。範例如下：
歪斜二元樹 (Skewed Binary Tree)

實作

二元樹的實作方式有兩種，使用連結串列或是陣列，應該考慮實際應用的情境選擇實作方式與介面，而不同的使用情況介面有很大的差異。這裡以簡單介面提供建立樹狀結構，實作以下介面：

  1. parent：取得父節點。
  2. left：取得左子節點。
  3. right：取得右子節點。
  4. addLeft：加入左子節點。
  5. addRight：加入右子節點。
  6. remove：移除節點。
  7. clone：複製樹。
  8. level：節點的階層。
  9. depth：樹的深度。
  10. size：子樹的節點個數。

連結串列

連結串列的方式較為簡單，使用三個指標分別指向父節點、左子節點和右子節點即可完成。由於本文另外實作 level、depth 和 size 的介面，所以還需額外的處理，這三個介面可以使用即時運算的方式，僅在呼叫時計算，這個方式也比較容易實作；而本文這裡是採用額外的記憶體去記錄這三種資料，所以必須考慮到節點異動時去更新其他節點的資料。至於用哪種方式效能較好，應該視實際的使用情況，例如時常需要取得這三項資料，則可考慮空間換時間。

陣列

陣列比較適合用在提供資料集合，僅提供資料的存放與查找；而我在這裡實作的是提供樹狀結構介面，可以對每個節點進行操作，對陣列來說要實作符合的介面效能上較不利。

陣列實作上利用一個陣列來表示整棵樹的資料結構，而利用特定的索引公式，可以快速計算出位於某一所引位置的節點，其父節點、左子節點和右子節點的索引位置，而無需另外的指標表示。為了簡化判斷，通常陣列 [0] 的位置不使用，根節點在 [1] 的位置開始，公式如下：

1
2
3
父節點 = floor(index / 2)
左子節點 = index * 2
右子節點 = index * 2 + 1

同樣的level也可以用索引計算出來：

Level = floor(log2(index) + 1)

如下圖所示：
陣列實作

使用陣列實作在歪斜二元樹的情況下，會需要產生非常巨大的陣列，然而實際上使用到的索引位置只有少部分，會造成大量的記憶體空間浪費，甚至記憶體不足的現象。

語法

C#

抽象類別

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinaryTree
{
    public abstract class BinaryTree<T>
    {
        public T Value { get; set; }

        public abstract int Count { get; }
        public abstract int Depth { get; }
        public abstract BinaryTree<T> Parent { get; }
        public abstract BinaryTree<T> Left { get; }
        public abstract BinaryTree<T> Right { get; }
        public abstract int Level { get; }

        public BinaryTree(T value)
        {
            this.Value = value;
        }

        public abstract void AddLeft(T value);
        public abstract void AddRight(T value);
        public abstract void AddLeft(BinaryTree<T> tree);
        public abstract void AddRight(BinaryTree<T> tree);
        public abstract void Remove();
        public abstract BinaryTree<T> Clone();

        public static void Copy(BinaryTree<T> srcTree, BinaryTree<T> destTree)
        {
            if (srcTree.Left != null)
            {
                destTree.AddLeft(srcTree.Left.Value);
                Copy(srcTree.Left, destTree.Left);
            }
            if (srcTree.Right != null)
            {
                destTree.AddRight(srcTree.Right.Value);
                Copy(srcTree.Right, destTree.Right);
            }
        }
    }
}

連結串列

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinaryTree
{
    public class LinkedBinaryTree<T> : BinaryTree<T>
    {
        private int count;
        public override int Count
        {
            get
            {
                return count;
            }
        }

        private int depth;
        public override int Depth
        {
            get
            {
                return depth;
            }
        }

        private LinkedBinaryTree<T> parent;
        public override BinaryTree<T> Parent
        {
            get
            {
                return parent;
            }
        }

        private LinkedBinaryTree<T> left;
        public override BinaryTree<T> Left
        {
            get
            {
                return left;
            }
        }

        private LinkedBinaryTree<T> right;
        public override BinaryTree<T> Right
        {
            get
            {
                return right;
            }
        }

        private int level;
        public override int Level
        {
            get
            {
                return level;
            }
        }

        public LinkedBinaryTree(T value)
            :base(value)
        {
            count = 1;
            depth = 1;
            level = 1;
        }

        public override void AddLeft(T value)
        {
            Add(ref left, value);
        }

        public override void AddRight(T value)
        {
            Add(ref right, value);
        }

        public override void AddLeft(BinaryTree<T> tree)
        {
            Add(ref left, tree);
        }

        public override void AddRight(BinaryTree<T> tree)
        {
            Add(ref right, tree);
        }

        protected void Add(ref LinkedBinaryTree<T> child, T value)
        {
            Add(ref child, new LinkedBinaryTree<T>(value));
        }

        protected void Add(ref LinkedBinaryTree<T> child, BinaryTree<T> tree)
        {
            if (child != null)
                throw new Exception("Child is existed");
            LinkedBinaryTree<T> tmpTree = tree as LinkedBinaryTree<T>;
            if (tmpTree == null)
            {
                tmpTree = new LinkedBinaryTree<T>(tree.Value);
                BinaryTree<T>.Copy(tree, tmpTree);
            }
            child = tmpTree;
            child.level = level + 1;
            child.parent = this;
            if (depth == 1)
            {
                depth = 2;
                BubbleDepth();
            }
            ++count;
            BubbleCount(1);
        }

        public override void Remove()
        {
            LinkedBinaryTree<T> sibling;
            if (parent == null)
                return;
            else if (parent.left == this)
            {
                parent.left = null;
                sibling = parent.right;
            }
            else if (parent.right == this)
            {
                parent.right = null;
                sibling = parent.left;
            }
            else
                return;

            if (depth + 1 == parent.depth)
            {
                if (sibling == null || sibling.depth < depth)
                    parent.UpdateDepth();
            }
            parent.count -= count;
            parent.BubbleCount(-count);
            parent = null;
        }

        public override BinaryTree<T> Clone()
        {
            LinkedBinaryTree<T> cloneTree = new LinkedBinaryTree<T>(this.Value);
            if (this.parent == null)
            {
                cloneTree.count = this.count;
                cloneTree.depth = this.depth;
                cloneTree.level = this.level;
                cloneTree.left = (LinkedBinaryTree<T>)this.left.Clone();
                cloneTree.right = (LinkedBinaryTree<T>)this.right.Clone();
                cloneTree.left.parent = cloneTree;
                cloneTree.right.parent = cloneTree;
            }
            else
                BinaryTree<T>.Copy(this, cloneTree);
            return cloneTree;
        }

        protected void BubbleDepth()
        {
            if (parent == null)
                return;

            if (depth + 1 > parent.depth)
            {
                parent.depth = depth + 1;
                parent.BubbleDepth();
            }
        }

        protected void UpdateDepth()
        {
            int tmpDepth = depth;
            depth = 1;

            if (left != null)
                depth = left.depth + 1;
            if (right != null && right.depth + 1 > depth)
                depth = right.depth + 1;

            if (tmpDepth == depth || parent == null)
                return;
            if (tmpDepth + 1 == parent.depth)
                parent.UpdateDepth();
        }

        protected void BubbleCount(int diff)
        {
            if (parent == null)
                return;

            parent.count += diff;
            parent.BubbleCount(diff);
        }
    }
}

陣列

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinaryTree
{
    public class ArrayBinaryTree<T> : BinaryTree<T>
    {
        public class SharedData<S>
        {
            public ArrayBinaryTree<S>[] Array { get; set; }
        }

        protected SharedData<T> data;

        protected int index;

        protected int parentIndex
        {
            get
            {
                return index / 2;
            }
        }
        protected int leftIndex
        {
            get
            {
                return index * 2;
            }
        }
        protected int rightIndex
        {
            get
            {
                return index * 2 + 1;
            }
        }

        protected int count;
        public override int Count
        {
            get
            {
                return count;
            }
        }

        protected int depth;
        public override int Depth
        {
            get
            {
                return depth;
            }
        }

        public override BinaryTree<T> Parent
        {
            get
            {
                return data.Array[parentIndex];
            }
        }

        public override BinaryTree<T> Left
        {
            get
            {
                int i = leftIndex;
                if (i < data.Array.Length)
                    return data.Array[i];
                else
                    return null;
            }
        }

        public override BinaryTree<T> Right
        {
            get
            {
                int i = rightIndex;
                if (i < data.Array.Length)
                    return data.Array[i];
                else
                    return null;
            }
        }

        public override int Level
        {
            get
            {
                return (int)Math.Log(index, 2) + 1;
            }
        }

        public ArrayBinaryTree(T value)
            : this(value, 10240)
        {
        }

        public ArrayBinaryTree(T value, int capacity)
            : this(value, new SharedData<T>(), 1)
        {
            this.data.Array = new ArrayBinaryTree<T>[capacity];
            this.data.Array[1] = this;
        }

        public ArrayBinaryTree(T value, SharedData<T> data, int index)
            : base(value)
        {
            this.data = data;
            this.depth = 1;
            this.count = 1;
            this.index = index;
        }

        public override void AddLeft(T value)
        {
            Add(leftIndex, value);
        }

        public override void AddRight(T value)
        {
            Add(rightIndex, value);
        }

        public override void AddLeft(BinaryTree<T> tree)
        {
            Add(leftIndex, tree);
        }

        public override void AddRight(BinaryTree<T> tree)
        {
            Add(rightIndex, tree);
        }

        protected void Add(int index, T value)
        {
            Add(index, new ArrayBinaryTree<T>(value, data, index));
        }

        protected void Add(int index, BinaryTree<T> tree)
        {
            if (index >= data.Array.Length)
                ExtendArray();
            if (data.Array[index] != null)
                throw new Exception("Child is existed");
            ArrayBinaryTree<T> tmpTree = tree as ArrayBinaryTree<T>;
            if (tmpTree == null)
            {
                tmpTree = new ArrayBinaryTree<T>(tree.Value);
                BinaryTree<T>.Copy(tree, tmpTree);
            }

            data.Array[index] = tmpTree;
            if (depth == 1)
            {
                depth = 2;
                BubbleDepth();
            }
            ++count;
            BubbleCount(1);
        }

        public override void Remove()
        {
            int i = parentIndex;
            RecursiveRemove();
            if (data.Array[i] == null)
                return;
            if (Depth + 1 == data.Array[i].Depth)
            {
                ArrayBinaryTree<T> sibling = index % 2 == 0 ? data.Array[index + 1] : data.Array[index - 1];
                if (sibling == null || sibling.Depth < Depth)
                    data.Array[i].UpdateDepth();
            }
            data.Array[i].count -= count;
            data.Array[i].BubbleCount(-count);
        }

        protected void RecursiveRemove()
        {
            int li = leftIndex;
            int ri = rightIndex;
            data.Array[index] = null;
            if (li < data.Array.Length && data.Array[li] != null)
                data.Array[li].RecursiveRemove();
            if (ri < data.Array.Length && data.Array[ri] != null)
                data.Array[ri].RecursiveRemove();
        }

        public override BinaryTree<T> Clone()
        {
            if (index == 1)
            {
                SharedData<T> cloneData = new SharedData<T>();
                cloneData.Array = new ArrayBinaryTree<T>[data.Array.Length];
                for (int i = 1; i < data.Array.Length; ++i)
                    if (data.Array[i] != null)
                    {
                        cloneData.Array[i] = new ArrayBinaryTree<T>(data.Array[i].Value, cloneData, i);
                        cloneData.Array[i].count = data.Array[i].count;
                        cloneData.Array[i].depth = data.Array[i].depth;
                    }
                return cloneData.Array[1];
            }
            else
            {
                ArrayBinaryTree<T> cloneTree = new ArrayBinaryTree<T>(this.Value);
                BinaryTree<T>.Copy(this, cloneTree);
                return cloneTree;
            }
        }

        protected void BubbleDepth()
        {
            ArrayBinaryTree<T> current = this;
            int i = current.parentIndex;
            while (data.Array[i] != null)
            {
                if (current.depth < data.Array[i].depth)
                    break;

                data.Array[i].depth = current.depth + 1;
                current = data.Array[i];
                i = current.parentIndex;
            }
        }

        protected void UpdateDepth()
        {
            ArrayBinaryTree<T> current = this;
            int li, ri, pi, tmpDepth = current.depth;
            do
            {
                li = current.leftIndex;
                ri = current.rightIndex;
                pi = current.parentIndex;
                tmpDepth = current.depth;
                current.depth = 1;

                if (data.Array[li] != null)
                    current.depth = data.Array[li].depth + 1;
                if (data.Array[ri] != null && data.Array[ri].depth + 1 > current.depth)
                    current.depth = data.Array[ri].depth + 1;

                if (tmpDepth == current.depth || data.Array[pi] == null)
                    break;

                current = data.Array[pi];
            } while (tmpDepth + 1 == current.depth);
        }

        protected void BubbleCount(int diff)
        {
            ArrayBinaryTree<T> current = this;
            int i = current.parentIndex;
            while (data.Array[i] != null)
            {
                data.Array[i].count += diff;
                current = data.Array[i];
                i = current.parentIndex;
            }
        }

        protected void ExtendArray()
        {
            ArrayBinaryTree<T>[] newArray = new ArrayBinaryTree<T>[data.Array.Length * 2];
            Array.Copy(data.Array, newArray, data.Array.Length);
            data.Array = newArray;
        }
    }
}

Java

抽象類別

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
public abstract class BinaryTree<T> {
    protected T value;
    public T getValue()
    {
        return value;
    }
    public void setValue(T value)
    {
        this.value = value;
    }

    public abstract int size();
    public abstract int depth();
    public abstract BinaryTree<T> parent();
    public abstract BinaryTree<T> left();
    public abstract BinaryTree<T> right();
    public abstract int level();

    public BinaryTree(T value)
    {
        this.value = value;
    }

    public abstract void addLeft(T value) throws Exception;
    public abstract void addRight(T value) throws Exception;
    public abstract void addLeft(BinaryTree<T> tree) throws Exception;
    public abstract void addRight(BinaryTree<T> tree) throws Exception;
    public abstract void remove();
    public abstract BinaryTree<T> copy() throws Exception;

    public static<T> void copy(BinaryTree<T> srcTree, BinaryTree<T> destTree) throws Exception
    {
        if (srcTree.left() != null)
        {
            destTree.addLeft(srcTree.left().getValue());
            copy(srcTree.left(), destTree.left());
        }
        if (srcTree.right() != null)
        {
            destTree.addRight(srcTree.right().getValue());
            copy(srcTree.right(), destTree.right());
        }
    }
}

連結串列

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
public class LinkedBinaryTree<T> extends BinaryTree<T> {
    protected int size;
    @Override
    public int size() {
        // TODO Auto-generated method stub
        return size;
    }

    protected int depth;
    @Override
    public int depth() {
        // TODO Auto-generated method stub
        return depth;
    }

    protected LinkedBinaryTree<T> parent;
    @Override
    public BinaryTree<T> parent() {
        // TODO Auto-generated method stub
        return parent;
    }

    protected LinkedBinaryTree<T> left;
    @Override
    public BinaryTree<T> left() {
        // TODO Auto-generated method stub
        return left;
    }

    protected LinkedBinaryTree<T> right;
    @Override
    public BinaryTree<T> right() {
        // TODO Auto-generated method stub
        return right;
    }

    protected int level;
    @Override
    public int level() {
        // TODO Auto-generated method stub
        return level;
    }

    public LinkedBinaryTree(T value)
    {
        super(value);
        size = 1;
        depth = 1;
        level = 1;
    }

    @Override
    public void addLeft(T value) throws Exception {
        add(true, value);
    }

    @Override
    public void addRight(T value) throws Exception {
        add(false, value);
    }

    @Override
    public void addLeft(BinaryTree<T> tree) throws Exception {
        add(true, tree);
    }

    @Override
    public void addRight(BinaryTree<T> tree) throws Exception {
        add(false, tree);
    }

    protected void add(boolean isLeft, T value) throws Exception {
        add(isLeft, new LinkedBinaryTree<T>(value));
    }

    protected void add(boolean isLeft, BinaryTree<T> tree) throws Exception {
        LinkedBinaryTree<T> tmpTree = null;
        if(tree instanceof  LinkedBinaryTree)
            tmpTree = (LinkedBinaryTree<T>)tree;
        else
        {
            tmpTree = new LinkedBinaryTree<T>(tree.getValue());
            BinaryTree.copy(tree, tmpTree);
        }
        if(isLeft)
        {
            if (left != null)
                throw new Exception("Child is existed");
            left = tmpTree;
            left.level = level + 1;
            left.parent = this;
        }
        else
        {
            if (right != null)
                throw new Exception("Child is existed");
            right = tmpTree;
            right.level = level + 1;
            right.parent = this;
        }
        if (depth == 1)
        {
            depth = 2;
            bubbleDepth();
        }
        ++size;
        bubbleCount(1);
    }

    @Override
    public void remove() {
        // TODO Auto-generated method stub
        LinkedBinaryTree<T> sibling;
        if (parent == null)
            return;
        else if (parent.left == this)
        {
            parent.left = null;
            sibling = parent.right;
        }
        else if (parent.right == this)
        {
            parent.right = null;
            sibling = parent.left;
        }
        else
            return;

        if (depth + 1 == parent.depth)
        {
            if (sibling == null || sibling.depth < depth)
                parent.updateDepth();
        }
        parent.size -= size;
        parent.bubbleCount(-size);
        parent = null;
    }

    @Override
    public BinaryTree<T> copy() throws Exception {
        // TODO Auto-generated method stub
        LinkedBinaryTree<T> cloneTree = new LinkedBinaryTree<T>(this.getValue());
        if (this.parent == null)
        {
            cloneTree.size = this.size;
            cloneTree.depth = this.depth;
            cloneTree.level = this.level;
            cloneTree.left = (LinkedBinaryTree<T>)this.left.copy();
            cloneTree.right = (LinkedBinaryTree<T>)this.right.copy();
            cloneTree.left.parent = cloneTree;
            cloneTree.right.parent = cloneTree;
        }
        else
            BinaryTree.copy(this, cloneTree);
        return cloneTree;
    }

    protected void bubbleDepth()
    {
        if (parent == null)
            return;

        if (depth + 1 > parent.depth)
        {
            parent.depth = depth + 1;
            parent.bubbleDepth();
        }
    }

    protected void updateDepth()
    {
        int tmpDepth = depth;
        depth = 1;

        if (left != null)
            depth = left.depth + 1;
        if (right != null && right.depth + 1 > depth)
            depth = right.depth + 1;

        if (tmpDepth == depth || parent == null)
            return;
        if (tmpDepth + 1 == parent.depth)
            parent.updateDepth();
    }

    protected void bubbleCount(int diff)
    {
        if (parent == null)
            return;

        parent.size += diff;
        parent.bubbleCount(diff);
    }
}

陣列

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
public class ArrayBinaryTree<T> extends BinaryTree<T> {
    public static class SharedData<S>
    {
        public ArrayBinaryTree<S>[] array;
    }

    protected SharedData<T> data;

    protected int index;

    protected int parentIndex() {
        return  index / 2;
    }

    protected int leftIndex() {
        return  index * 2;
    }

    protected int rightIndex() {
        return index * 2 + 1;
    }

    protected int size;
    @Override
    public int size() {
        // TODO Auto-generated method stub
        return size;
    }

    protected int depth;
    @Override
    public int depth() {
        // TODO Auto-generated method stub
        return depth;
    }

    @Override
    public BinaryTree<T> parent() {
        // TODO Auto-generated method stub
        return data.array[parentIndex()];
    }

    @Override
    public BinaryTree<T> left() {
        // TODO Auto-generated method stub
        int i = leftIndex();
        if (i < data.array.length)
            return data.array[i];
        else
            return null;
    }

    @Override
    public BinaryTree<T> right() {
        // TODO Auto-generated method stub
        int i = rightIndex();
        if (i < data.array.length)
            return data.array[i];
        else
            return null;
    }

    @Override
    public int level() {
        // TODO Auto-generated method stub
        return (int)(Math.log(index) / Math.log(2)) + 1;
    }

    public ArrayBinaryTree(T value)
    {
        this(value, 10240);
    }

    @SuppressWarnings("unchecked")
    public ArrayBinaryTree(T value, int capacity)
    {
        this(value, new SharedData<T>(), 1);
        this.data.array = (ArrayBinaryTree<T>[])new ArrayBinaryTree[capacity];
        this.data.array[1] = this;
    }

    public ArrayBinaryTree(T value, SharedData<T> data, int index)
    {
        super(value);
        this.data = data;
        this.depth = 1;
        this.size = 1;
        this.index = index;
    }

    @Override
    public void addLeft(T value) throws Exception {
        // TODO Auto-generated method stub
        add(leftIndex(), value);
    }

    @Override
    public void addRight(T value) throws Exception {
        // TODO Auto-generated method stub
        add(rightIndex(), value);
    }

    @Override
    public void addLeft(BinaryTree<T> tree) throws Exception {
        // TODO Auto-generated method stub
        add(leftIndex(), tree);
    }

    @Override
    public void addRight(BinaryTree<T> tree) throws Exception {
        // TODO Auto-generated method stub
        add(rightIndex(), tree);
    }

    protected void add(int index, T value) throws Exception
    {
        add(index, new ArrayBinaryTree<T>(value, data, index));
    }

    protected void add(int index, BinaryTree<T> tree) throws Exception
    {
        if (index >= data.array.length)
            extendArray();
        if (data.array[index] != null)
            throw new Exception("Child is existed");
        ArrayBinaryTree<T> tmpTree = null;
        if(tree instanceof  ArrayBinaryTree)
            tmpTree = (ArrayBinaryTree<T>)tree;
        else
        {
            tmpTree = new ArrayBinaryTree<T>(tree.getValue(), data, index);
            BinaryTree.copy(tree, tmpTree);
        }
        data.array[index] = tmpTree;
        if (depth == 1)
        {
            depth = 2;
            bubbleDepth();
        }
        ++size;
        bubbleCount(1);
    }

    @Override
    public void remove() {
        // TODO Auto-generated method stub
        int i = parentIndex();
        recursiveRemove();
        if (data.array[i] == null)
            return;
        if (depth + 1 == data.array[i].depth)
        {
            ArrayBinaryTree<T> sibling = index % 2 == 0 ? data.array[index + 1] : data.array[index - 1];
            if (sibling == null || sibling.depth < depth)
                data.array[i].updateDepth();
        }
        data.array[i].size -= size;
        data.array[i].bubbleCount(-size);
    }

    protected void recursiveRemove()
    {
        int li = leftIndex();
        int ri = rightIndex();
        data.array[index] = null;
        if (li < data.array.length && data.array[li] != null)
            data.array[li].recursiveRemove();
        if (ri < data.array.length && data.array[ri] != null)
            data.array[ri].recursiveRemove();
    }

    @SuppressWarnings("unchecked")
    @Override
    public BinaryTree<T> copy() throws Exception
    {
        if (index == 1)
        {
            SharedData<T> cloneData = new SharedData<T>();
            cloneData.array = (ArrayBinaryTree<T>[])new ArrayBinaryTree[data.array.length];
            for (int i = 1; i < data.array.length; ++i)
                if (data.array[i] != null)
                {
                    cloneData.array[i] = new ArrayBinaryTree<T>(data.array[i].getValue(), cloneData, i);
                    cloneData.array[i].size = data.array[i].size;
                    cloneData.array[i].depth = data.array[i].depth;
                }
            return cloneData.array[1];
        }
        else
        {
            ArrayBinaryTree<T> cloneTree = new ArrayBinaryTree<T>(this.getValue());
            BinaryTree.copy(this, cloneTree);
            return cloneTree;
        }
    }

    protected void bubbleDepth()
    {
        ArrayBinaryTree<T> current = this;
        int i = current.parentIndex();
        while (data.array[i] != null)
        {
            if (current.depth < data.array[i].depth)
                break;

            data.array[i].depth = current.depth + 1;
            current = data.array[i];
            i = current.parentIndex();
        }
    }

    protected void updateDepth()
    {
        ArrayBinaryTree<T> current = this;
        int li, ri, pi, tmpDepth = current.depth;
        do
        {
            li = current.leftIndex();
            ri = current.rightIndex();
            pi = current.parentIndex();
            tmpDepth = current.depth;
            current.depth = 1;

            if (data.array[li] != null)
                current.depth = data.array[li].depth + 1;
            if (data.array[ri] != null && data.array[ri].depth + 1 > current.depth)
                current.depth = data.array[ri].depth + 1;

            if (tmpDepth == current.depth || data.array[pi] == null)
                break;

            current = data.array[pi];
        } while (tmpDepth + 1 == current.depth);
    }

    protected void bubbleCount(int diff)
    {
        ArrayBinaryTree<T> current = this;
        int i = current.parentIndex();
        while (data.array[i] != null)
        {
            data.array[i].size += diff;
            current = data.array[i];
            i = current.parentIndex();
        }
    }

    @SuppressWarnings("unchecked")
    protected void extendArray() {
        ArrayBinaryTree<T>[] newArray = (ArrayBinaryTree<T>[])new ArrayBinaryTree[data.array.length * 2];
        System.arraycopy(data.array, 0, newArray, 0, data.array.length);
        data.array = newArray;
    }
}

C++

抽象類別

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
#ifndef BINARYTREE_H
#define BINARYTREE_H

template<typename T>
class BinaryTree
{
    public:
        BinaryTree(T value)
        {
            this->value = value;
        }
        virtual ~BinaryTree() {}

        T getValue()
        {
            return value;
        }
        void setValue(T value)
        {
            this.value = value;
        }

        virtual int size() = 0;
        virtual int depth() = 0;
        virtual BinaryTree<T>* parent() = 0;
        virtual BinaryTree<T>* left() = 0;
        virtual BinaryTree<T>* right() = 0;
        virtual int level() = 0;

        virtual void addLeft(T value) = 0;
        virtual void addRight(T value) = 0;
        virtual void addLeft(BinaryTree<T>* tree) = 0;
        virtual void addRight(BinaryTree<T>* tree) = 0;
        virtual void remove() = 0;
        virtual BinaryTree<T>* clone() = 0;

        static void copy(BinaryTree<T>* srcTree, BinaryTree<T>* destTree)
        {
            if (srcTree->left() != 0)
            {
                destTree->addLeft(srcTree->left()->getValue());
                copy(srcTree->left(), destTree->left());
            }
            if (srcTree->right() != 0)
            {
                destTree->addRight(srcTree->right()->getValue());
                copy(srcTree->right(), destTree->right());
            }
        }
    protected:
        T value;
    private:
};

#endif // BINARYTREE_H

連結串列

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#ifndef LINKEDBINARYTREE_H
#define LINKEDBINARYTREE_H

#include "BinaryTree.h"

template<typename T>
class LinkedBinaryTree : public BinaryTree<T>
{
    public:
        LinkedBinaryTree(T value) : BinaryTree<T>(value)
        {
            _size = 1;
            _depth = 1;
            _level = 1;
            _parent = 0;
            _left = 0;
            _right = 0;
        }

        virtual ~LinkedBinaryTree()
        {
            delete _left;
            delete _right;
        }

        int size()
        {
            return _size;
        }

        int depth()
        {
            return _depth;
        }

        BinaryTree<T>* parent()
        {
            return _parent;
        }

        BinaryTree<T>* left()
        {
            return _left;
        }

        BinaryTree<T>* right()
        {
            return _right;
        }

        int level()
        {
            return _level;
        }

        void addLeft(T value)
        {
            add(_left, value);
        }

        void addRight(T value)
        {
            add(_right, value);
        }

        void addLeft(BinaryTree<T>* tree)
        {
            add(_left, tree);
        }

        void addRight(BinaryTree<T>* tree)
        {
            add(_right, tree);
        }

        void remove()
        {
            LinkedBinaryTree<T>* sibling;
            if (_parent == 0)
                return;
            else if (_parent->_left == this)
            {
                _parent->_left = 0;
                sibling = _parent->_right;
            }
            else if (_parent->_right == this)
            {
                _parent->_right = 0;
                sibling = _parent->_left;
            }
            else
                return;

            if (_depth + 1 == _parent->_depth)
            {
                if (sibling == 0 || sibling->_depth < _depth)
                    _parent->updateDepth();
            }
            _parent->_size -= _size;
            _parent->bubbleCount(-_size);
            _parent = 0;
            delete this;
        }

        BinaryTree<T>* clone()
        {
            LinkedBinaryTree<T>* cloneTree = new LinkedBinaryTree<T>(this->getValue());
            if (this->_parent == 0)
            {
                cloneTree->_size = this->_size;
                cloneTree->_depth = this->_depth;
                cloneTree->_level = this->_level;
                cloneTree->_left = (LinkedBinaryTree<T>*)this->_left->clone();
                cloneTree->_right = (LinkedBinaryTree<T>*)this->_right->clone();
                cloneTree->_left->_parent = cloneTree;
                cloneTree->_right->_parent = cloneTree;
            }
            else
                BinaryTree<T>::copy(this, cloneTree);
            return cloneTree;
        }
    protected:
        int _size;
        int _depth;
        int _level;
        LinkedBinaryTree<T>* _parent;
        LinkedBinaryTree<T>* _left;
        LinkedBinaryTree<T>* _right;

        void add(LinkedBinaryTree<T>* &node, T value)
        {
            add(node, new LinkedBinaryTree<T>(value));
        }

        void add(LinkedBinaryTree<T>* &node, BinaryTree<T>* tree)
        {
            if (node != 0)
                throw "Child is existed";
            LinkedBinaryTree<T>* tmpTree = dynamic_cast<LinkedBinaryTree<T>*>(tree);
            if(tmpTree == 0)
            {
                tmpTree = new LinkedBinaryTree<T>(tree->getValue());
                BinaryTree<T>::copy(tree, tmpTree);
            }
            node = tmpTree;
            node->_level = _level + 1;
            node->_parent = this;
            if (_depth == 1)
            {
                _depth = 2;
                bubbleDepth();
            }
            ++_size;
            bubbleCount(1);
        }

        void bubbleDepth()
        {
            if (_parent == 0)
                return;

            if (_depth + 1 > _parent->_depth)
            {
                _parent->_depth = _depth + 1;
                _parent->bubbleDepth();
            }
        }

        void updateDepth()
        {
            int tmpDepth = _depth;
            _depth = 1;

            if (_left != 0)
                _depth = _left->_depth + 1;
            if (_right != 0 && _right->_depth + 1 > _depth)
                _depth = _right->_depth + 1;

            if (tmpDepth == _depth || _parent == 0)
                return;
            if (tmpDepth + 1 == _parent->_depth)
                _parent->updateDepth();
        }

        void bubbleCount(int diff)
        {
            if (_parent == 0)
                return;

            _parent->_size += diff;
            _parent->bubbleCount(diff);
        }
    private:
};

#endif // LINKEDBINARYTREE_H

陣列

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
#ifndef ARRAYBINARYTREE_H
#define ARRAYBINARYTREE_H

#include <memory.h>
#include <cmath>
#include "BinaryTree.h"

using namespace std;

template<typename T>
class SharedData;

template<typename T>
class ArrayBinaryTree : public BinaryTree<T>
{
    public:
        ArrayBinaryTree(T value, int capacity = 10240) : BinaryTree<T>(value)
        {
            init(new SharedData<T>(), 1);
            data->array = new ArrayBinaryTree<T>*[capacity];
            for(int i = 0;i < capacity;++i)
                data->array[i] = 0;
            data->array[1] = this;
            data->arrayLength = capacity;
        }

        ArrayBinaryTree(T value, SharedData<T>* data, int index) : BinaryTree<T>(value)
        {
            init(data, index);
        }

        virtual ~ArrayBinaryTree()
        {
            if(index == 1)
                delete data;
        }

        int size()
        {
            return _size;
        }

        int depth()
        {
            return _depth;
        }

        BinaryTree<T>* parent()
        {
            return data->array[parentIndex()];
        }

        BinaryTree<T>* left()
        {
            int i = leftIndex();
            if (i < data->arrayLength)
                return data->array[i];
            else
                return 0;
        }

        BinaryTree<T>* right()
        {
            int i = rightIndex();
            if (i < data->arrayLength)
                return data->array[i];
            else
                return 0;
        }

        int level()
        {
            return (int)log2(index) + 1;
        }

        void addLeft(T value)
        {
            add(leftIndex(), value);
        }

        void addRight(T value)
        {
            add(rightIndex(), value);
        }

        void addLeft(BinaryTree<T>* tree)
        {
            add(leftIndex(), tree);
        }

        void addRight(BinaryTree<T>* tree)
        {
            add(rightIndex(), tree);
        }

        void remove()
        {
            int i = parentIndex();
            recursiveRemove();
            if (data->array[i] == 0)
                return;
            if (_depth + 1 == data->array[i]->_depth)
            {
                ArrayBinaryTree<T>* sibling = index % 2 == 0 ? data->array[index + 1] : data->array[index - 1];
                if (sibling == 0 || sibling->_depth < _depth)
                    data->array[i]->updateDepth();
            }
            data->array[i]->_size -= _size;
            data->array[i]->bubbleCount(-_size);
        }

        BinaryTree<T>* clone()
        {
            if (index == 1)
            {
                SharedData<T>* cloneData = new SharedData<T>();
                cloneData->array = new ArrayBinaryTree*[data->arrayLength];
                cloneData->arrayLength = data->arrayLength;
                for (int i = 0; i < data->arrayLength; ++i)
                    if (data->array[i] != 0)
                    {
                        cloneData->array[i] = new ArrayBinaryTree<T>(data->array[i]->getValue(), cloneData, i);
                        cloneData->array[i]->_size = data->array[i]->_size;
                        cloneData->array[i]->_depth = data->array[i]->_depth;
                    }
                    else
                        cloneData->array[i] = 0;
                return cloneData->array[1];
            }
            else
            {
                ArrayBinaryTree<T>* cloneTree = new ArrayBinaryTree<T>(this->getValue());
                BinaryTree<T>::copy(this, cloneTree);
                return cloneTree;
            }
        }
    protected:
        SharedData<T>* data;
        int index;
        int _size;
        int _depth;

        void init(SharedData<T>* data, int index)
        {
            this->data = data;
            _depth = 1;
            _size = 1;
            this->index = index;
        }


        int parentIndex()
        {
            return  index / 2;
        }

        int leftIndex()
        {
            return  index * 2;
        }

        int rightIndex()
        {
            return index * 2 + 1;
        }

        void add(int index, T value)
        {
            add(index, new ArrayBinaryTree<T>(value, data, index));
        }

        void add(int index, BinaryTree<T>* tree)
        {
            if (index >= data->arrayLength)
                extendArray();
            if (data->array[index] != 0)
                throw "Child is existed";
            ArrayBinaryTree<T>* tmpTree = dynamic_cast<ArrayBinaryTree<T>*>(tree);
            if(tmpTree == 0)
            {
                tmpTree = new ArrayBinaryTree<T>(tree->getValue(), data, index);
                BinaryTree<T>::copy(tree, tmpTree);
            }
            data->array[index] = tmpTree;
            if (_depth == 1)
            {
                _depth = 2;
                bubbleDepth();
            }
            ++_size;
            bubbleCount(1);
        }

        void recursiveRemove()
        {
            int li = leftIndex();
            int ri = rightIndex();
            data->array[index] = 0;
            if (li < data->arrayLength && data->array[li] != 0)
                data->array[li]->recursiveRemove();
            if (ri < data->arrayLength && data->array[ri] != 0)
                data->array[ri]->recursiveRemove();
            delete data->array[index];
        }

        void bubbleDepth()
        {
            ArrayBinaryTree<T>* current = this;
            int i = current->parentIndex();
            while (data->array[i] != 0)
            {
                if (current->_depth < data->array[i]->_depth)
                    break;

                data->array[i]->_depth = current->_depth + 1;
                current = data->array[i];
                i = current->parentIndex();
            }
        }

        void updateDepth()
        {
            ArrayBinaryTree<T>* current = this;
            int li, ri, pi, tmpDepth = current->_depth;
            do
            {
                li = current->leftIndex();
                ri = current->rightIndex();
                pi = current->parentIndex();
                tmpDepth = current->_depth;
                current->_depth = 1;

                if (data->array[li] != 0)
                    current->_depth = data->array[li]->_depth + 1;
                if (data->array[ri] != 0 && data->array[ri]->_depth + 1 > current->_depth)
                    current->_depth = data->array[ri]->_depth + 1;

                if (tmpDepth == current->_depth || data->array[pi] == 0)
                    break;

                current = data->array[pi];
            } while (tmpDepth + 1 == current->_depth);
        }

        void bubbleCount(int diff)
        {
            ArrayBinaryTree<T>* current = this;
            int i = current->parentIndex();
            while (data->array[i] != 0)
            {
                data->array[i]->_size += diff;
                current = data->array[i];
                i = current->parentIndex();
            }
        }

        void extendArray()
        {
            int newLength = data->arrayLength * 2;
            ArrayBinaryTree<T>** newArray = new ArrayBinaryTree<T>*[newLength];
            memcpy(newArray, data->array, data->arrayLength * sizeof(ArrayBinaryTree<T>*));
            delete [] data->array;
            data->array = newArray;
            for(int i = data->arrayLength;i < newLength;++i)
                data->array[i] = 0;
            data->arrayLength *= 2;
        }
    private:
};

template<typename T>
class SharedData
{
    public:
        virtual ~SharedData()
        {
            for(int i = 2;i < arrayLength;++i)
                delete array[i];
            delete [] array;
        }
        int arrayLength;
        ArrayBinaryTree<T>** array;
    protected:
    private:
};

#endif // ARRAYBINARYTREE_H

隨機建立十幾萬個節點，與刪除隨機一半的節點比較：

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
C#
Ready to build tree with 137784 nodes.
Ready to remove 77086 nodes from tree

Build ArrayBinaryTree Time: 140ms
Memory uage: 24788788bytes
Traverse ArrayBinaryTree Time: 20ms
Remove ArrayBinaryTree Time: 30ms

Build LinkedBinaryTree Time: 60ms
Memory uage: 4960188bytes
Traverse LinkedBinaryTree Time: 0ms
Remove LinkedBinaryTree Time: 20ms

Java
Ready to build tree with 137696 nodes.
Ready to remove 76944 nodes from tree

Build ArrayBinaryTree Time: 180ms
Memory uage: 426552bytes
Traverse ArrayBinaryTree Time: 10ms
Remove ArrayBinaryTree Time: 40ms

Build LinkedBinaryTree Time: 100ms
Memory uage: 5418600bytes
Traverse LinkedBinaryTree Time: 10ms
Remove LinkedBinaryTree Time: 40ms

C++
Ready to build tree with 141311 nodes.
Ready to remove 78765 nodes from tree.

Build ArrayBinaryTree Time: 110ms
Traverse ArrayBinaryTree Time: 0ms
Remove ArrayBinaryTree Time: 830ms

Build LinkedBinaryTree Time: 80ms
Traverse LinkedBinaryTree Time: 10ms
Remove LinkedBinaryTree Time: 740ms

延伸閱讀

樹 (Tree)
二元搜索樹 (Binary Search Tree)
一般樹轉二元樹
樹的走訪 (Tree Traversal)