簡介

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

IGEIS_CinqueTerre_tree-72  

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

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

orgpic   

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

定義

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

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

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

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

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

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

tree  

上圖藍色線段的部分是符合樹的條件,而紅色的線段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表示。

以下面的樹為例子:

tree2  

根節點: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#

抽象類別

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();
        }
    }
}

連結串列

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

抽象類別

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();
}
public abstract class TreeList<T> implements Iterable<Tree<T>> {
	public abstract int size();
}

連結串列

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();
        }
    }
}
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++

抽象類別

#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

連結串列

#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

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

相關樹種

二元樹(Binary Tree)

AVL樹(AVL Tree)

紅黑樹(Red-black Tree)

堆(Heap)

...

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()