树和二叉树及C#实现

树的相关术语

• 结点：
  包括一个数据元素及若干指向其他结点的分支信息
• 结点的度
  一个结点的子树个数称为此结点的度。
• 叶结点
  度为0的结点，即无后继的结点，也称为终端结点。
• 分支结点
  度不为0的结点，也称为非终端结点。
• 结点的层次
  从根结点开始定义，根节点的层次为1，根的直接后继层次为2，依此类推。
• 结点的层次编号
  将树中的结点按从上层到下层、同层从左到右的次序排成一个线性序列，依次给它们编以连续的自然数。
• 树的度
  树中所有结点大的度的最大值
  二叉树结点的度数指该结点所含子树的个数。
• 树的高度（深度）：
  树中所有结点的层次的最大值。
  二叉树的深度是指所有结点中最深的结点所在的层数。
• 有序树
  在数T中，如果各子树Ti之间是有先后次序的，则称为有序树。
• 森林
  m(m>=0)棵互不相交的树的集合。将一棵非空树的根节点删去，树就变成一个森林，反之，给森林增加一个统一的跟结点，森林就变成一棵树。
• 同构
  对两颗树，通过对结点适当地重命名，就可以使两棵树完全相等（结点对应相等，对应结点的相关关系也相等），则称这两棵树同构。
• 孩子结点
  一个结点的直接后继结点称为该结点的孩子结点。
• 双亲结点
  一个结点的直接前驱结点称为该结点的双亲结点。
• 兄弟结点
  同一双亲结点的孩子结点之间互称兄弟结点。
• 堂兄弟
  父亲是兄弟关系或堂兄弟关系的结点称为堂兄弟结点。
• 祖先结点
  一个结点的祖先结点是指从跟结点到该结点的路径上的所有结点。
• 子孙结点
  一个积极点的直接后继和间接后继称为该结点的子孙结点。
• 前辈
  层号比该结点小的结点，都称为该结点的前辈。
• 后辈
  层号比该结点小的结点，都称为该结点的后辈。

二叉树

把满足一下两个条件的树型结构叫做二叉数。

1. 每个节点的度都不大于2；
2. 每个节点的孩子节点次序不能任意颠倒

二叉树的性质

• 性质1：
  在二叉树的第i层上至多有2^(i+1)个结点（i>=1）。

• 性质2：
  深度为k的二叉树至多有2^k-1个结点(K>=1)。

• 性质3:
  对任意一棵二叉树T，若终端结点数为n0，而且度数为2的结点数为n2，则n0=n2+1

• 满二叉树:
  深度为k且有2^k-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。

• 完全二叉树:
  深度为k，结点为n的二叉树，如果其结点1_{n的位置序号分别与满二叉树的结点1}n的位置序号一一对应，则完全为二叉树。

  TIM截图20181210174810.png

• 性质4:
  具有n个结点的完全二叉树的深度为[log2n]+1

• 性质5:
  对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：
  (1)如i=1,则序号为i的结点是根结点，无双亲结点；如i>1，则序号为i的结点的双亲结点序号为[i/2]。
  (2)如2i>n，则序号为i的结点无左孩子；如2xi<=n，则序号为i的结点的左孩子结点的序号为2i。
  (3)如2i+1>n，则序号为i的结点无右孩子；如2i+1<=n，则序号为i的结点的右孩子结点的序号为2*i+1。

二叉树的遍历

二叉树的遍历有6中方式：
（1）访问根，遍历左子树，遍历右子树（记做DLR）。
（2）访问根，遍历右子树，遍历左子树（记做DRL）。
（3）遍历左子树，访问根，遍历右子树（记做LDR）。
（4）遍历左子树，遍历右子树，访问根（记做LRD）。
（5）遍历右子树，访问根，遍历左子树（记做RDL）。
（6）遍历右子树，遍历左子树，访问根（记做RLD）。
在以上6中方式中，如果规定按先左后右的顺序，那么就只剩DLR、LDR和LRD三种。
下面就分别介绍三种遍历方法的递归定义。
（1）先序遍历（DLR）操作过程若二叉树为空，则空操作，否则依次执行如下3个操作：
①访问根结点；
②按先序遍历左子树；③按先序遍历右子树。
（2）中序遍历（LDR）操作过程若二叉树为空，则空操作，否则依次执行如下3个操作：
①按中序遍历左子树；
②访问根结点；
③按中序遍历右子树。
（3）后序遍历（LRD）操作过程若二叉树为空，则空操作，否则依次执行如下3个操作：
①按后序遍历左子树；②按后序遍历右子树；
③访问根结点。
显然，遍历操作是一个递归过程。

三种遍历的实现

TreeNode

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

namespace Tree
{
    class TreeNode<T>
    {
        T data;
        TreeNode<T> LChrild;
        TreeNode<T> RChirld;
        
        public T Data { get => data; set => data = value; }
        internal TreeNode<T> LChrild1 { get => LChrild; set => LChrild = value; }
        internal TreeNode<T> RChirld1 { get => RChirld; set => RChirld = value; }

        public TreeNode(T data)
        {
            this.Data = data;
        }
    }
}

Program

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

namespace Tree
{
    class Program
    {
        static void Main(string[] args)
        {
            TreeNode<string> root = new TreeNode<string>("a");
            TreeNode<string> L = new TreeNode<string>("b");
            TreeNode<string> R = new TreeNode<string>("c");
            root.LChrild1 = L;
            root.RChirld1 = R;
            DLR(root);
            Console.WriteLine("----");
            LDR(root);
            Console.WriteLine("----");
            LRD(root);
        }

        /// <summary>
        /// 先序遍历
        /// </summary>
        /// <param name="root"></param>
        static void DLR(TreeNode<string> root)
        {
            if (root != null)
            {
                Console.WriteLine(root.Data);
                DLR(root.LChrild1);
                DLR(root.RChirld1);
            }
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        /// <param name="root"></param>
        static void LDR(TreeNode<string> root)
        {
            if (root != null)
            {
                LDR(root.LChrild1);
                Console.WriteLine(root.Data);
                LDR(root.RChirld1);
            }
        }

        /// <summary>
        /// 后序遍历
        /// </summary>
        static void LRD(TreeNode<string> root)
        {
            if (root != null)
            {
                LRD(root.LChrild1);
                LRD(root.RChirld1);
                Console.WriteLine(root.Data);
            }
        }
    }
}