寒光博客

[java]Tree构造 及其简单的实现
Tree ITree Interface package _11_Tree._01_trie; import j...
扫描右侧二维码阅读全文
14
2019/11

[java]Tree构造 及其简单的实现

  1.  Home
  2. Text  
    3. Share to：

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 （寒光博客）”原创，转载请保留文章出处。
Last modification：November 14th, 2019 at 02:58 pm
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏

Leave a Comment