首页 > 代码库 > C#数据结构-树 data Structure Tree

C#数据结构-树 data Structure Tree

树(Tree)是n(n>=0)个相同类型的数据元素的有限集合。树中的数据元素叫结点(Node)。n=0的树称为空树(Empty Tree);对于n>0的任意非空树T有:

1.有且只有一个特殊的结点称为树的根(Root)结点,根没有前驱结点。

2.若n>1,则除根结点外,其余结点被分成了m(m>0)个互不相交的集合T1,T2,T3,...Tm,其中每个集合Ti(1<=i<=m)本身又是一棵树。树T1,T2,...Tm称为这棵树的子树(Subtree)。

由树的定义可知,树的定义是递归的,用树来定义树,因此,树的许多运算都使用过了递归。

树的相关术语

结点(Node)。表示树中的数据元素,由数据项和数据元素之间的关系组成。

结点的度。结点所拥有的子树的个数。

树的度。树中各结点度的最大值。

叶子结点。度为0的结点,也叫终端结点。

其他术语参考二叉树。

用多重链表表示法存储树

每个结点指针域的个数等于树的度数。


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DataStructure
{

    public interface ITree<T>
    {
        T Root();                                //求树的根结点
        T Parent(T t);                           //求结点t的双亲结点
        T Child(T t, int i);                     //求结点t的第i个子结点
        T RightSibling(T t);                     //求结点t第一个右边兄弟结点
        bool Insert(T s, T t, int i);            //将树s加入树中作为结点t的第i颗子树
        T Delete(T t, int i);                    //删除结点t的第i颗子树
        void Traverse(int TraverseType);         //按某种方式遍历树
        void Clear();                            //清空树
        bool IsEmpty();                          //判断是否为空
        int GetDepth(T t);                          //求树的深度
    }


    /// <summary>
    /// 循环顺序队列
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class CSeqQueue<T>
    {
        private int maxsize;       //循环顺序队列的容量
        private T[] data;          //数组,用于存储循环顺序队列中的数据元素
        private int front;         //指示最近一个已经离开队列的元素所占有的位置 循环顺序队列的对头
        private int rear;          //指示最近一个进入队列的元素的位置           循环顺序队列的队尾

        public T this[int index]
        {
            get { return data[index]; }
            set { data[index] = value; }
        }

        //容量属性
        public int Maxsize
        {
            get { return maxsize; }
            set { maxsize = value; }
        }

        //对头指示器属性
        public int Front
        {
            get { return front; }
            set { front = value; }
        }

        //队尾指示器属性
        public int Rear
        {
            get { return rear; }
            set { rear = value; }
        }

        public CSeqQueue()
        {

        }

        public CSeqQueue(int size)
        {
            data = http://www.mamicode.com/new T[size];>

C#数据结构-树 data Structure Tree