树的简介及Java实现

Java基础

浏览数:49

2019-10-8

一、树的基本知识

  树是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点;除了根结点外,每个子结点可以分为多个不相交的子树;

1、结点的层次和树的深度   树的结点包含一个数据元素及若干指向其子树的若干分支。结点的层次( level) 从根开始定义,层次数为 0 的结点是根结点,其子树的根的层次数为 1。若结点在 L 层,其子树的根就在 L+1 层。对于层次为 k( k > 0)的每个结点 c,都有且仅有一个层次为 k-1 的结点 p与之对应, p 称为 c 的父亲( parent) 或父结点。若 p 是 c 的父亲,则 c 称为 p 的孩子( child)。父子之间的连线是树的一条边。在树中根结点没有父亲,其余结点只有一个父结点,但是却可能有多个孩子,同一结点的孩子相互称为兄弟( sibling)。树中结点的最大层次数称为树的深度( Depth) 或高度。树中结点也有高度,其高度是以该结点为根的树的高度。 2、结点的度与树的度   结点拥有的子树的数目称为结点的度( Degree)。度为 0 的结点称为叶子( leaf) 或终端结点。度不为 0 的结点称为非终端结点或分支结点。除根之外的分支结点也称为内部结点。在这里需要注意的是结点的直接前驱结点,即它的父结点不计入其度数。 3、在树结构中有一个重要的性质如下:   树中的结点数等于树的边数加 1,也等于所有结点的度数之和加 1。这是因为除根结点以外每个结点都与指向它的一条边对应,所以除根结点以外的结点数等于树中边数之和。因此树中的结点数等于树的边数加 1。而边数之和就是所有结点的度数之和,因此树中的结点数也等于所有结点的度数之和加 1。   这个性质说明在树中结点总数与边的总数是相当的,基于这一事实,在对涉及树结构的算法复杂性进行分析时,可以用结点的数目作为规模的度量。 4、路径   在树中k+1 个结点通过k条边连接构成的序列{( v0,v1) ,( v1,v2) , … ,( vk-1,vk) | k ≥ 0},称为长度为k的路径( path)。注意,此时忽略了树中边的方向。由单个结点, 0 条边构成的是长度为 0 的路径。结论:树中任意两个结点之间都存在唯一的路径。这意味着树既是连通的,同时又不会出现环路。从根结点开始,存在到其他任意结点的一条唯一路径,根到某个结点路径的长度,恰好是该结点的层次数。 5、祖先、子孙、堂兄弟   将父子关系进行扩展,就可以得到祖先、子孙、堂兄弟等关系。结点的祖先是从根到该结点路径上的所有结点。以某结点为根的树中的任一结点都称为该结点的子孙。父亲在同一层次的结点互为堂兄弟。 6、有序树、m 叉树、森林   如果将树中结点的各子树看成是从左至右是有次序的,则称该树为有序树;若不考虑子树的顺序则称为无序树。对于有序树,我们可以明确的定义每个结点的第一个孩子、第二个孩子等,直到最后一个孩子。若不特别指明,一般讨论的树都是有序树。   树中所有结点最大度数为 m 的有序树称为 m 叉树。   森林( forest) 是 m( m ≥ 0 )棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。树和森林的概念相近。删去一棵树的根,就得到一个森林;反之,加上一个结点作树根,森林就变为一棵树。
二、代码实现 1、树的结点类:

 1 import java.util.List;
 2 
 3 public class TreeNode<E> {
 4     public E key;// data
 5     public TreeNode<E> parent;// parent
 6     public List<TreeNode<E>> children;// children
 7 
 8     public TreeNode(E key, TreeNode<E> parent) {
 9         this.key = key;
10         this.parent = parent;
11     }
12 
13     public TreeNode(E key) {
14         this.key = key;
15     }
16 
17     @Override
18     public String toString() {
19         return "BSTNode [key=" + key + "]";
20     }
21 
22 }

2、树的接口类:


 1 import java.util.List;
 2 
 3 public interface ITree<E> {
 4   /**
 5    * 节点数
 6    * @return
 7    */
 8   int getSize();
 9 
10   /**
11    * 获取根节点
12    * @return
13    */
14   TreeNode<E> getRoot();
15 
16   /**
17    * 获取x的父节点
18    * @param x
19    * @return
20    */
21   TreeNode<E> getParent(TreeNode<E> x);
22 
23   /**
24    * 获取第一个儿子
25    * @param x
26    * @return
27    */
28   TreeNode<E> getFirstChild(TreeNode<E> x);
29 
30   /**
31    * 获取x的下一个兄弟
32    * @param x
33    * @return
34    */
35   TreeNode<E> getNextSibling(TreeNode<E> x);
36 
37   /**
38    * 子树高度
39    * @param x
40    * @return
41    */
42   int getHeight(TreeNode<E> x);
43 
44   /**
45    * 插入子节点
46    * @param x
47    * @param child
48    */
49   void insertChild(TreeNode<E> x, TreeNode<E> child);
50 
51   /**
52    * 删除第i个子节点
53    * @param x
54    * @param i
55    */
56   void deleteChild(TreeNode<E> x, int i);
57 
58   /**
59    * 先序遍历
60    * @param x
61    * @return
62    */
63   List<TreeNode<E>> preOrder(TreeNode<E> x);
64 
65   /**
66    * 后续遍历
67    * @param x
68    * @return
69    */
70   List<TreeNode<E>> postOrder(TreeNode<E> x);
71 
72   /**
73    * 层次遍历
74    * @param x
75    * @return
76    */
77   List<List<TreeNode<E>>> levelOrder(TreeNode<E> x);
78 
79   List<List<TreeNode<E>>> levelOrder();
80 }

3、MyTree类:

  注意这儿层次遍历这个函数,用到的bfs(宽度优先搜索),顾名思义就是遍历完每一层再接着遍历下一层。相比于DFS用的递归而言,那么bfs用到的技巧就是队列,口诀:(队)弹一个,加N个(队)。如果某行有n个节点,从1访问到n时,需要保存1的左右节点,2的左右节点,,,n的左右节点,遍历下行时的顺序是1的左右,2的左右,,,n的左右。这不就是先进(先保存)先出(先访问)吗?算法伪码:1.root进队(每个元素都要进队,别直接访问)2.开始循环:队首出队,其左右节点进队。(当然你也可以左右节点先进队,接着队首出队) 循环条件是队非空。

  但若是需要换行打印的话就比较麻烦了,第一行的换行很简单啊,root后直接换行。那么你已经知道了第一行的换行,你就知道了第二行的换行位置啊,毕竟第二行都是第一行的“映射”。所以呢,跟刚才一样,在访问第n行的时候就要保存第n+1行的最右信息,反正n+1行的最右就是从第n行的左节点(第n+1行的最左)开始迭代。那么就需要用到双指针:增加两个TreeNode:last和nlast。last:表示当前遍历层最右结点。nlast:表示下一层最右结点。遍历时,每次将nlast指向插入队列元素,最后一个插入结点时即最右结点。插入左右孩子之后,检测last是否为当前输出结点,若是,则表示需要进行换行,并将last指向下一层的nlast。


  1 import java.util.ArrayList;
  2 import java.util.LinkedList;
  3 import java.util.List;
  4 import java.util.Queue;
  5 
  6 public class MyTree<E> implements ITree<E> {
  7     private int size = 0;
  8     private TreeNode root;
  9 
 10     public MyTree(TreeNode root) {
 11         this.root = root;
 12         size++;
 13     }
 14 
 15     @Override
 16     public int getSize() {
 17         return size;
 18     }
 19 
 20     @Override
 21     public TreeNode<E> getRoot() {
 22         return root;
 23     }
 24 
 25     @Override
 26     public TreeNode<E> getParent(TreeNode<E> x) {
 27         return x.parent;
 28     }
 29 
 30     @Override
 31     public TreeNode<E> getFirstChild(TreeNode<E> x) {
 32         return x.children.get(0);
 33     }
 34 
 35     @Override
 36     public TreeNode<E> getNextSibling(TreeNode<E> x) {
 37         List<TreeNode<E>> children = x.parent.children;
 38         int i = children.indexOf(x);
 39         // try {
 40         // return children.get(i + 1);
 41         // } catch (Exception e) {
 42         // return null;
 43         // }
 44         if (i == children.size() - 1) {
 45             return null;
 46         } else {
 47             return children.get(i + 1);
 48         }
 49     }
 50 
 51     /**
 52      * 获得整棵树的高度
 53      */
 54     public int getHeight() {
 55         return getHeight(root);
 56     }
 57     
 58     // dfs 深度优先遍历求高度
 59     @Override
 60     public int getHeight(TreeNode<E> x) {
 61         if (x.children == null) {
 62             return 0;
 63         } else {
 64             int h = 0;
 65             for (int i = 0; i < x.children.size(); i++) {
 66                 h = Math.max(h, getHeight(x.children.get(i)));
 67             }
 68             return h + 1;
 69         }
 70     }
 71 
 72     @Override
 73     public void insertChild(TreeNode<E> p, TreeNode<E> child) {
 74         if (p.children == null) {
 75             p.children = new ArrayList<>();
 76         }
 77         p.children.add(child);
 78         child.parent = p;
 79         size++;
 80     }
 81 
 82     @Override
 83     public void deleteChild(TreeNode<E> p, int i) {
 84         p.children.remove(i);
 85         size--;
 86     }
 87 
 88     // 因为这不是二叉树,所以先序等遍历就先不写
 89     @Override
 90     public List<TreeNode<E>> preOrder(TreeNode<E> x) {
 91         return null;
 92     }
 93 
 94     @Override
 95     public List<TreeNode<E>> postOrder(TreeNode<E> x) {
 96         return null;
 97     }
 98 
 99     // 层次遍历 bfs 宽度优先搜索 队列  口诀:(队)弹一个,加N个(队)
100     // 深搜 递归  
101     // 双指针 换行
102     @Override
103     public List<List<TreeNode<E>>> levelOrder(TreeNode<E> x) {
104         List<List<TreeNode<E>>> res = new ArrayList<>();// list的list
105         Queue<TreeNode<E>> q = new LinkedList<>();
106         q.add(x);// 初始化
107         TreeNode<E> last = x;// 标记上一行的最末节点
108         TreeNode<E> nLast = null;// 标记最新加入队列的节点
109         List<TreeNode<E>> l = new ArrayList<>();// 第一行的list
110         res.add(l);
111 
112         while (!q.isEmpty()) {
113             TreeNode<E> peek = q.peek();
114             // 把即将弹出的节点的子节点加入队列
115             if (peek.children != null) {
116                 for (TreeNode<E> n : peek.children) {
117                     q.add(n);
118                     nLast = n;
119                 }
120             }
121             l.add(q.poll());// 弹出,加入到当前层列表
122 
123             if (peek == last && !q.isEmpty()) {// 如果现在弹出的节点是之前标记的最后节点,就要换列表
124                 l = new ArrayList<>();
125                 res.add(l);
126                 last = nLast;
127             }
128         }
129         return res;
130     }
131 
132     @Override
133     public List<List<TreeNode<E>>> levelOrder() {
134         return levelOrder(root);
135     }
136 }

 

作者:|旧市拾荒|