ArrayList实现多叉树

- 日理万妓 2021-09-28 18:06 170阅读 0赞

**多叉树接口**

这个接口主要定义获取树的一些基本信息。如：获取节点数，获取根节点，获取一个节点的子节点/父节点以及对树进行遍历的方法。

import java.util.List;
    
    public interface Treeable<E> {
    	/**
    	 * 得到这棵树的节点数
    	 * @return
    	 */
    	int getSize();
    	
    	/**
    	 * 得到根节点
    	 * @return
    	 */
    	TreeNode<E> getRoot();
    	
    	/**
    	 * 得到节点e的父节点
    	 * @param e
    	 * @return
    	 */
    	TreeNode<E> getParent(TreeNode<E> e);
    	
    	/**
    	 * 得到e的第一个子节点
    	 * @param e
    	 * @return
    	 */
    	TreeNode<E> getFirstChild(TreeNode<E> e);
    	
    	/**
    	 * 得到e的下一个子节点
    	 * @param e
    	 * @return
    	 */
    	TreeNode<E> getNextSibling(TreeNode<E> e);
    	
    	/**
    	 * 这棵树的高度
    	 * @param e
    	 * @return
    	 */
    	int getHeight(TreeNode<E> e);
    
    	/**
    	 * 向父节点e插入一个子节点
    	 * @param e
    	 * @param child
    	 */
    	void insertChild(TreeNode<E> e,TreeNode<E> child);
    	
    	/**
    	 * 在节点e中删除第i个子节点
    	 * @param e
    	 * @param i
    	 */
    	void deleteChild(TreeNode<E> e,int i);
    
    	/**
    	 * 先根遍历
    	 * @param e
    	 * @return
    	 */
    	List<TreeNode<E>> preOrder(TreeNode<E> e);
    	
    	/**
    	 * 后根遍历
    	 * @param e
    	 * @return
    	 */
    	List<TreeNode<E>> postOrder(TreeNode<E> e);
    	
    	/**
    	 * 层次遍历
    	 * @param e
    	 * @return
    	 */
    	List<TreeNode<E>> levelOrder(TreeNode<E> e);
    }

**节点树**

定义树的节点，多叉树与二叉树最大的区别是子节点，这里使用列表来存储子节点。

import java.util.List;
    /**
     * 节点类,构成节点类的三要素:数据(内容),父节点,子节点
     * @author Admin
     *
     * @param <E>
     */
    public class TreeNode<E> {
    	public E data;//data即内容
    	public TreeNode<E> parent;//父节点
    	public List<TreeNode<E>> children;//子节点
    
    	public TreeNode(E data) {
    		this.data = data;
    	}
    	
    	public TreeNode(E data,TreeNode<E> parent) {
    		this.data = data;
    		this.parent = parent;
    	}
    }

**多叉树实现**

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    public class MyTree<E> implements Treeable<E>{
    	private int size = 0;//整棵树的节点数
    	private TreeNode<E> root;//根节点
    	
        //构造方法
    	public MyTree(TreeNode<E> 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> e) {
    		return e.parent;
    	}
    
    	@Override
    	public TreeNode<E> getFirstChild(TreeNode<E> e) {
    		return e.children.get(0);
    	}
    
    	@Override
    	public TreeNode<E> getNextSibling(TreeNode<E> e) {
    		List<TreeNode<E>> children = e.parent.children;
    		int i = children.indexOf(e);
    		try {
    			return children.get(i+1);
    		}catch(Exception e2) {
    			return null;
    		}
    	}
    
    	@Override
    	public int getHeight(TreeNode<E> e) {
    		if(e.children == null) {
    			return 0;
    		}else {
    			int h = 0;
    			for(int i=0;i<e.children.size();i++) {//此处使用dfs进行尝试取最大高度
    				h = max(h,getHeight(e.children.get(i)));
    			}
    			return h+1;//加上根节点
    		}
    	}
    
    	@Override 
    	public void insertChild(TreeNode<E> e, TreeNode<E> child) {
    		if(e.children == null) {
    			e.children = new ArrayList<>();
    		}
    		e.children.add(child);
    		child.parent = e;
    		size++;
    	}
    
    	@Override
    	public void deleteChild(TreeNode<E> e, int i) {
    		if(i<0 || i>=e.children.size()) {
    			throw new IndexOutOfBoundsException("下标不合法/下标越界");
    		}{
    			e.children.remove(i);
    			size--;
    		}
    	}
    
    	@Override
    	public List<TreeNode<E>> preOrder(TreeNode<E> e) {
    		// TODO Auto-generated method stub
    		return null;
    	}
    
    	@Override
    	public List<TreeNode<E>> postOrder(TreeNode<E> e) {
    		// TODO Auto-generated method stub
    		return null;
    	}
    	
    	/**
    	 * 换行式层序遍历
    	 * @param e
    	 * @return
    	 */
    	public List<List<TreeNode<E>>> levelOrder2(TreeNode<E> e){
    		List<List<TreeNode<E>>> ans = new ArrayList<>();
    		Queue<TreeNode<E>> q = new LinkedList<>();
    		q.add(e);
    		TreeNode<E> last = e;
    		TreeNode<E> nLast = null;
    		List<TreeNode<E>> l = new ArrayList<>();
    		ans.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<>();
    				ans.add(l);
    				last = nLast;
    			}
    		}
    		
    		return ans;
    	
    	}
    	
    	@Override
    	public List<TreeNode<E>> levelOrder(TreeNode<E> e) {
    		List<TreeNode<E>> ans = new ArrayList<TreeNode<E>>();
    		Queue<TreeNode<E>> que = new LinkedList<>();
    		que.add(e);
    		while(!que.isEmpty()) {//bfs核心,使用队列,弹一个加多个
    			ans.add(que.peek());
    			if(que.peek().children != null)que.addAll(que.element().children);
    			que.poll();
    		}
    		return ans;
    		
    	}
    	
    	private final int max(int a,int b) {
    		return a>b?a:b;
    	}
    }

**测试类**

import java.util.List;
    
    public class TestMyTree {
    	static MyTree<String> t1;
    	public static void main(String[] args) {
    		t1 = new MyTree<String>(new TreeNode<String>("a", null));
    		TreeNode<String> root = t1.getRoot();
    		//1层
    		TreeNode<String> b = new TreeNode<String>("b");
    		TreeNode<String> c = new TreeNode<String>("c");
    		TreeNode<String> d = new TreeNode<String>("d");
    		
    		//其他层
    		TreeNode<String> e = new TreeNode<String>("e");
    		TreeNode<String> f = new TreeNode<String>("f");
    		TreeNode<String> g = new TreeNode<String>("g");
    		TreeNode<String> h = new TreeNode<String>("h");
    
    		//将b、c、d分别挂到主节点上
    		t1.insertChild(root, b);
    		t1.insertChild(root, c);
    		t1.insertChild(root, d);
    		
    		t1.insertChild(b, e);
    		t1.insertChild(c, f);
    		t1.insertChild(d, g);
    		
    		TreeNode<String> i = new TreeNode<String>("i");
    		TreeNode<String> j = new TreeNode<String>("j");
    		
    		//将i和j挂到e节点上
    		t1.insertChild(e, i);
    		t1.insertChild(e, j);
    		
    		System.out.println("子节点数:"+t1.getSize());//子节点个数
    		System.out.println("root的子节点数量:"+root.children.size());
    		System.out.println("root的第一个子节点:"+root.children.get(0).data);
    		System.out.println("根节点的高度:"+t1.getHeight(root));
    		System.out.println();
    		//简单打印树
    		List<List<TreeNode<String>>> list = t1.levelOrder2(t1.getRoot());
    		for (List<TreeNode<String>> lst : list) {
    			for(TreeNode<String> n:lst) {
    				System.out.print(n.data+" ");
    			}
    			System.out.println();
    		}
    	}
    }

**输出信息**

子节点数:9
    root的子节点数量:3
    root的第一个子节点:b
    根节点的高度:3
    
    a 
    b c d 
    e f g 
    i j