一、树的基本知识
树是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点;除了根结点外,每个子结点可以分为多个不相交的子树;
import java.util.List; public class TreeNode<E> {
public E key;// data
public TreeNode<E> parent;// parent
public List<TreeNode<E>> children;// children public TreeNode(E key, TreeNode<E> parent) {
this.key = key;
this.parent = parent;
} public TreeNode(E key) {
this.key = key;
} @Override
public String toString() {
return "BSTNode [key=" + key + "]";
} }
2、树的接口类:
import java.util.List; public interface ITree<E> {
/**
* 节点数
* @return
*/
int getSize(); /**
* 获取根节点
* @return
*/
TreeNode<E> getRoot(); /**
* 获取x的父节点
* @param x
* @return
*/
TreeNode<E> getParent(TreeNode<E> x); /**
* 获取第一个儿子
* @param x
* @return
*/
TreeNode<E> getFirstChild(TreeNode<E> x); /**
* 获取x的下一个兄弟
* @param x
* @return
*/
TreeNode<E> getNextSibling(TreeNode<E> x); /**
* 子树高度
* @param x
* @return
*/
int getHeight(TreeNode<E> x); /**
* 插入子节点
* @param x
* @param child
*/
void insertChild(TreeNode<E> x, TreeNode<E> child); /**
* 删除第i个子节点
* @param x
* @param i
*/
void deleteChild(TreeNode<E> x, int i); /**
* 先序遍历
* @param x
* @return
*/
List<TreeNode<E>> preOrder(TreeNode<E> x); /**
* 后续遍历
* @param x
* @return
*/
List<TreeNode<E>> postOrder(TreeNode<E> x); /**
* 层次遍历
* @param x
* @return
*/
List<List<TreeNode<E>>> levelOrder(TreeNode<E> x); List<List<TreeNode<E>>> levelOrder();
}
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。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue; public class MyTree<E> implements ITree<E> {
private int size = 0;
private TreeNode root; public MyTree(TreeNode root) {
this.root = root;
size++;
} @Override
public int getSize() {
return size;
} @Override
public TreeNode<E> getRoot() {
return root;
} @Override
public TreeNode<E> getParent(TreeNode<E> x) {
return x.parent;
} @Override
public TreeNode<E> getFirstChild(TreeNode<E> x) {
return x.children.get(0);
} @Override
public TreeNode<E> getNextSibling(TreeNode<E> x) {
List<TreeNode<E>> children = x.parent.children;
int i = children.indexOf(x);
// try {
// return children.get(i + 1);
// } catch (Exception e) {
// return null;
// }
if (i == children.size() - 1) {
return null;
} else {
return children.get(i + 1);
}
} /**
* 获得整棵树的高度
*/
public int getHeight() {
return getHeight(root);
} // dfs 深度优先遍历求高度
@Override
public int getHeight(TreeNode<E> x) {
if (x.children == null) {
return 0;
} else {
int h = 0;
for (int i = 0; i < x.children.size(); i++) {
h = Math.max(h, getHeight(x.children.get(i)));
}
return h + 1;
}
} @Override
public void insertChild(TreeNode<E> p, TreeNode<E> child) {
if (p.children == null) {
p.children = new ArrayList<>();
}
p.children.add(child);
child.parent = p;
size++;
} @Override
public void deleteChild(TreeNode<E> p, int i) {
p.children.remove(i);
size--;
} // 因为这不是二叉树,所以先序等遍历就先不写
@Override
public List<TreeNode<E>> preOrder(TreeNode<E> x) {
return null;
} @Override
public List<TreeNode<E>> postOrder(TreeNode<E> x) {
return null;
} // 层次遍历 bfs 宽度优先搜索 队列 口诀:(队)弹一个,加N个(队)
// 深搜 递归
// 双指针 换行
@Override
public List<List<TreeNode<E>>> levelOrder(TreeNode<E> x) {
List<List<TreeNode<E>>> res = new ArrayList<>();// list的list
Queue<TreeNode<E>> q = new LinkedList<>();
q.add(x);// 初始化
TreeNode<E> last = x;// 标记上一行的最末节点
TreeNode<E> nLast = null;// 标记最新加入队列的节点
List<TreeNode<E>> l = new ArrayList<>();// 第一行的list
res.add(l); while (!q.isEmpty()) {
TreeNode<E> peek = q.peek();
// 把即将弹出的节点的子节点加入队列
if (peek.children != null) {
for (TreeNode<E> n : peek.children) {
q.add(n);
nLast = n;
}
}
l.add(q.poll());// 弹出,加入到当前层列表 if (peek == last && !q.isEmpty()) {// 如果现在弹出的节点是之前标记的最后节点,就要换列表
l = new ArrayList<>();
res.add(l);
last = nLast;
}
}
return res;
} @Override
public List<List<TreeNode<E>>> levelOrder() {
return levelOrder(root);
}
}