我们在前面介绍了很多典型的线性结构，如队列，堆栈，数组，她们至多只有一个尾节点。这是非常容易理解的。

下面我们要来介绍一个非线性结构，树（tree）：

树不在是一对一的数据结构，而是一对多的非线性连接：

 

这里有几个规定：

• 图中的结构就像一棵倒过来的树，最顶部的节点就是“根节点 (root 节点)”
• 每棵树至多只有一个根节点
• 根节点生出多个孩子节点，每个孩子节点只有一个父节点，每个孩子节点又生出多个孩子
• 父亲节点 (parent) 和孩子节点 (child) 是相对的
• 没有孩子节点的节点成为叶子节点 (leaf)

树的相关术语：

 

1）节点的度：

　　一个节点直接含有的子树个数，上图中3的度为2，10的度为1；

2）树的度：

　　一个树里面节点的度的最大值。例如上图的树的度为2；

3）节点的层次：

　　从根节点开始算起，根节点算第一层，上图中3为第二层，13为第四层；

4）树的高度：

　　从叶节点开始，从下往上增加；

5）树的深度：

　　从根节点开始，从上往下增加；

 

上看给出的信息是非常非常重要的，一定要熟练掌握。

 

由上述描述，我们一般可以通过两种方式实现一棵简单的树：

1）数组实现。

package treeTest;public class TreeNodebyArray
     
       {    private item mData;    private int mParent;        public TreeNodebyArray(item data,int parent){        mData=data;        mParent=parent;    }        public item getData(){        return mData;    }        public int getMParent(){        return mParent;    }        public void setData(item data){        mData=data;    }        public void setParent(int parent){        mParent=parent;    }    public static void main(String[] args){                TreeNode[] arrayTree = new TreeNode[10];        }}
     

 

2)链表实现：

package treeTest;public class TreeNodebyLinkList
     
       {    private item mData;    private TreeNodebyLinkList parent;    private TreeNodebyLinkList kid;        public TreeNodebyLinkList(item data,TreeNodebyLinkList parent){        mData=data;        this.parent=parent;    }        public item getData() {        return mData;    }    public void setData(item data) {        mData = data;    }    public TreeNodebyLinkList getParent() {        return parent;    }    public void setParent(TreeNodebyLinkList parent) {        this.parent = parent;    }    public TreeNodebyLinkList getChild() {        return kid;    }    public void setChild(TreeNodebyLinkList kid) {        this.kid = kid;    }    public static void main(String[] args){        LinkedList
      
        linkedTree = new LinkedList<>();    }}
      
     

 

 

当然，根据不同的树的要求，我们需要在一定程度上更改树内部的结构，所以实现代码也会不同。上述代码知识考虑了一种情况。