Tree
ITree Interface
package _11_Tree._01_trie;
import java.util.List;
public interface ITree<E> {
int getSize();//获取节点数
TreeNode<E> getRoot();//返回根
TreeNode<E> getParent(TreeNode<E> x);//返回节点的父节点
TreeNode<E> getFirstChild(TreeNode<E> x);//节点获取第一个孩子
TreeNode<E> getNextSibling(TreeNode<E> x);//返回一个节点的下一个兄弟
int getHeight(TreeNode<E> x);//子树高度
void insertChild(TreeNode<E> x,TreeNode<E> child);//插入子节点(孩子)
void deleteChild(TreeNode<E> x,int i);//删孩子 节点编号
List<TreeNode<E>> preOrder(TreeNode<E> x);//前序遍历 先根遍历BA-C
List<TreeNode<E>> postOrder(TreeNode<E> x);//后序遍历 后根遍历AC-B
List<List<TreeNode<E>>> levelOrder(TreeNode<E> x);//层次遍历 ABC-
//
}
MyTree
package _11_Tree._01_trie;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import static java.lang.Math.max;
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;
}
/**
* 返回节点的第一个孩子
*
* @param x
* @return
*/
@Override
public TreeNode<E> getFirstChild(TreeNode<E> x) {
return x.children.get(0);
}
/**
* 返回我的右边的兄弟
*
* @param x
* @return
*/
@Override
public TreeNode<E> getNextSibling(TreeNode<E> x) {
//回溯 认祖归宗 先找到父亲 然后得到孩子列表 获取我的位置 +1就是兄弟的位置
List<TreeNode<E>> children = x.parent.children;
int i = children.indexOf(x);//找到x的索引
try {
return children.get(i + 1);
} catch (Exception e) {//如果x的最后一个孩子
return null;
}
// if(i==children.size()-1){
// return null;
// }else{
// return children.get(i+1);
// }
}
/**
* 返回整棵树的高度
*
* @return
*/
public int getHeight() {
return getHeight(root);
}
/**
* 返回x的高度 DFS 递归算法
*
* @param x
* @return
*/
@Override
public int getHeight(TreeNode<E> x) {
if (x == null) {
return 0;
} else {
int h = 0;
for (int i = 0; i < x.children.size(); i++) {
h = max(h, getHeight(x.children.get(i)));
}
return h + 1;
}
}
/**
* 增加节点 父子关系
*
* @param parent
* @param child
*/
@Override
public void insertChild(TreeNode<E> parent, TreeNode<E> child) {
if (parent.children == null) {
parent.children = new ArrayList<>();
}
//双向确定关系
parent.children.add(child);
child.parent=parent;
size++;
}
/**
* 删除x节点的孩子 有问题!!
*
* @param x
* @param i
*/
@Override
public void deleteChild(TreeNode<E> x, int i) {
// int n = x.children.size();
// for (int j = n-1; j >=0; j--) {
// System.out.println(x.children.remove(j));
// size--;
// }
x.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个(队)
* 两个游标 来分层对比 出的最后一个 那么下一层进的也是最后一个
* @param x
* @return
*/
@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;
}
}
层次遍历
LevelOrder 深搜(dfs)用递归 宽搜(bfs)用队列
队列 (队)弹一个 加n个(队)

如何保持分层 用双指针标记 并依据 出的慢加的快
返回一个node列表的列表
/**
* bfs
* 深搜用递归 宽搜用队列
* 队列 (队)弹一个 加n个(队)
* 两个游标 来分层对比 出的最后一个 那么下一层进的也是最后一个
* @param x
* @return
*/
@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;
}
MyTreeTest
package _11_Tree._01_trie;
import org.junit.Before;
import org.junit.Test;
import java.util.List;
public class MyTreeTest {
MyTree tree = new MyTree(new TreeNode("a"));
TreeNode<String> root = tree.getRoot();
@Before
public void insertChild() {
//初始化跟节点
//要添加的节点
TreeNode<String> b = new TreeNode("b");
TreeNode<String> c = new TreeNode("c");
TreeNode<String> d = new TreeNode("d");
//bcd添加给a节点做儿子
tree.insertChild(root, b);
tree.insertChild(root, c);
tree.insertChild(root, d);
TreeNode<String> e = new TreeNode("e");
TreeNode<String> f = new TreeNode("f");
TreeNode<String> g = new TreeNode("g");
TreeNode<String> h = new TreeNode("h");
tree.insertChild(b, e);
tree.insertChild(b, f);
tree.insertChild(c, g);
tree.insertChild(d, h);
//e的子节点
TreeNode<String> i = new TreeNode("i");
TreeNode<String> j = new TreeNode("j");
tree.insertChild(e, i);
tree.insertChild(i, j);
}
@Test
public void getSize() {
System.out.println(tree.getSize());
}
@Test
public void getRoot() {
System.out.println(tree.getRoot());
}
@Test
public void getParent() {
System.out.println(tree.getParent(tree.getRoot()));
System.out.println(tree.getRoot().parent);
}
@Test
public void getFirstChild() {
TreeNode<String> root = tree.getRoot();
String key = (String) tree.getNextSibling(tree.getFirstChild(root)).key;
System.out.println(key);
}
@Test
public void getNextSibling() {
}
@Test
public void getHeight() {
}
@Test
public void getHeight1() {
}
@Test
public void deleteChild() {
System.out.println(tree.getSize());
System.out.println(tree.getFirstChild(tree.getRoot()));
tree.deleteChild(tree.getFirstChild(tree.getRoot()), 0);
System.out.println(tree.getSize());
}
@Test
public void preOrder() {
}
@Test
public void postOrder() {
}
@Test
public void levelOrder() {
List<List<TreeNode<String>>> lists = tree.levelOrder(root);
for (List<TreeNode<String>> list : lists) {
for (TreeNode<String> node : list) {
System.out.print(node.key + "\t");
}
System.out.println("--------");
}
}
}
本文作者:Author: 寒光博客
文章标题:[java]Tree构造 及其简单的实现
本文地址:https://dxoca.cn/java/319.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/java/319.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。