数据结构树及树的存储结构

梦里梦外; 2022-06-17 10:51 257阅读 0赞

# 概述 #

树，它是由n（n>=0）个有限节点组成一个具有层次关系的集合。当n=0时，这棵树被称之为空树。

![这里写图片描述][SouthEast]

树它具有以下的特点：

1.  每个节点有零个或多个子节点；
2.  没有父节点的节点称为根节点；
3.  每一个非根节点有且只有一个父节点；
4.  除了根节点外，每个子节点可以分为多个不相交的子树；

# 树的相关属性 #

## 结点的度 ##

*  结点拥有的子树数称为结点的度。
 *  度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。
 *  除根结点以外，分支结点也称为内部结点。
 *  树的度：一棵树中，最大的节点的度称为树的度；

![这里写图片描述][SouthEast 1]

## 层次与深度 ##

*  节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
 *  树的高度或深度：树中节点的最大层次；
 *  兄弟节点：具有相同父节点的节点互称为兄弟节点；
 *  堂兄弟节点：双亲在同一层的节点互为堂兄弟；

![这里写图片描述][SouthEast 2]

## 树的分类 ##

*  无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树;
 *  有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树；
 *  霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
 *  二叉树：每个节点最多含有两个子树的树称为二叉树；

# 树的数据结构 #

在树的数据结构中，简单的数据结构不能满足树，所以我们需要通过顺序存储结构和链式存储结构。

通常，有三种方式来表示树的存储结构：

*  双亲表示法
 *  孩子表示法
 *  孩子兄弟表示法

## 双亲表示法 ##

所谓双亲表示法，在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。  
双亲表示法的的优点是找到双亲节点容易，但是找到孩子节点困难。

数据结构：  
![这里写图片描述][SouthEast 3]

具体表示如下：  
![这里写图片描述][SouthEast 4]

代码定义：

/**
         * 双亲表示法
         */
        public class TreeNode<E> {
        
            private int parent;
    
            private E data;
        }

## 孩子表示法 ##

所谓孩子表示法，就是把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中。  
使用孩子表示法，寻找孩子节点比较容易，但是找到双亲节点会非常困难。

数据结构：  
![这里写图片描述][SouthEast 5]

具体表示如下：  
![这里写图片描述][SouthEast 6]

代码实现：

/**
         * 头节点
         */
        public class HeadNode<E> {
        
            private E data;
    
            private ChildNode firstChild;
        }
    
        /**
         * 孩子节点
         */
        public class ChildNode<E>{
        
    
            private E data;
    
            private ChildNode next;
        }

## 孩子兄弟表示法 ##

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。这种数据结构称之为孩子兄弟表示法。

数据结构：  
![这里写图片描述][SouthEast 7]

具体表示如下：  
![这里写图片描述][SouthEast 8]

代码实现如下：

public class Node<E> {
            private E data;
    
            private Node firstChild;
    
            private Node rightBrother;
        }

[SouthEast]: /images/20220617/c989edede2464f20a5814f1bbeca891b.png
[SouthEast 1]: /images/20220617/483cfab50d344579bd8094a7649cc8df.png
[SouthEast 2]: /images/20220617/4d29110167ad4e3baf94a2ba5c6437d0.png
[SouthEast 3]: /images/20220617/a491c322a25044b3b858b4511d06512e.png
[SouthEast 4]: /images/20220617/7d0bf5dfe77f48c8949cffe17cb371ee.png
[SouthEast 5]: /images/20220617/24d46dbdf7664fcc97895e1851a297d6.png
[SouthEast 6]: /images/20220617/0095dd885d2c4a57b3ff33b90e6af5a2.png
[SouthEast 7]: /images/20220617/a4ff2ca5db2f451a868c6b11b2d9fafb.png
[SouthEast 8]: /images/20220617/9c71b8dbd04d4937a60f7bd00f2c3f5a.png