数据结构C#版笔记--树与二叉树

                图1

上图描述的数据结构就是“树”,其中最上面那个圈圈A称之为根节点(root),其它圈圈称为节点(node),当然root可以认为是node的特例。

树跟之前学习过的线性结构不同,它是一对多的非线性结构,具有二个基本特点:

1、根节点(root)没有前驱节点,除root之外的所有节点有且只有一个前驱节点 2、树中的所有节点都可以有0个或多个后继节点。

所以下面这些歪瓜咧枣,不能算是树:

                图2

下是是一些烦人但是很重要的术语:   1、结点(Node):表示树中的数据元素,由数据项和数据元素之间的关系组成。在图1中,共有10个结点。   2、结点的度(Degree of Node):结点所拥有的子树的个数,在图1中,结点A的度为3。   3、树的度(Degree of Tree):树中各结点度的最大值。在图1中,树的度为3。   4、叶子结点(Leaf Node):度为0的结点,也叫终端结点。在图1中,结点E、F、G、H、I、J都是叶子结点。   5、分支结点(Branch Node):度不为0的结点,也叫非终端结点或内部结点。在图1中,结点A、B、C、D是分支结点。   6、孩子(Child):结点子树的根。在图1中,结点B、C、D是结点A的孩子。   7、双亲(Parent):结点的上层结点叫该结点的双亲。在图1中,结点B、C、D的双亲是结点A。   8、祖先(Ancestor):从根到该结点所经分支上的所有结点。在图1中,结点E的祖先是A和B。   9、子孙(Descendant):以某结点为根的子树中的任一结点。在图1中,除A之外的所有结点都是A的子孙。 10、兄弟(Brother):同一双亲的孩子。在图1中,结点B、C、D互为兄弟。 11、结点的层次(Level of Node):从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1,其余结点的层次等于其双亲结点的层次加1。 12、堂兄弟(Sibling):同一层的双亲不同的结点。在图1中,G和H互为堂兄弟。 13、树的深度(Depth of Tree):树中结点的最大层次数。在图1中,树的深度为3。 14、无序树(Unordered Tree):树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。 15、有序树(Ordered Tree):树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树,因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。 16、森林(Forest):m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大,但在数据结构中树和森林的概念差别很小。从定义可知,一棵树有根结点和m个子树构成,若把树的根结点删除,则树变成了包含m棵树的森林。当然,根据定义,一棵树也可以称为森林。

二叉树

通俗点讲,就是每个节点最多只能分二叉的树(标准的废话,呵),图示如下:

                图3

注:二叉树是有序树,即每个节点下的左右子节点摆放是有顺序的,所以上图中的(a)跟(b)被认为是二棵不同的二叉树!

二叉树有二种经典的特例:完全二叉树(Complete Binary Tree) 与 满二叉树(Full Binary Tree)

                图4

如上图,所谓满二叉树就是:每个节点都有二个分支,且所有叶节点都处于同一个层次。(很明显,对于一个深度Degree为K的满二叉树,其节点总数为

)

所谓完全二叉树就是:叶结点只可能出现在层次最大的两层上,并且某个结点的"左分支"下"子节点"的最大层次与"右分支"下"子节点"的最大层次相等或大1。(再讲得更通俗点:除最后一层外,其它各层都是满的,且最后一层如果出现未满的情况,叶节点只能在左边,即只能空出右节点的位置)

二叉树的数学特性:

1、 一棵非空二叉树的第 i 层上最多有

个结点(i≥1)。

      比如:以上图满二叉树(a)为例,第一层只有节点a,即2的0次方=1,第二层有B,C二个节点,即2的(2-1)次方为2...

2、若规定空树的深度为0,则深度为k的二叉树最多有

个结点(k≥0)。

      这个其实上面在介绍满二叉树的时候,已经说过深度为k的满二叉树,有

个节点,这个就是二叉树的节点数极限了.

3、具有n个结点的完全二叉树的深度k为

  比如上图中(a)树的总节点数为15,则深度K = lg(15) + 1 = 3 + 1 = 4

4、对于一棵非空二叉树,如果度为0的结点数目为

,度为2的结点数目为

,则有

  比如上图中(a)树中度为0的节点为H,I,J,K,L,M共6个(即叶节点),其它节点A,B,C,D,E,F,G都是度为2的结节有7个,有 7 = 6 + 1

5、对于具有n个结点的完全二叉树,如果按照从上到下和从左到右的顺序对所有结点从1开始编号,则对于序号为 i 的结点,有:

                图5 (1)如果 i>1,则序号为i的结点的双亲结点的序号为i/2(“/”表示整除);如果i=1,则该结点是根结点,无双亲结点。

    如上图,随便选一个节点,比如D(序号为4),则D的父节点序号为4/2 = 2,即节点B (2)如果2i≤n,则该结点的左孩子结点的序号为2i;若2i>n,则该结点无左孩子。

    如上图,随便找个节点5(即E点),则2*5<=10,则E节点的左子节点序号为2*5 = 10即J点 (3)如果2i+1≤n,则该结点的右孩子结点的序号为2i+1;若2i+1>n,则该结点无右孩子。

    如上图,随便找个节点4(即D点),则2*4 + 1<=10,则D点的右子节点序列为2*4 +1 = 9,即I点

二叉树的存储结构

1、顺序存储

对于完全二叉树,比如图5的这种,可以表示为

由刚才的数学特性5得知,只要知道了一个节点的序号i,就能确定该节点的父节点,以及左右子节点的序号(如果有左右子节点的话),所以这样就可以将非线性的树型结构,变成一一对应的线性结构.

但是非完全二叉树,特性5就不成立了,但我们可以给非完全二叉树添加一些空节点,补成一棵完全二叉树

上图中的^代表空节点(NULL)

这样就能使用顺序存储了,但是缺点很明显:浪费了存储空间。

2、二叉链表存储

把每个节点Node添加三个基本属性 lChild(左子节点),rChild(右子节点),以及data(节点值),如果左子节点或右子节点为空,则用Null表示(图形中用^表示)

如上图,根据是否有头节点引用,可分为"不带头结点的二叉链表"和"带头结点的二叉链表"

3、三叉链表存储

二叉链表存储方式,如果要从某节点向上找父节点或根结点,会很麻烦,所以为了改进,可以给每个Node再增加一个parent父节点属性,就变成下面这种结构

下面来看看代码的实现:(下面只演示了不带头结点的二叉链表实现)

节点类Node.cs(二叉链表的结点)

namespace 树与二叉树
{
    public class Node<T>
    {
        private T data;
        private Node<T> lChild;//左子节点
        private Node<T> rChild;//右子节点

        public Node(T data, Node<T> ln, Node<T> rn) 
        {
            this.data = data;
            this.lChild = ln;
            this.rChild = rn;
        }

        public Node(Node<T> ln, Node<T> rn) 
        {
            this.data = default(T);
            this.lChild = ln;
            this.rChild = rn;
        }

        public Node(T data) 
        {
            this.data = data;
            lChild = null;
            rChild = null;
        }

        public Node() 
        {
            data = default(T);
            lChild = null;
            rChild = null;
        }

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

        public Node<T> LChild 
        {
            get { return this.lChild; }
            set { this.lChild = value; }
        }

        public Node<T> RChild 
        {
            get { return this.rChild; }
            set { this.rChild = value; }
        }
    }
}

树BiTree.cs

namespace 树与二叉树
{
    public class BiTree<T>
    {
        private Node<T> root;

        /// <summary>
        /// 根节点(属性)
        /// </summary>
        public Node<T> Root
        {
            get { return root; }
            set { root = value; }
        }

        /// <summary>
        /// 构造函数
        /// </summary>
        public BiTree()
        {
            root = null;
        }

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="data"></param>
        public BiTree(T data)
        {
            Node<T> p = new Node<T>(data);
            root = p;
        }

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="data"></param>
        /// <param name="ln"></param>
        /// <param name="rn"></param>
        public BiTree(T data, Node<T> ln, Node<T> rn)
        {
            Node<T> p = new Node<T>(data, ln, rn);
            root = p;
        }

        /// <summary>
        /// 判断树是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            if (root == null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        /// <summary>
        /// 获取节点p的左子节点
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public Node<T> GetLChild(Node<T> p)
        {
            return p.LChild;
        }

        /// <summary>
        /// 获取节点p的右子节点
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public Node<T> GetRChild(Node<T> p)
        {
            return p.RChild;
        }

        /// <summary>
        /// 节点p下插入左子节点data
        /// </summary>
        /// <param name="data"></param>
        /// <param name="p"></param>
        public void InsertL(T data, Node<T> p)
        {
            Node<T> tmp = new Node<T>(data);
            tmp.LChild = p.LChild;
            p.LChild = tmp;
        }

        /// <summary>
        /// 节点p下插入右子节点data
        /// </summary>
        /// <param name="data"></param>
        /// <param name="p"></param>
        public void InsertR(T data, Node<T> p)
        {
            Node<T> tmp = new Node<T>(data);
            tmp.RChild = p.RChild;
            p.RChild = tmp;
        }

        /// <summary>
        /// 删除节点p的左子节点
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public Node<T> DeleteL(Node<T> p)
        {
            if ((p == null) || (p.LChild == null))
            {
                return null;
            }
            Node<T> tmp = p.LChild;
            p.LChild = null;
            return tmp;
        }

        /// <summary>
        /// 删除节点p的右子节点
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public Node<T> DeleteR(Node<T> p)
        {
            if ((p == null) || (p.RChild == null))
            {
                return null;
            }
            Node<T> tmp = p.RChild;
            p.RChild = null;

            return tmp;
        }

        /// <summary>
        /// 判断节点p是否为叶节点
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public bool IsLeaf(Node<T> p)
        {
            if ((p != null) && (p.LChild == null) && (p.RChild == null))
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
}

其中向节点B下插入左子节点的算法示意图如下:

二叉树的遍历:

对于二叉树而言,有四种经典的遍历方式

1、前序遍历(也称先序遍历)-->即按 node-->lChild-->rChild的顺序来递归遍历(也就是“先自身”-->然后“左子节点”-->最后“右子节点”)

2、中序遍历-->即按 lChild-->node-->rChild(先“左子节点”,然后“自身节点”,最后“右子节点”)的顺序来递归遍历

3、后序遍历-->即按 lChild-->rChild-->node(先“左子节点”,然后“右子节点”,最后“自身节点”)的顺序来递归遍历

4、层顺遍历--这个不解释,字面意思理解就行

ok,最后来一段代码验证+测试一把:

using System;
using System.Collections;
using System.Collections.Generic;

namespace 树与二叉树
{
    class Program
    {
        static void Main(string[] args)
        {
            #region //构造树
            BiTree<string> tree = new BiTree<string>("A");
            Node<string> root = tree.Root;
            tree.InsertL("B", root);
            tree.InsertR("C", root);

            Node<string> b = root.LChild;
            Node<string> c = root.RChild;

            tree.InsertL("D", b);
            tree.InsertR("E", b);

            tree.InsertL("F", c);
            tree.InsertR("G", c);

            Node<string> d = b.LChild;
            Node<string> e = b.RChild;

            tree.InsertL("H", d);
            tree.InsertR("I", d);
            tree.InsertL("J", e);
            #endregion



            Console.WriteLine("前序遍历开始>>>\n");
            //前序遍历
            PreOrder(root);

            Console.WriteLine("\n------------------------\n");


            Console.WriteLine("中序遍历开始>>>\n");
            //中序遍历
            InOrder(root);

            Console.WriteLine("\n------------------------\n");
            Console.WriteLine("后序遍历开始>>>\n");
            //后序遍历
            PostOrder(root);


            Console.WriteLine("\n------------------------\n");
            Console.WriteLine("层序遍历开始>>>\n");
            //后序遍历
            LevelOrder(root);

            Console.Read();
        }

        /// <summary>
        /// 前序遍历(即 root-->left-->right )
        /// </summary>
        /// <param name="root"></param>
        static void PreOrder(Node<string> root) 
        {
            if (root != null) 
            {
                //先处理root
                Console.Write("{0} ", root.Data);

                //再处理root的左子节点
                PreOrder(root.LChild);

                //再处理root的右子节点
                PreOrder(root.RChild);
            }         

            
        }

        /// <summary>
        /// 中序遍历(left-->root-->right)
        /// </summary>
        /// <param name="root"></param>
        static void InOrder(Node<string> root) 
        {
            if (root == null) 
            {
                return;
            }

            //先左子节点
            InOrder(root.LChild);

            //再根节点
            Console.Write("{0} ", root.Data);

            //再右子节点
            InOrder(root.RChild);
        }

        /// <summary>
        /// 后序遍历
        /// </summary>
        /// <param name="root"></param>
        static void PostOrder(Node<string> root) 
        {
            if (root == null) 
            {
                return;
            }

            PostOrder(root.LChild);
            PostOrder(root.RChild);
            Console.Write("{0} ", root.Data);
        }

        /// <summary>
        /// 层顺遍历
        /// </summary>
        /// <param name="root"></param>
        static void LevelOrder(Node<string> root) 
        {
            if (root != null) 
            {
                Queue<Node<string>> q = new Queue<Node<string>>();
                
                q.Enqueue(root);

                while (q.Count>0)
                {
                    Node<string> tmp = q.Dequeue();

                    //先处理根节点
                    Console.Write("{0} ", tmp.Data);

                    if (tmp.LChild != null) 
                    {
                        //左子节点入队
                        q.Enqueue(tmp.LChild);
                    }

                    if (tmp.RChild != null) 
                    {
                        //右子节点入队
                        q.Enqueue(tmp.RChild);
                    }
                }
            }
        }
    }
}

运行结果:

前序遍历开始>>>

A B D H I E J C F G ------------------------

中序遍历开始>>>

H D I B J E A F C G ------------------------

后序遍历开始>>>

H I D J E B F G C A ------------------------

层序遍历开始>>>

A B C D E F G H I J

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏曾大稳的博客

树(Tree)以及二叉树的遍历

树(tree) 是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次...

1741
来自专栏xcywt

《大话数据结构》树以及赫夫曼编码的例子

第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)...

4356
来自专栏用户画像

4.3.1 二叉树的遍历

所谓二叉树的遍历,是指按照某条搜索路径访问树中的每个结点,使得每个几点均被访问一次,而且仅被访问一次。

822
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1834
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题19二叉树的镜像

   分析:所谓“镜像”就是从镜子里看到的样子。我们可以画一棵二叉树,然后画出该二叉树的镜像。画完图之后我们会发现,所谓“二叉树的镜像”就是把二叉树中所有子树...

2815
来自专栏向治洪

ArrayList和LinkedList的区别

一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构...

1949
来自专栏xingoo, 一个梦想做发明家的程序员

AVL树

平衡二叉树,是一个方便查找的树,树的左子树深度与右子树的深度的差总(BF)是在+1,0,-1之中。 随着树的建立,插入,树都会自动的进行调整,使得其满足上面的条...

2055
来自专栏软件开发 -- 分享 互助 成长

二叉排序树和平衡二叉树

二叉排序树又称二叉查找树或二叉搜索树。 它一棵空树或者是具有下列性质: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,...

20710
来自专栏weixuqin 的专栏

数据结构学习笔记(树、二叉树)

2603
来自专栏Android相关

平衡二叉树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

3673

扫码关注云+社区