树结构

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