示例树

1.双亲表示法

在每个结点中，

附设一个双亲指示器，指示其双亲结点到链表中的位置，

附设一个长子指示器，指示同一个双亲下最左侧结点的位置，

附设一个右兄弟指示器，指示该结点右侧兄弟位置的节点。

双亲表示法实现

/**
 * 双亲表示法
 */
//结点结构
class PTNode{
    public $data;//结点数据
    public $parent;//双亲位置
    public $firstChild;//长子位置（最左边子结点的位置）
    public $rightsib;//右边兄弟的位置
}
//树结构
class PTree{
    public $nodes=[];//结点数组
    public $count;//结点数量
    public $rootPos;//根的位置
}

约定根结点的父节点的位置为-1，这样我们所有结点都存了其双亲的位置，很容易就可以根据位置找到双亲，如图

约定不存在子结点，长子位置为-1，如此，在0个，1个,2个子结点的时候就很容易找到子结点了

约定不存在右兄弟结点，右兄弟位置为-1，如此，无论有多少个子结点，都很容易一一找出来。

2.孩子表示法

把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点右n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储机构，存放进一个一维数组中。

孩子表示法实现

/**
 * 孩子表示法
 */
//结点结构
class CTNode{
    public $child;//某个结点在表头结构中的位置
    public $next=null;//指向下一个孩子结点的指针域
}
//表头结构
class CTHead{
    public $data;//结点数据域
    public $firstchild;//孩子链表的头指针
    public $parent;//双亲结点指向结点数组的位置
}
//树结构
class CTree{
    public $nodes=[];//结点数组
    public $count;//结点数量
    public $rootPos;//根的位置
}

3.孩子兄弟表示法

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

孩子兄弟表示法实现

/**
 * 孩子兄弟表示法
 */
//结点结构
class CSTNode{
    public $data;//结点数据域
    public $firstchild;//长子结点
    public $rightsib;//右侧兄弟结点
}
//树结构
class CSTree{
    public $nodes=[];//结点数组
    public $count;//结点数量
    public $rootPos;//根的位置
}