C#樹類型及其遍歷

2019-11-14 14:01:07

字體：大中小

來源：轉載

供稿：網友

最近有個項目不僅需要取部門的層級關系，還要處理不規則的關系（移除某個部門），只有樹結構才能實現相關遍歷和操作。

涉及到的知識點：泛型、遞歸、數據結構

既然研究樹類型就先來看下樹的定義：

一棵樹（tree）是由n（n>0）個元素組成的有限集合，其中：

（1）每個元素稱為結點（node）；

（2）有一個特定的結點，稱為根結點或根（root）；

（3）除根結點外，其余結點被分成m（m>=0）個互不相交的有限集合，而每個子集又都是一棵樹（稱為原樹的子樹）；——百度

本文將簡化樹，只研究樹的結點-結點樹。結點樹包含：父結點（根結點的父結點為null）、子結點（List集合）、數據對象。

類的設計：

public class BoTree<T>    {        public BoTree()        {            nodes = new List<BoTree<T>>();        }        public BoTree(T data)        {            this.Data = data;            nodes = new List<BoTree<T>>();        }        PRivate BoTree<T> parent;        /// <summary>        /// 父結點        /// </summary>        public BoTree<T> Parent        {            get { return parent; }        }        /// <summary>        /// 結點數據        /// </summary>        public T Data { get; set; }        private List<BoTree<T>> nodes;        /// <summary>        /// 子結點        /// </summary>        public List<BoTree<T>> Nodes        {            get { return nodes; }        }        /// <summary>        /// 添加結點        /// </summary>        /// <param name="node">結點</param>        public void AddNode(BoTree<T> node)        {            if (!nodes.Contains(node))            {                node.parent = this;                nodes.Add(node);            }        }        /// <summary>        /// 添加結點        /// </summary>        /// <param name="nodes">結點集合</param>        public void AddNode(List<BoTree<T>> nodes)        {            foreach (var node in nodes)            {                if (!nodes.Contains(node))                {                    node.parent = this;                    nodes.Add(node);                }            }        }        /// <summary>        /// 移除結點        /// </summary>        /// <param name="node"></param>        public void Remove(BoTree<T> node)        {            if (nodes.Contains(node))                nodes.Remove(node);        }        /// <summary>        /// 清空結點集合        /// </summary>        public void RemoveAll()        {            nodes.Clear();        }    }

測試：

首先創建一個學生類（任意）

public class Student    {        public Student(string name, string sex, int age)        {            this.Name = name;            this.Sex = sex;            this.Age = age;        }        public string Name { get; set; }        public string Sex { get; set; }        public int Age { get; set; }    }

初始化樹：

BoTree<Student> tree1 = new BoTree<Student>();tree1.Data = new Student("小波1", "男", 18);BoTree<Student> tree2 = new BoTree<Student>();tree2.Data = new Student("小波2", "男", 19);BoTree<Student> tree3 = new BoTree<Student>();tree3.Data = new Student("小波3", "男", 20);BoTree<Student> tree4 = new BoTree<Student>();tree4.Data = new Student("小波4", "男", 21);tree1.AddNode(tree2);tree1.AddNode(tree3);tree3.AddNode(tree4);

調試：

可以從監視中看出tree1有2個子結點

可以看出tree4的父結點為tree3

下面我們來遍歷這棵樹：

public static void Recursive(BoTree<Student> tree)        {            Console.WriteLine("姓名：{0}，姓名：{1}，年齡：{2}", tree.Data.Name, tree.Data.Sex, tree.Data.Age);            if (tree.Nodes.Count > 0)            {                foreach (var item in tree.Nodes)                {                    Recursive(item);                }            }        }