数据结构之树

1.树定义

树(Tree)是由n(n≥0)个结点组成的有限集合(树中元素通常称为结点)。
n＝0的树称为空树；n＞0的树T由以下两个条件约定构成:
① 有一个特殊的结点称为根(Root)结点，它只有后继结点，没有前驱结
点。
② 除根结点之外的其他结点分为m个互不相交的集合T0、T1、…、Tm-1，
其中每个集合Ti也具有树结构，称为根的子树( Subtree)。

2.树的术语

（1）父母、孩子与兄弟结点
一棵树中，一个结点的子树的根结点称为其孩子(Child)结点；相对
地，该结点是其孩子结点的父母( Parent)结点，也称为双亲结点。
根结点没有父母结点，其他结点有且仅有一个父母结点。
拥有同一个父母结点的多个结点之间称为兄弟( Sibling)结点。
结点的祖先( Ancestor)：是指其父母结点以及父母的父母结点等，直至
根结点。
结点的后代(Descendant，也称为子孙)是指其所有孩子结点，以及孩子的孩子结点等。
（2）度
结点的度( Degree)：是结点所拥有子树的棵数。
度为0的结点：称为叶子 (Leaf)结点，又称终端结点；树中除叶子结点之外的其他结点称为分支结点，又称非叶结点或非终端结点。
树的度：是指树中各结点度的最大值。
（3）结点层次、树的高度
结点的层次( Level)属性反映结点处于树中的层次位置。约定根结点的层次为1，其他结点的层次是其父母结点的层次加1。显然，兄弟结点
的层次相同。
树的高度( Height)，或称为深度( Depth)是树中结点的最大层次数。
(4)边、路径、直径
设树中X结点是Y结点的父母结点，序偶（X，Y）称为连接这两个结
点的分支，也称为边(Edge)。
设(X0，X1，…，Xk)是由树中结点组成的一个序列，且（Xi、Xi+1）都
是树中的边，则称该序列为从X0到Xk的一条路径(Path)。路径长度( Path
Length)为路径上的边数。
(5)无序树、有序树
在树的定义中，结点的子树T0、T1…、Tm-1之间没有次序，可以交换
位置，称为无序树，简称树。如果结点的子树T0、T1、…、Tm-1从左至右是有次序的，不能交换位置，则称该树为有序树。
(6) 森林( Forest)是m(m≥0)棵互不相交的树的集合。给森林加上一个根结
点就变成一棵树，将树的根结点删除就变成森林。

3.树的表示

（1）直观表示法

（2）嵌套集合表示法

（3）凹入表示法

（4）广义表表示法
A（B（D，E（H，I），F），C（G））

4.树的存储结构

（1）双亲表示法：用一维数组来存储树的各个结点，每个结点都记录自己的双亲。结点内容包括其数据信息以及该结点双亲在数组中的下标。

采用双亲表示法存储，查找任意结点的父母结点，仅需要常数时间，时间
性能为O(1)。查找结点的孩子结点，需要遍历所有结点，时间性能O(n)。
（2）孩子表示法：孩子表示法是一种基于链表的存储方法，即把每个结点的孩子排列起来，看成一个线性表，以单链表存储，称为该结点的孩子链表。

采用孩子表示法，查找任意结点的父母结点，需要遍历所有的孩子链表，
时间性能为O(n)。查找任意结点的孩子结点，若该结点孩子个数为m，则时间性能为O(m)。
孩子兄弟表示法：在这种存储结构中，每个结点记录自己的第一个孩子和下一个兄弟结点，也称为二叉链表表示法。

孩子兄弟表示法便于实现树的各种操作。例如，若要访问某结点x的第i
个孩子，只需要从该结点的第一个孩子引用找到第1个孩子后，沿着孩子结点的右兄弟域连续走i-1步，便可找到结点x的第i个孩子。

5.树的遍历

树的遍历是指从根结点出发，按照某种次序访问树中所有结点，使得每
个结点被访问一次且仅被访问一次。
• 先根遍历：先访问根结点，然后按照从左到右的次序遍历根的每一棵子树。
• 后根遍历：先按照从左到右的次序遍历根的每一棵子树，然后再访问根结点。
• 层次遍历：也称为树的广度遍历，它是从树的根结点开始，自上而下逐层遍历，同一层中，按从左到右的顺序对结点进行逐个访问。

6.二叉树的定义

二叉树( Binary Tree)是n个结点组成的有限集合，n=0时称为空二叉树；n>0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。

满二叉树：在一棵二叉树中，如果所有分支结点都存在左右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。

满二叉树特点：
①叶子结点只能出现在最下一层；
②只有度为0和度为2的结点

完全二叉树：
对一棵具有n个结点的二叉树按层序编号，根结点为0，
自上而下，每层从左至右。如果编号为i（0≤i≤n-1）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则这棵树称为完全二叉树

完全二叉树特点：
①深度为h的完全二叉树在h-1层是满二叉树；
②叶子结点只能出现在最下两层，且最下层的叶子结点都集
中在左侧连续的位置；
③如果有度为1的结点，则只能有一个，且该结点只有左孩
子。

7.二叉树的性质

性质1：若根结点的层次为1，则二叉树第i层最多有2i-1（i≥1）个结点。
性质2：在高度为h的二叉树中，最多有2h-1个结点（h≥0）。
性质3：设一棵二叉树的叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。
性质4：一棵具有n个结点的完全二叉树，其高度h= log2 𝑛 +1。
性质5：一棵具有n个结点的完全二叉树，对于序号为i（0≤i＜n）的结点，有：
①若i=0，则i为根结点，无父母结点；若i>0，则i的父母结点序号
为(i-1)/2。
②若2i+1＜n，则i的左孩子结点在2i+1；否则i无左孩子。
③若2i+2＜n，则i的右孩子结点在2i+2；否则i无右孩子。

8.二叉树的存储结构

8.1二叉树的顺序存储结构
对一棵完全二叉树，其顺序存储结构是：对树中每个结点进行编号,结点按其编号次序依次存储到连续的存储空间，结点编号对应数组下标。根据二叉树的性质5，由结点序号i可知其父母结点、左孩子结点和右孩子结点的序号，在顺序存储结构中，结点的逻辑关系实际上也隐含在其中，因此，完全二叉树能够可以采用顺序存储结构存储。

对于非完全二叉树，树中各结点的编号与等高度的完全二叉树对应
位置上的编号相同，依据其编号将结点存储到数组对应位置上，所以非
完全二叉树也可以采用顺序存储结构。

8.2 二叉树的链式存储结构
二叉树通常采用链式存储结构，每个结点至少要有两条链分别链接
左、右孩子结点，以表达二叉树的层次关系。二叉树的链式存储结构主
要有二叉链表和三叉链表。
(1) 二叉链表
二叉链表的结点结构如下，除了数据域外，另外再设两个地址域分
别指向左、右孩子。


采用二叉链表存储二叉树，每个结点只存储了到其孩子结点的单向
关系，没有存储到其父母结点的关系，查找父母结点需要遍历二叉树，
时间花费较多。
(2)三叉链表
在二叉链表结点结构的基础上，再增加一个地址域parent指向其父母
结点，就形成了三叉链表结点结构。

9 二叉树的遍历

先根次序遍历二叉树算法描述

  private void preorder(BinaryNode<T> p) //先根次序遍历以p结点为根的子树，递归方法
    {
        if (p != null) //若二叉树不空
        {
            System.out.print(p.data.toString() +“ ”); //先访问当前结点
            preorder(p.left); //遍历p的左子树，递归调用
            preorder(p.right); //遍历p的右子树，递归调用
        }
    }

 public void preorderTraverse() //先根次序遍历二叉树的非递归算法
    {
        System.out.print("先根次序遍历（非递归）： ");
        LinkedStack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>(); //创建空栈
        BinaryNode<T> p = this.root;
        while (p != null || !stack.isEmpty()) //p非空或栈非空时
            if (p != null) {
                System.out.print(p.data + " "); //访问结点
                stack.push(p); //p结点入栈
                p = p.left; //进入左子树
            } else //p为空且栈非空时
            {
                System.out.print("∧ ");
                p = stack.pop(); //p指向出栈结点
                p = p.right; //进入右子树
            }
        System.out.println();
    }

中根次序遍历二叉树算法描述

  private void inorder(BinaryNode<T> p) //中根次序遍历以p结点为根的子树，递归方法
    {
        if (p != null) {
            inorder(p.left); //中根次序遍历p的左子树，递归调用
            System.out.print(p.data.toString() +“ ”); //访问当前结点
            inorder(p.right); //中根次序遍历p的右子树，递归调用
        }
    }

后根次序遍历二叉树算法描述

  private void postorder(BinaryNode<T> p) //后根次序遍历以p结点为根的子树，递归方法
    {
        if (p != null) {
            postorder(p.left); //后根次序遍历p的左子树，递归调用
            postorder(p.right); //后根次序遍历p的右子树，递归调用
            System.out.print(p.data.toString() + " "); //后访问当前结点
        }
    }

4. 层次遍历
   
   
   层次遍历过程：
   ①当前结点p不空时，访问p，将其左、右孩子进队；
   ②出队一个结点，使p指向它，重复①，直到队列为空。

 public void levelorder() //按层次遍历二叉树
    {
        System.out.print("层次遍历二叉树： ");
        LinkedQueue<BinaryNode<T>> que = new LinkedQueue<BinaryNode<T>>(); //创建空队列
        BinaryNode<T> p = this.root; //根结点没有入队
        while (p != null) {
            System.out.print(p.data + " "); //访问p结点
            if (p.left != null)
                que.add(p.left); //p的左孩子结点入队
            if (p.right != null)
                que.add(p.right); //p的右孩子结点入队
            p = que.poll(); //p指向出队结点，若队列空返回null
        }
        System.out.println();
    }

10线索二叉树

定义:利用空链存储结点在某种遍历次序下的前驱和后继关系，原有非空的链保持不变，仍然指向该结点的左、右孩子结点；使空的left域指向前驱结点，空的right域指向后继结点，指向前驱或后继结点的链称为线索
在结点的存储结构上增加两个标志位来区分这两种情况：

对二叉树以某种次序进行遍历并加上线索的过程称为线索化。
按先根遍历次序进行线索化的二叉树称为先序线索二叉树，而按照
中根、后根遍历次序进行线索化的二叉树分别称为中序线索二叉树和后
序线索二叉树。

中序线索化算法描述：

 private ThreadNode<T> front=null; //front指向p在中根次序下的前前驱结点
 private void inorderThread( ThreadNode<T> p) //中序线索化以p结点为根的子树
    {
        if(p!=null)
        { inorderThread(p.left); //中序线索化p的左子树
            if(p.left= =null) //p的左子树为空
            { p.ltag=true; //设置左线索标记
                p.left= front; //设置p.left为指向前驱front的线索
            }
            if(p.right==null) //若p的右子树为空
                p.rtag=true; //设置右线索标记
            if(front!=null & front.rtag)
                front.right=p; //设置前驱 front. right为指向后继p的线索
            front=p; //front移动到p，即是p下个访问结点的
            inorderThread(p.right); //中序线索化p的右子树
        }
    }

中根次序遍历中序线索二叉树

  public ThreadNode<T> inNext(ThreadNode<T> p) //返回p在中根次序下的后继结点
    {
        if (p.rtag) //右线索标记
            return p.right;
        p=p.right; //进入p的右子树
        while (!p.ltag) //找到最左边的后代结点
            p=p.left;
        return p;
    }
    public void inorder() //中根次序遍历中序线索二叉树，非递归算法
    {
        System.out.print("中根次序遍历中序线索二叉树： ");
        ThreadNode<T> p=this.root;
        while (p!=null && !p.ltag) //寻找根的最左边的后代结点，即第一个访问结点
            p=p.left;
        while (p!=null)
        {
            System.out.print(p.data.toString()+" ");
            p = this.inNext(p); //返回p在中根次序下的后继结点
        }
        System.out.println();
    }

11哈夫曼树

定义：叶子结点的权值是对叶子结点赋予的一个有意义的数量值。 设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和称为二叉树的带权路径长度。
给定一组具有确定权值的叶子结点，可以构造出形态不同的多棵二
叉树。带权路径长度最小的二叉树称为最优树，也称为哈夫曼树。

11.1 哈夫曼树的构造

根据哈夫曼树的定义，一棵二叉树要使其带权路径长度最小，就应
该让权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离
根结点。

11.2 哈夫曼算法实现

//声明二叉树的静态三叉链表结点类TriElement如下：
    public class TriElement
    {
        int data; //数据域
        int parent, left, right; //父母、左、右孩子结点下标
        public TriElement(int data, int parent, int left, int right) //构造结点
        public TriElement(int data) //构造叶子结点
        public String toString() //返回结点的描述字符串
        public boolean isLeaf() //判断是否叶子结点
    }
    //构建哈夫曼树
 public class HuffmanTree{
       String charset; //字符集合
       TriElement[] huftree; //静态三叉链表结点数组
       //构造Huffman树，weights指定权值集合，数组长度为叶子结点数；默认字符集合从A开始
       public HuffmanTree(int[] weights)
       {
           this.charset = "";
           for (int i=0; i<weights.length; i++) //默认字符集合是从'A'开始的weights.length个字符
               this.charset += (char)('A'+i);

           int n = weights.length; //叶子结点数
           this.huftree = new TriElement[2*n-1]; //n个叶子的Huffman树共有2n-1个结点
           for(int i=0; i<n; i++) //Huffman树初始化n个叶子结点
               this.huftree[i] = new TriElement(weights[i]); //构造无父母的叶子结点
           for(int i=n; i<2*n-1; i++) //构造n-1个2度结点
           {
               int min1=Integer.MAX_VALUE, min2=min1; //最小和次小权值，初值为整数最大值
               int x1=-1, x2=-1; //最小和次小权值结点下标
               for (int j=0; j<i; j++) //寻找两个无父母的最小权值结点下标
                   if (this.huftree[j].parent==-1) //第j个结点无父母
                       if (this.huftree[j].data<min1) //第j个结点权值最小
                       {
                           min2 = min1; //min2记得次小权值
                           x2 = x1; //x2记得次小权值结点下标
                           min1 = this.huftree[j].data; //min1记得最小权值
                           x1 = j; //x1记得最小权值结点下标
                       }
                       else
                       if (this.huftree[j].data<min2) //第j个结点权值次小
                       {
                           min2 = huftree[j].data;
                           x2 = j;
                       }
               this.huftree[x1].parent = i; //合并两棵权值最小的子树，左孩子最小
               this.huftree[x2].parent = i;
               this.huftree[i] = new TriElement(min1+min2, -1, x1, x2); //构造结点，指定值、父母、左右孩子
           }
       }

       private String getCode(int i) //返回charset第i个字符的Huffman编码字符串
       {
           int n=8;
           char hufcode[] = new char[n]; //声明字符数组暂存Huffman编码
           int child=i, parent=this.huftree[child].parent;
           for (i=n-1; parent!=-1; i--) //由叶结点向上直到根结点，反序存储编码
           {
               hufcode[i] = (huftree[parent].left==child) ? '0' : '1'; //左、右孩子编码为0、1
               child = parent;
               parent = huftree[child].parent;
           }
           return new String(hufcode,i+1,n-1-i); //由hufcode数组从i+1开始的n-1-i个字符构造串
       }
   }

11.3 哈夫曼编码

（1）相关概念
等长编码：每个字符编码的长度相等，如ASCⅡ码，如果每个字符的使用频率相等，则等长编码是空间效率最高的方法。
不等长编码：频率高的字符采用尽可能短的编码，频率低的字符采用稍长的编码，以此获得更好的空间效率。
前缀编码：一组编码中任一编码都不是其他任何一个编码的前缀，我们称这组编码为前缀编码（产生二义性的不等长编码解决方案）
（2）哈夫曼编码
哈夫曼树可以构造不等长的前缀编码，称为哈夫曼编码。由于哈夫曼树是最优树，所以构造的哈夫曼编码总长度最短。文章来源地址https://www.toymoban.com/news/detail-526486.html

到了这里，关于数据结构之树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！