簡介

樹 (Tree) 是一種常見的資料結構，他是一種階層式 (Hierarchical) 的資料集合，我們就先來看看下面這棵樹：
樹

我們觀察這棵樹之後可以發現他由某些東西組成，包含樹葉、樹枝和樹幹；同樣地，在程式世界裡有著類似的對應，樹的最開始會有一個根節點，就像樹的樹根一樣，所有的資料都是由這裡開始發展，接著會有一些其他的節點，有些節點可能在最末端，稱之為葉節點，就像樹的樹葉一樣，其他的節點則像樹的樹枝一樣。

不過在程式世界裡面，我們習慣把根節點放在最上面，而在我們生活中其實也很常使用，像是組織圖：
組織圖

上圖的區長為根節點，最下面的各單位則為葉節點。

定義

在數學的圖論和資料結構所提到的樹其實有些差異，在這裡先說明兩者的不同，數學中對樹的定義這裡簡化如下：

  • 圖中任兩點存在一條路經相通，但不存在環 (Cycle)。

不過在資料結構裡面所說的樹，指的是數學裡的有根樹 (Rooted tree)，定義如下：

  • 有一個特殊節點為根節點的樹。

在資料結構中的實作會有父節點和子節點的分別，所以可以進一步的定義：

  1. 樹存在一個為根節點，根節點沒有父節點 (不可以有迴圈)。
  2. 每個節點只有一個父節點 (子樹不交集)。
不是樹

上圖藍色線段的部分是符合樹的條件，而紅色的線段 C -> B 和 C -> E 違反了每個節點只有一個父節點，形成交集或連結；而線段 D -> A 則違反了必須存在一個根節點，形成了迴圈；而這兩點正是對應到數學的環。

在樹的資料結構中有一些專有名詞，解釋和定義如下：

  1. 根 (Root) 節點：沒有父節點的節點。
  2. 葉 (Leaf) 節點：沒有子節點的節點。或稱終端 (Terminal)、外部 (External) 或外 (Outer) 節點。
  3. 分枝 (Branch) 節點：有子節點的節點。或稱非終端 (Non-terminal)、內部 (Internal) 或內 (Inner) 節點。
  4. 子 (Child) 節點：一個節點的下一層節點。
  5. 父 (Parent) 節點：一個節點的上一層節點。
  6. 祖先 (Ancestor) 節點：從根節點到此節點路徑上的所有節點，不包含此節點。
  7. 兄弟 (Sibling) 節點：相同父節點的所有節點彼此稱為兄弟節點。
  8. 節點分支度 (Degree)；一個節點的子節點個數。
  9. 階層 (Level)：若某節點之父節點的階層為 n，則該節點階層為 n + 1，且根節點階層為 1。
  10. 樹分支度：樹當中節點分支度最大值。
  11. 深度 (Depth)：樹當中節點階層最大值。或稱高度 (Height)。
  12. 森林 (Forest)：許多不相交的樹可組成森林。
  13. K元樹 (K-ary tree)：一個樹的節點之子節點都不超過 K 個，稱為K元樹，例如 K = 2 為二元樹。K為變數，也常用 N 表示。

以下面的樹為例子：
樹

根節點：A
葉節點：DEGH
分支節點：ABCF
A的子節點：BC
B的子節點：DEF
…
C的父節點：A
D的父節點：B
…
H的祖先節點：ABF
G的祖先節點：AC
…
E的兄弟節點：DF
B的兄弟節點：C
…
B的分支度：3
H的分支度：0
…
樹的分支度：3
樹的深度：4

實作

由於樹的用途相當多變，所以實作的介面和方式也不同，這裡實作一種類型，介面如下：

  1. parent：取得父節點。
  2. children：取得子節點。
  3. add：加入子節點。
  4. remove：移除節點。
  5. clone：複製樹。
  6. level：節點的階層。
  7. depth：樹的深度。
  8. degree：取得分支度。
  9. size：子樹的節點個數。

連結串列

實作上可以用連結串列完成，本文簡單利用一個參考指向父節點，同時搭配內建的連結串列表示子節點來實作。除了連結串列之外也可使用其他的資料集合來取代，例如動態陣列等。

語法

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 Tree
{
    public abstract class Tree<T>
    {
        public T Value { get; set; }

        public abstract Tree<T> Parent { get; }
        public abstract TreeList<T> Children { get; }
        public abstract int Count { get; }
        public abstract int Degree { get; }
        public abstract int Depth { get; }
        public abstract int Level { get; }

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

        public abstract void Add(T value);
        public abstract void Add(Tree<T> tree);
        public abstract void Remove();
        public abstract Tree<T> Clone();
    }

    public abstract class TreeList<T> : IEnumerable<Tree<T>>
    {
        public abstract int Count { get; }
        public abstract IEnumerator<Tree<T>> GetEnumerator();

        IEnumerator<Tree<T>> IEnumerable<Tree<T>>.GetEnumerator()
        {
            return GetEnumerator();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}

連結串列

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

namespace Tree
{
    public class LinkedTree<T> : Tree<T>
    {
        protected LinkedList<LinkedTree<T>> childrenList;

        protected LinkedTree<T> parent;
        public override Tree<T> Parent
        {
            get
            {
                return parent;
            }
        }

        protected LinkedTreeList<T> children;
        public override TreeList<T> Children
        {
            get
            {
                return children;
            }
        }

        public override int Degree
        {
            get
            {
                return childrenList.Count;
            }
        }

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

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

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

        public LinkedTree(T value)
            : base(value)
        {
            childrenList = new LinkedList<LinkedTree<T>>();
            children = new LinkedTreeList<T>(childrenList);
            depth = 1;
            level = 1;
            count = 1;
        }

        public override void Add(T value)
        {
            Add(new LinkedTree<T>(value));
        }

        public override void Add(Tree<T> tree)
        {
            LinkedTree<T> gtree = (LinkedTree<T>)tree;
            if (gtree.Parent != null)
                gtree.Remove();
            gtree.parent = this;
            if (gtree.depth + 1 > depth)
            {
                depth = gtree.depth + 1;
                BubbleDepth();
            }
            gtree.level = level + 1;
            gtree.UpdateLevel();
            childrenList.AddLast(gtree);
            count += tree.Count;
            BubbleCount(tree.Count);
        }

        public override void Remove()
        {
            if (parent == null)
                return;
            parent.childrenList.Remove(this);
            if (depth + 1 == parent.depth)
                parent.UpdateDepth();
            parent.count -= count;
            parent.BubbleCount(-count);
            parent = null;
        }

        public override Tree<T> Clone()
        {
            return Clone(1);
        }

        protected LinkedTree<T> Clone(int level)
        {
            LinkedTree<T> cloneTree = new LinkedTree<T>(Value);
            cloneTree.depth = depth;
            cloneTree.level = level;
            cloneTree.count = count;
            foreach (LinkedTree<T> child in childrenList)
            {
                LinkedTree<T> cloneChild = child.Clone(level + 1);
                cloneChild.parent = cloneTree;
                cloneTree.childrenList.AddLast(cloneChild);
            }
            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;
            foreach (LinkedTree<T> child in childrenList)
                if (child.depth + 1 > depth)
                    depth = child.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);
        }

        protected void UpdateLevel()
        {
            int childLevel = level + 1;
            foreach (LinkedTree<T> child in childrenList)
            {
                child.level = childLevel;
                child.UpdateLevel();
            }
        }
    }

    public class LinkedTreeList<T> : TreeList<T>
    {
        protected LinkedList<LinkedTree<T>> list;

        public LinkedTreeList(LinkedList<LinkedTree<T>> list)
        {
            this.list = list;
        }

        public override int Count
        {
            get
            {
                return list.Count;
            }
        }

        public override IEnumerator<Tree<T>> GetEnumerator()
        {
            return list.GetEnumerator();
        }
    }
}

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

    public abstract Tree<T> parent();
    public abstract TreeList<T> children();
    public abstract int size();
    public abstract int depth();
    public abstract int degree();
    public abstract int level();

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

    public abstract void add(T value);
    public abstract void add(Tree<T> tree);
    public abstract void remove();
    public abstract Tree<T> copy();
}
1
2
3
public abstract class TreeList<T> implements Iterable<Tree<T>> {
    public abstract int size();
}

連結串列

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
import java.util.LinkedList;
import java.util.List;


public class LinkedTree<T> extends Tree<T> {
    protected List<LinkedTree<T>> childrenList;

    protected LinkedTree<T> parent;
    @Override
    public Tree<T> parent() {
        return parent;
    }

    protected TreeList<T> children;
    @Override
    public TreeList<T> children() {
        return children;
    }

    protected int size;
    @Override
    public int size() {
        return size;
    }

    protected int depth;
    @Override
    public int depth() {
        return depth;
    }

    @Override
    public int degree() {
        return childrenList.size();
    }

    protected int level;
    @Override
    public int level() {
        return level;
    }

    public LinkedTree(T value) {
        super(value);
        childrenList = new LinkedList<LinkedTree<T>>();
        children = new LinkedTreeList<T>(childrenList);
        depth = 1;
        level = 1;
        size = 1;
    }

    @Override
    public void add(T value) {
        add(new LinkedTree<T>(value));
    }

    @Override
    public void add(Tree<T> tree) {
        LinkedTree<T> gtree = (LinkedTree<T>)tree;
        if (gtree.parent != null)
            gtree.remove();
        gtree.parent = this;
        if (gtree.depth + 1 > depth)
        {
            depth = gtree.depth + 1;
            bubbleDepth();
        }
        gtree.level = level + 1;
        gtree.updateLevel();
        childrenList.add(gtree);
        size += gtree.size;
        bubbleCount(gtree.size);
    }

    @Override
    public void remove() {
        if (parent == null)
            return;
        parent.childrenList.remove(this);
        if (depth + 1 == parent.depth)
            parent.updateDepth();
        parent.size -= size;
        parent.bubbleCount(-size);
        parent = null;
    }

    @Override
    public Tree<T> copy() {
        return copy(1);
    }

    protected LinkedTree<T> copy(int level)
    {
        LinkedTree<T> cloneTree = new LinkedTree<T>(value);
        cloneTree.depth = depth;
        cloneTree.level = level;
        cloneTree.size = size;
        for (LinkedTree<T> child : childrenList)
        {
            LinkedTree<T> cloneChild = child.copy(level + 1);
            cloneChild.parent = cloneTree;
            cloneTree.childrenList.add(cloneChild);
        }
        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;
        for (LinkedTree<T> child : childrenList)
            if (child.depth + 1 > depth)
                depth = child.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);
    }

    protected void updateLevel()
    {
        int childLevel = level + 1;
        for (LinkedTree<T> child : childrenList)
        {
            child.level = childLevel;
            child.updateLevel();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Iterator;
import java.util.List;


public class LinkedTreeList<T> extends TreeList<T> {
    protected List<LinkedTree<T>> list;

    public LinkedTreeList(List<LinkedTree<T>> list)
    {
        this.list = list;
    }

    @Override
    public int size() {
        return list.size();
    }

    @SuppressWarnings("unchecked")
    @Override
    public Iterator<Tree<T>> iterator() {
        return (Iterator<Tree<T>>)((List<Tree<T>>)(List<?>)list).iterator();
    }
}

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

template<typename T>
class TreeList;

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

        T getValue()
        {
            return value;
        }
        void setValue(T value)
        {
            this.value = value;
        }
        virtual Tree<T>* parent() = 0;
        virtual TreeList<T>* children() = 0;
        virtual int level() = 0;
        virtual int size() = 0;
        virtual int depth() = 0;
        virtual int degree() = 0;
        virtual void add(T value) = 0;
        virtual void add(Tree<T>* tree) = 0;
        virtual void remove() = 0;
        virtual Tree<T>* clone() = 0;
    protected:
        T value;
    private:
};


template<typename T>
class TreeList
{
    public:
        TreeList() {}
        virtual ~TreeList() {}
        virtual int size() = 0;
        virtual void begin() = 0;
        virtual Tree<T>* next() = 0;
    protected:
    private:
};

#endif // TREE_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
#ifndef LINKEDTREE_H
#define LINKEDTREE_H

#include <list>

using namespace std;

template<typename T>
class LinkedTreeList;

template<typename T>
class LinkedTree : public Tree<T>
{
    public:
        LinkedTree(T value) : Tree<T>(value)
        {
            _children = new LinkedTreeList<T>(&_list);
            _parent = 0;
            _level = 1;
            _size = 1;
            _depth = 1;
        }
        virtual ~LinkedTree()
        {
            delete _children;
        }

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

        TreeList<T>* children()
        {
            return _children;
        }

        int level()
        {
            return _level;
        }

        int size()
        {
            return _size;
        }

        int depth()
        {
            return _depth;
        }

        int degree()
        {
            return _list.size();
        }

        void add(T value)
        {
            add(new LinkedTree<T>(value));
        }

        void add(Tree<T>* tree)
        {
            LinkedTree<T>* gtree = (LinkedTree<T>*)tree;
            if (gtree->_parent != 0)
                gtree->remove();
            gtree->_parent = this;
            if (gtree->_depth + 1 > _depth)
            {
                _depth = gtree->_depth + 1;
                bubbleDepth();
            }
            gtree->_level = _level + 1;
            gtree->updateLevel();
            _list.push_back(gtree);
            _size += gtree->_size;
            bubbleCount(gtree->_size);
        }

        void remove()
        {
            if (_parent == 0)
                return;
            for(typename list<LinkedTree<T>*>::iterator it = _parent->_list.begin();it != _list.end();++it)
            {
                LinkedTree<T>* child = *it;
                if(child == this)
                {
                    _parent->_list.erase(it);
                    break;
                }
            }
            if (_depth + 1 == _parent->_depth)
                _parent->updateDepth();
            _parent->_size -= _size;
            _parent->bubbleCount(-_size);
            _parent = 0;
        }

        Tree<T>* clone()
        {
            return clone(1);
        }
    protected:
        list<LinkedTree<T>*> _list;
        LinkedTreeList<T>* _children;
        LinkedTree<T>* _parent;
        int _level;
        int _size;
        int _depth;

        LinkedTree<T>* clone(int level)
        {
            LinkedTree<T>* cloneTree = new LinkedTree<T>(this->getValue());
            cloneTree->_depth = _depth;
            cloneTree->_level = level;
            cloneTree->_size = _size;
            for(typename list<LinkedTree<T>*>::iterator it = _list.begin();it != _list.end();++it)
            {
                LinkedTree<T>* child = *it;
                LinkedTree<T>* cloneChild = child->clone(level + 1);
                cloneChild->_parent = cloneTree;
                cloneTree->_list.push_back(cloneChild);
            }
            return cloneTree;
        }

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

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

        void updateDepth()
        {
            int tmpDepth = _depth;
            _depth = 1;
            for(typename list<LinkedTree<T>*>::iterator it = _list.begin();it != _list.end();++it)
            {
                LinkedTree<T>* child = *it;
                if (child->_depth + 1 > _depth)
                    _depth = child->_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);
        }

        void updateLevel()
        {
            int childLevel = _level + 1;
            for(typename list<LinkedTree<T>*>::iterator it = _list.begin();it != _list.end();++it)
            {
                LinkedTree<T>* child = *it;
                child->_level = childLevel;
                child->updateLevel();
            }
        }
    private:
};

template<typename T>
class LinkedTreeList : public TreeList<T>
{
    public:
        LinkedTreeList(list<LinkedTree<T>*>* list)
        {
            this->_list = list;
        }
        virtual ~LinkedTreeList()
        {
        }

        int size()
        {
            return _list->size();
        }

        void begin()
        {
            this->_iterator = _list->begin();
        }

        Tree<T>* next()
        {
            if(this->_iterator == this->_list->end())
                return 0;
            Tree<T>* tree = *this->_iterator;
            ++this->_iterator;
            return tree;
        }
    protected:
        list<LinkedTree<T>*>* _list;
        typename list<LinkedTree<T>*>::iterator _iterator;
    private:
};

#endif // LINKEDTREE_H

延伸閱讀

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