【Java数据结构】树的概念及存储结构

一、树的概念

1、树的逻辑结构

①树的定义

• 在树中，通常将数据元素称为结点。
• 树是n个节点的有限集合，当n为0的时候，称为空树。

②树的特点

• 非空树，有且仅有一个特定的称为根的结点。
• 当n>1的时候，除了根节点之外的其余节点被分成m个互不相交的有限集合T1、T2、...Tm，其中每个集合又是一棵树，并成为这个根节点的子树。

③树的基本术语

• 结点的度、树的度：

  • 某个结点所拥有的子树的个数称为该结点的度（degree）
  • 树中各结点度的最大值称为该树的度。

• 叶子结点、分支结点：

  • 度为0的结点称为叶子结点，也称为终端结点。
  • 度不为0的结点称为分支结点，也称为非终端结点。

• 孩子结点、双亲结点、兄弟节点：

  • 某结点的子树的根结点称为该结点的孩子结点(children node)
  • 反之，该节点称为其孩子结点的双亲结点(parent node)

• 路径、路径长度：

  • n1n2...nk称为一条由n1到nk的路径，路径上经过的边数称为路径长度。
  • 例如：在上述图(a)中，结点A到结点I的路径是ABEI，路径长度为3。显然，在树中，路径是唯一的！

• 祖先、子孙：

  • 如果从结点x到结点y有一条路径，那么x就称为y的祖先，y称为x的子孙。
  • 显然，以某结点为根的子树中的任一结点都是该结点的子孙。
  • 例如，A、B、E结点均为I结点的祖先。

• 结点的层数、树的深度（高度）、树的宽度：

  • 规定根节点的层数为1，对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。
  • 数中所有节点的最大层数为树的深度，也称为树的高度。
  • 树中每一层结点个数的最大值称为树的宽度.

2、树的抽象数据类型

ADT Tree
DataModel
	树由一个根节点和若干颗子树构成，树中结点具有层次关系。
Operation
	initTree
		输入：无
		功能：初始化一棵树
		输出：一棵树
	preOrder
		输入：无
		功能：前序遍历树
		输出：树的前序遍历序列
	postOrder
		输入：无
		功能：后序遍历树
		输出：树的后序遍历序列
	leverOrder
		输入：无
		功能：层序遍历树
		输出：树的层序遍历序列
endADT

3、树的遍历操作定义

​ 树的遍历是指从根节点出发，按照某种次序访问树中所有结点，使得每个结点被访问一次且仅被访问一次。

①前序（根）遍历

​ 若树为空，则空操作返回；否则执行以下操作

• 访问根结点
• 按照从左到右的顺序前序遍历根节点的每一颗子树

②后序（根）遍历

​ 若树为空，则空操作返回；否则执行以下操作

• 按照从左到右的顺序后序遍历根节点的每一颗子树
• 访问根节点

③举例

• 前序遍历序列：A B D E I F C G H
• 后序遍历序列：D I E F B G H C A
• 层序遍历序列：A B C D E F G H I

二、树的存储结构

1、双亲表示法

• 每个结点都记录自己的双亲，除根节点外，每个结点都有且仅有一个双亲结点。
• 使用一维数组来存储树的各个结点（一般按层序存储），数组元素包括结点的数据信息、该结点的双亲在数组中的下标。

定义如下：

public class ParentNode<T>{
    private T data;	//定义结点泛型数据域
    private int parent;	//定义结点双亲下标
    public T getData(){return data;}
    public void setData(T element){data = element;}
    public int getParent(){return next;}
    public void setParent(int parent){this.parent=parent;}
}

下图中，根节点的parent为-1，表示没有双亲。

2、孩子表示法

• 每个结点记述自己的所有孩子。
• 是一种基于链表的存储方法，即把每个结点的孩子排列起来，看成一个线性表，且以单链表存储，称为该结点的孩子链表。
• n个结点共有n个孩子链表（叶子结点的孩子链表为空表）
• n个链表共有n个头引用，这n个头引用又构成了一个线性表，为了便于查找，可以采用顺序存储。
• 最后，将存放n个头引用的数组和存放n个结点数据信息的数组结合起来，构成孩子链表的表头数组。

孩子结点：

public class ChildNode{
    private int child;		//结点对应头结点下标
    private ChildNode next;	//引用下一个孩子
    public int getChild(){return child;}
    public void setChild(int child){this.child=child;}
    public ChildNode getNext(){return next;}
    public void setNext(ChildNode next){this.next=next;}
}

头结点：

public class TreeNode<T>{
    private T data;		//定义结点泛型数据域
    private ChildNode firstChild;	//孩子链表头引用
    public T getData(){return data;}
    public void setData(T data){this.data=data;}
    public ChildNode getFirstChild(){return firstChild;}
    public void setFirstChild(ChildNode firstChild){
        this.firstChild=firstChild;
    }
}

3、孩子兄弟表示法

• 每个结点记录自己的长子和右兄弟

• 又称为二叉链表表示法

  • 除了每个结点的数据域之外，设置两个引用域分别引用该结点的第一个孩子和右兄弟，链表的结构如下所示。

    

  • firstChild存储第一个孩子引用，rightSib存储右兄弟引用。