树结构

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

namespace DataList.Scrips.Tree
{
    //相同数据类型的数据元素的有限集合
    //1.有且仅有一个特殊的节点，叫跟节点,根节点没有前驱节点
    //2.除根节点外，其余节点被分为n个互不相交的节点，每个节点本身又是一棵树，这课树称为子树
    //3.树种的节点，除根节点外，其他的节点都有且仅有一个前驱节点，有零个或者多个后驱节点
    //节点:树中的元素，由数据项和数据之间的关系组成(node(data,lchild,rchild))
    //节点的度：节点所拥有的子树的个数
    //树的度：树中各节点度的最大值
    //叶子节点：度为零的节点，也叫终端节点
    //节点的层：节点的深度+1
    //节点的深度：从节点开始到节点的最大边数
    //节点的高度：从叶子节点开始到节点的最大边数
    //二叉树的存储方式:数组存储(2*i,2*i+1)，二叉链表存储（链式存储）
    //俩种特殊的二叉树：满二叉树（叶子节点在最后一层，其余节点都是有左右俩个孩子），完全二叉树（叶子节点在倒数第二层不满，或者最后一层只有左孩子）
    //二叉树的遍历：前序遍历，中序遍历，后续遍历
    //代码实现二叉树
    /// <summary>
    /// 节点类
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class TreeNode<T>
    {
        /// <summary>
        /// 节点类三个成员，数据，左孩子，右孩子
        /// </summary>
        public T data;
        public TreeNode<T> lChild;
        public TreeNode<T> rChild;

        /// <summary>
        /// 节点构造器
        /// </summary>
        /// <param name="_data"></param>
        public TreeNode(T _data)
        {
            data = _data;
            lChild = null;
            rChild = null;
        }
        /// <summary>
        /// 节点构造器
        /// </summary>
        /// <param name="_data"></param>
        public TreeNode(TreeNode<T> _lchild,TreeNode<T> _rchild)
        {
            data = default(T);
            lChild = _lchild;
            rChild = _rchild;
        }
        /// <summary>
        /// 节点构造器
        /// </summary>
        /// <param name="_data"></param>
        public TreeNode(T _data, TreeNode<T> _lchild, TreeNode<T> _rchild)
        {
            data = _data;
            lChild = _lchild;
            rChild = _rchild;
        }
        /// <summary>
        /// 节点构造器
        /// </summary>
        /// <param name="_data"></param>
        public TreeNode()
        {
            data = default(T);
            lChild = null;
            rChild = null;
        }

        public T Data
        {
            get { return data; }
            set { data = value; }
        }

        public TreeNode<T> LChild
        {
            get { return lChild; }
            set { lChild = value; }
        }

        public TreeNode<T> RChild
        {
            get { return rChild; }
            set { rChild = value; }
        }
    }
    class BinaryTree<T>
    {
        TreeNode<T> root;
        
        public TreeNode<T> Head
        {
            get { return root; }
            set { root = value; }
        }
        /// <summary>
        /// 树构造器
        /// </summary>
        /// <param name="_data"></param>
        public BinaryTree()
        {
            root = null;
        }
        /// <summary>
        /// 树构造器
        /// </summary>
        /// <param name="_data"></param>
        public BinaryTree(TreeNode<T> head)
        {
            root = head;
        }
        /// <summary>
        /// 树构造器
        /// </summary>
        /// <param name="_data"></param>
        public BinaryTree(T value)
        {
            root =new TreeNode<T>(value);
        }
        /// <summary>
        /// 树构造器
        /// </summary>
        /// <param name="_data"></param>
        public BinaryTree(T value, TreeNode<T> _lchild, TreeNode<T> _rchild)
        {
            TreeNode<T> p = new TreeNode<T>(value,_lchild,_rchild);
            root = p;
        }

        public TreeNode<T> GetRoot()
        {
            return root;
        }

        public TreeNode<T> GetLChild(TreeNode<T> Lp)
        {
            return Lp.lChild;
        }

        public TreeNode<T> GetRChild(TreeNode<T> Rp)
        {
            return Rp.rChild;
        }

        /// <summary>
        /// 节点p的左子树处插入值为value的节点
        /// </summary>
        /// <param name="value"></param>
        /// <param name="p"></param>
        public void InsertLChild(T value, TreeNode<T> p)
        {
            TreeNode<T> temp = new TreeNode<T>(value);
            temp.lChild = p.lChild;
            p.lChild = temp;
        }

        /// <summary>
        /// 节点p的右子树处插入值为value的节点
        /// </summary>
        /// <returns></returns>
        public void insertRChild(T value, TreeNode<T> p)
        {
            TreeNode<T> temp = new TreeNode<T>();
            temp.rChild = p.rChild;
            p.rChild = temp;
        }

        /// <summary>
        /// 删除p的左子树
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public TreeNode<T> DeletLChild(TreeNode<T> p)
        {
            if (p == null)
            {
                Console.WriteLine("p为空节点，不做处理");
            }
            TreeNode<T> temp = null;
            if (p.lChild != null)
            {
                temp = p.lChild;
                p.lChild = null;
            }
            return temp;

        }
        /// <summary>
        /// 删除p的右子树
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public TreeNode<T> DeletRChild(TreeNode<T> p)
        {
            if (p == null)
            {
                Console.WriteLine("p为空节点，不做处理");
            }
            TreeNode<T> temp = null;
            if (p.rChild != null)
            {
                temp = p.rChild;
                p.rChild = null;
            }
            return temp;
        }
        /// <summary>
        /// 判断节点p是否是叶子节点
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public bool IsLeaf(TreeNode<T> p)
        {
            if (p != null && p.rChild != null && p.lChild != null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        //判断树是否为空
        public bool IsEmpty()
        {
            if (root == null)
            {
                return true;
            }
            else
                return false;
        }
        /// <summary>
        /// 清空树，或者删除树
        /// </summary>
        public void ClearTree()
        {
            root = null;
        }
        /// <summary>
        /// 前序遍历树
        /// </summary>
        public void PerOrder(TreeNode<T> p)
        {
            if (p == null)
            {
                return;
            }
            //处理节点
            Console.WriteLine(p.data);

            PerOrder(p.lChild);
            PerOrder(p.rChild);
        }
        /// <summary>
        /// 中序遍历
        /// </summary>
        /// <param name="p"></param>
        public void InOrder(TreeNode<T> p)
        {
            if (p == null)
            {
                return;
            }

            InOrder(p.lChild);
            Console.WriteLine(p.data);
            InOrder(p.rChild);
        }
        /// <summary>
        /// 后序遍历
        /// </summary>
        /// <param name="head"></param>
        public void PostOrder(TreeNode<T> head)
        {
            if (head == null) { return; }

            PostOrder(head.lChild);
            PostOrder(head.rChild);
            Console.WriteLine(head.data);
        }
    }
}