大话数据结构-树

文章知识点来至于大话数据结构里边章节知识， 这篇主要介绍串和树列在计算机中存储形式， 以及在某些算法领域中对栈和队列的相关应用。章节最后介绍了著名的赫夫曼编码，该算法是现在网络所有的压缩工具算法之父，没有他可能就没有现在大家常用的压缩解压功能，它是通过二叉树的原理对传输内容进行编码，压缩传送量。 本篇对算法进行了描述和实现， 在实现代码的同时添加了流程图。相关代码源码请查看文章最后。本篇最后的算法描述和流程图以及代码实现是重点，如果对本篇感兴趣一定要通过该部分来巩固数据机构。

串

1 串的定义

         串是由零个或者多个字符组成的有序序列，又名叫做字符串。

2 串的比较

         ASCII和Unicode的引入：计算机中的常用字符是使用标准的ASCII编码，由7位二级制数表示一个字符，总共可表示128个。后来特殊字符的出现，ASCII码扩展成用8位二进制表示字符，总共可表示256个字符。这已经满足以英语为主的语言和特殊字符输入。但随着中文等更多字符出现，就有了Unicode编码，由16位二进制表示，这样约是65万多个字符。足够表示世界上所有字符了。为了ASCII和Unicode编码兼容，前面256个字符相同。

         串的比较

                       

3 串的抽象数据类型

 

         Index函数的算法实现：

4 串的存储结构

         串的顺序存储结构

         串的链式存储结构

5 朴素的模式匹配算法

         缺点：时间复杂度高

        

6 KMP模式匹配算法

         优点：避免重复遍历情况

    树

1 定义

         树是n(n=>0)个节点的有限集。 N=0时成为空树。在任意一颗非空树中：（1）有且仅有一个称为根的节点；（2）当n>0时，其余节点可分为m(m>0)个互不相交的有限集T1、T2、T3、Tm，其中每个节点又是一棵树，并且称为根的子树。

2 节点分类

         节点拥有的的子树的称为节点的度。度为0的称为终端节点或者叶节点；度不为0的称为非终端节点或者分支节点。树的度是树内个节点的度的最大值。

 

3 节点间关系

         节点的子树的根称为该节点的孩子， 该节点称为孩子的双亲。同一个双亲的孩子之间称为兄弟。

         如果将树种节点的各子树看成是从左到右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

4 线性结构和树结构对比

         线性节点的第一个元素无前驱，树结构的根节点无双亲，且唯一。

         线性表最有一个元素无后继， 树节点的叶节点无还是，但可以有多个

         中间元素一个前驱一个后继， 树节点一个双亲多个孩子。

5 树的存储结构

         双亲表示法

                   节点结构定义代码

 

                   设计方法：

                   思路：由于根节点是没有双亲我们设子位置域为-1。这也意味着我们所有节点都存在双亲的位置。树结构和树双亲表示法如下：

 

         孩子表示法

                   思路：把每个节点的孩子节点排列起来，以单链表做存储结构，则n个节点有n个孩子链表，如果是叶子节点则次单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一位数组中。

 

         双亲孩子表示法：是孩子表示法的改进，添加了双亲的存储结构。

 

         孩子兄弟表示法：任意一棵树，它的节点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此我们设置两个指针，分别指向该节点的第一个孩子和此节点的有兄弟。

         节点结构：

         示意图：

6 二叉树

         定义：二叉树（Binary Tree）是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两颗互不相交的、分别称为根节点的左子树、右子树的二叉树组成。

         五种基本形态

                   空二叉树

                   只有一个根节点

                   根节点只有左子树

                   根节点只有右子树

                   根节点既有左子树又有右子树

         二叉链表

　　　　　　二叉树每个结点最多有两个孩子,所有为它设计一个数据域和两个指针域,我们称这样的链表为二叉链表。

         定义代码        

 

7 遍历二叉树

         定义：二叉树的遍历是指从根节点开始，按照某种次序，依次访问二叉树中所有结点，使得每个节点被访问的一次且仅被访问一次。

         遍历方法

                   前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。如下顺序为：ABDGHCEIF

 

                   算法:       

         中序遍历

                   若树为空则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树。如下顺序为：GDHBAEICFA

 

                   算法:

         后序遍历

                   若树为空则空操作返回，否则从左到右先叶子后节点的方式遍历访问左右子树，最后是访问根节点。遍历顺序为：GHDBIEFCA

 

                   算法:

 

         层序遍历

                   若树为空则空操作返回，否则从树的第一层开始也就是根节点开始访问，从上而下，逐层遍历，在同一层，按从左到右顺序对结点访问。遍历顺序：ABCDEFGHJ

8 线索二叉树

         定义：指向前驱或者后继得指针陈为线索，加上线索的二叉树链表称为线性链表，相应的二叉树就称为线索二叉树。

著名的赫夫曼编码算法

         算法描述

                   赫夫曼当年通过二叉树原理设计的算法主要目的是为了解决当年远程通讯（主要是电报）的数据传送问题。

                   比如我们有一段文字内容“BADCADFEED”要通过网络传送给别人，显然用二进制（0和1）标示法很自然的想法。我们现在有六个字母ABCDEF，那么我们可以用相应的二进制数据表示：

                       

                   但如果一篇文章很长这样的二进制非常可怕，事实上，不管是英文、中文、或者其他的语言，字母和汉字的出现概率是不一样的。比如英语的几个元音字母，中文的“的 是 有 在”出现的频率很高。

                   假设六个字母出现的频率A 27， B 8，C 15， D 15， E 30，F5，合起来正好是100%。那就意味着，我们完全可以用赫夫曼来重新编码规划。

                   左图为构造赫夫曼树的过程中的权值显示。右图为将权值做分支改为0， 右分支改为1，这样的树就是赫夫曼树。

                  

                  

                   我们队六个字母用其根结点到叶子节点所经过的路径的0和1来编码，可以得到：

 

                   我们将文本内容BADCADFEED再次进行编码，对可可以看到结果串变小了。

 

　　算法实现流程图：

　　算法代码实现(C#版)（算法中可能有些地方可以优化）：

 public static string GetHoffmanCode(ICollection<Data>  dataCollection)
        {
            var originalTrees = dataCollection.Select(data => new BinaryNode() {Data = data}).ToList();
            var backupTrees = originalTrees.ToList();
            originalTrees.Sort();
            var i = 0;
           while (originalTrees.Count > 1)
           {
               var newData = new Data("T" + (++i), originalTrees[0].Data.Weight + originalTrees[1].Data.Weight);
               var newTree = new BinaryNode
                                 {
                                     LeftChildNode = originalTrees[0],
                                     RightChildNode = originalTrees[1],
                                     Data = newData
                                 };
               originalTrees[0].ParentNode = originalTrees[1].ParentNode = newTree;
               originalTrees.RemoveAt(0);
               originalTrees.RemoveAt(0);
               originalTrees.Add(newTree);
               originalTrees.Sort();
           }

            var codeString = string.Empty;
            foreach (var tree in backupTrees)
            {
                var tempNode = tree;
                var codeList = new List<string>();
                while (tempNode.ParentNode != null)
                {
                    var parentNode = tempNode.ParentNode;
                    codeList.Insert(0, ReferenceEquals(parentNode.LeftChildNode, tempNode) ? "0" : "1");
                    tempNode = tempNode.ParentNode;
                }
                var treeCode = string.Empty;
                codeList.ForEach(code => treeCode += code);
                codeString += string.Format("{0}{1};", tree.Data.Value, treeCode);
            }

            return codeString;
        }

 　　单元测试：

  private static void TestHoffmanCode()
        {
            var binaryTrees = new List<Data>();
            binaryTrees.Add(new Data("A", 27));
            binaryTrees.Add(new Data("B", 8));
            binaryTrees.Add(new Data("C", 15));
            binaryTrees.Add(new Data("D", 15));
            binaryTrees.Add(new Data("E", 30));
            binaryTrees.Add(new Data("F", 5));
            var codeString = HoffmanCode.GetHoffmanCode(binaryTrees);
            Assert.IsEqual(codeString, "A01;B1001;C101;D00;E11;F1000;");
        }

最后附上源代码下载地址：

http://download.csdn.net/detail/w_wanglei/5689883