树之存储结构

树的存储结构多种多样，下面给出树的常见的三种链式存储结构：双亲表示法，孩子表示法，孩子兄弟表示法。

1. 双亲表示法

核心思想：以一组连续空间（数组）存储树的结点，同时每个结点（内部类）附设一个指示器指示器双亲结点在链表中的位置。

package org.sky.tree;

/**
 * @description 树的双亲表示法
 * @author sky
 * @date 2017/1/4
 */
public class ParentTree {
public class PTNode{
        Object data;    //结点信息
int parent;     //双亲结点位置

public PTNode() {
super();
        }

public PTNode(Object data, int parent) {
super();
this.data = data;
this.parent = parent;
        }   
    }

private PTNode[] nodes;     //树采用顺序存储结构
private int numNodes;       //树中结点数
private int rootLocation;   //根结点位置

public ParentTree(PTNode[] nodes, int numNodes, int rootLocation) {
super();
this.nodes = nodes;
this.numNodes = numNodes;
this.rootLocation = rootLocation;
    }

public PTNode[] getNodes() {
return nodes;
    }

public void setNodes(PTNode[] nodes) {
this.nodes = nodes;
    }

public int getNumNodes() {
return numNodes;
    }

public void setNumNodes(int numNodes) {
this.numNodes = numNodes;
    }

public int getRootLocation() {
return rootLocation;
    }

public void setRootLocation(int rootLocation) {
this.rootLocation = rootLocation;
    }


}

2. 孩子表示法

核心思想 ：把每个结点的孩子结点排列起来，看成一个线性表，且以单链表作存储结构，则n个结点有那个孩子链表；n个头指针采用顺序存储结构。

package org.sky.tree;

import org.sky.tree.ParentTree.PTNode;

/**
 * @description 树的孩子表示法
 * @author sky
 *
 */
public class ChildrenTree {
public class CTNode{        //孩子结点
int child;
        CTNode next;
public CTNode(int child, CTNode next) {
super();
this.child = child;
this.next = next;
        }       
    }

public class CTBox{         //头结点
        Object data;
        CTNode firstchild;      //孩子链表头指针
public CTBox(Object data, CTNode firstchild) {
super();
this.data = data;
this.firstchild = firstchild;
        }       
    }

private PTNode[] nodes;     //树采用顺序存储结构
private int numNodes;       //树中结点数
private int rootLocation;   //根结点位置

public ChildrenTree(PTNode[] nodes, int numNodes, int rootLocation) {
super();
this.nodes = nodes;
this.numNodes = numNodes;
this.rootLocation = rootLocation;
    }

public PTNode[] getNodes() {
return nodes;
    }

public void setNodes(PTNode[] nodes) {
this.nodes = nodes;
    }

public int getNumNodes() {
return numNodes;
    }

public void setNumNodes(int numNodes) {
this.numNodes = numNodes;
    }

public int getRootLocation() {
return rootLocation;
    }

public void setRootLocation(int rootLocation) {
this.rootLocation = rootLocation;
    }   
}

3. 孩子兄弟表示法

核心思想：链表中的结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。

package org.sky.tree;

/**
 * @description 树的孩子兄弟表示法
 * @author sky
 * @date 2017/1/4
 */
public class ChildSiblingTree {
public class CSNode{
        Object data;
        CSNode firstChild;
        CSNode nextSibling;
public CSNode(Object data, CSNode firstChild, CSNode nextSibling) {
super();
this.data = data;
this.firstChild = firstChild;
this.nextSibling = nextSibling;
        }       
    }
}