簡介

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

定義

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

complete_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]的位置開始,公式如下:

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

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

Level = floor(log

2

(index) + 1)

如下圖所示:

 binary_tree_index  

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

語法

C#

抽象類別

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

連結串列

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

陣列

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

抽象類別

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

}

連結串列

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

陣列

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++

抽象類別

#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

連結串列

#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

陣列

#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

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

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

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

延伸閱讀

二元搜索樹(Binary Search Tree)

文章標籤
創作者介紹

小殘的程式光廊

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