美文网首页
树和二叉树及C#实现

树和二叉树及C#实现

作者: 周末的游戏之旅 | 来源:发表于2019-08-03 10:38 被阅读0次

    树的相关术语

    • 结点:
      包括一个数据元素及若干指向其他结点的分支信息
    • 结点的度
      一个结点的子树个数称为此结点的度。
    • 叶结点
      度为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的二叉树,如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应,则完全为二叉树。

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

    相关文章

      网友评论

          本文标题:树和二叉树及C#实现

          本文链接:https://www.haomeiwen.com/subject/tjtjdctx.html