树

树是n个结点的有限集。n=0时是空树。在任意一棵非空树中：(1)有且仅有一个特定的称为根的结点(2)当n>1时，其余结点可分为m个互不相交的有限集T1、T2、、、其每一个集合本身又是一棵树，并且称为根的子树。

叶子节点、分支结点

结点拥有子树的个数称为结点的度。度为0的结点称为叶子结点，度不为0的结点称为分支结点。

双亲、孩子、兄弟

结点的子树称为该结点的孩子，该结点称为孩子的双亲。同一个双亲的孩子之间称为兄弟

高度、深度、层

结点的高度：结点到叶子结点的最长路径（边数）
结点的深度：根到这个结点所经历的边的个数
结点的层数：结点的深度+1
树的高度：根结点的高度

——————————————————树的存储结构———————————————————

——————————————————双亲表示法———————————————————

以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在数组中位置。
data是数据域，存储结点的数据信息。parent是指针域，存储该结点的双亲在数组中的下标。

结点数据结构：

    private static class ParentNode {

        private Object item;

        private int parent;

        public ParentNode(Object item, int parent) {
            this.item = item;
            this.parent = parent;
        }
    }

初始化：

    //双亲结点下标数组
    private TreeNode[] treeNodes;


    public ParentalRepresentationTree() {
        treeNodes = new TreeNode[10];
    }

获取根节点：

    public Object root() {
        if (treeNodes.length == 0) {
            return null;
        }
        return treeNodes[0].item;
    }

插入结点：

    public void addNode(Object o, int parentIndex) {
        for (int i = 0; i < treeNodes.length; i++) {
            if (treeNodes[i] == null) {
                treeNodes[i] = new TreeNode(o, parentIndex);
                return;
            }
        }
    }

获取孩子节点：

    public List<Object> getChildren(TreeNode treeNode) {
        List<Object> list = new ArrayList<>();
        for (int i = 0; i < treeNodes.length; i++) {
            if (treeNodes[i] != null && treeNodes[i].parent == indexOf(treeNode.item)) {
                list.add(treeNodes[i].item);
            }
        }
        return list;
    }

    public int indexOf(Object o) {
        for (int i = 0; i < treeNodes.length; i++) {
            if (o.equals(treeNodes[i].item)) {
                return i;
            }
        }

        return -1;
    }

树的深度：

    public  int getDepth(){
        if(treeNodes.length == 0){
            return 0;
        }

        int depth=0;
        for (int i = 0; i <treeNodes.length ; i++) {
            int nowDepth = 1;
            if(treeNodes[i] != null){
                int m = treeNodes[i].parent;
                while (m!=-1 ){
                    m = treeNodes[m].parent;
                    nowDepth ++;
                }
                if(depth < nowDepth){
                    depth = nowDepth;
                }
            }
        }
        return depth;
    }

——————————————————双亲孩子表示法—————————————————

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

结点数据结构：

    private static class ChildNode {
        private int firstChild;

        private ChildNode nextChildNode;

        public ChildNode(int firstChild) {
            this.firstChild = firstChild;
            this.nextChildNode = null;
        }

        public ChildNode(int firstChild, ChildNode nextChildNode) {
            this.firstChild = firstChild;
            this.nextChildNode = nextChildNode;
        }
    }

    private static class ParentNode {
        Object data;

        ChildNode firstChildNode;

        public ParentNode(Object data) {
            this.data = data;
            this.firstChildNode = null;
        }

        public ParentNode(Object data, ChildNode firstChildNode) {
            this.data = data;
            this.firstChildNode = firstChildNode;
        }
    }

初始化：

    /**
     * 跟节点
     */
    private ParentNode root;

    /**
     * 双亲结点列表
     */
    private ParentNode[] parentNodes;

    /**
     * 节点数目
     */
    private int nodeNums;

    public ChildrenRepresentationTree(ParentNode root) {
        this.root = root;
        parentNodes = new ParentNode[10];
        nodeNums++;
    }

    public ChildrenRepresentationTree() {
    }

插入结点：

    public void add(Object o, int parentIndex) {

        ParentNode newNode = new ParentNode(o);
        if (parentIndex == -1) {
            root = newNode;
        }
        parentNodes[nodeNums] = newNode;

        //已有子节点数据
        int childCount = countChild(parentIndex);
        if(childCount != 0){
            ChildNode childNode = getChild(parentIndex, childCount);
            childNode.nextChildNode = new ChildNode(nodeNums);

        }else {
            parentNodes[parentIndex].firstChildNode = new ChildNode(nodeNums);
        }

        nodeNums++;
    }
    public int countChild(int index){
        if(parentNodes[index].firstChildNode == null){
            return  0;
        }
        int count = 1;
        ChildNode childNode = parentNodes[index].firstChildNode;
        while (childNode != null){

            childNode = childNode.nextChildNode;
            count ++;
        }
        return count;
    }

获取节点的孩子节点：

    public ChildNode getChild(int index, int n){
        if(countChild(index) < n){
            return null;
        }

        ChildNode childNode = parentNodes[index].firstChildNode;
        for (int i = 0; i <n ; i++) {
            childNode = childNode.nextChildNode;
        }

        return childNode;


    }

——————————————————孩子兄弟表示法—————————————————

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

结点的数据结构：

    private static class BotherNode {

        private Object item;

        private BotherNode firstChild;

        private BotherNode rightBother;

        public BotherNode(Object item) {
            this.item = item;
        }

        public BotherNode(Object item, BotherNode firstChild) {
            this.item = item;
            this.firstChild = firstChild;
        }

        public BotherNode(Object item, BotherNode firstChild, BotherNode rightBother) {
            this.item = item;
            this.firstChild = firstChild;
            this.rightBother = rightBother;
        }
    }