文章目录

代码实现节点实现类二叉树实现 单元测试

代码实现

节点实现类

package csdn.dreamzuora.tree; /** * Title: * Description: * * @version 1.0 * @author: weijie * @date: 2020/10/19 13:30 */ public interface Node { } package csdn.dreamzuora.tree; import java.io.Serializable; /** * Title: * Description: * * @version 1.0 * @author: weijie * @date: 2020/10/19 13:27 */ public abstract class AbstractNode<T, E> implements Node, Serializable { private static final long serialVersionUID = -2321782309212147194L; /** * 数据域 */ T data; /** * 左孩子 */ E left; /** * 右孩子 */ E right; public AbstractNode() { } public AbstractNode(T data) { this.data = data; } public T getData() { return data; } public void setData(T data) { this.data = data; } public E getLeft() { return left; } public void setLeft(E left) { this.left = left; } public E getRight() { return right; } public void setRight(E right) { this.right = right; } } package csdn.dreamzuora.tree; /** * Title: 二叉树节点 * Description: * * @version 1.0 * @author: weijie * @date: 2020/10/19 13:27 */ public class BinaryNode extends AbstractNode<Integer, BinaryNode>{ public BinaryNode(Integer data) { super(data); } }

二叉树实现

package csdn.dreamzuora.tree; import java.util.List; /** * Title: 树接口 * Description: * * @version 1.0 * @author: weijie * @date: 2020/10/16 14:56 */ public interface Tree<T,E> { /** * 构建树 * @param dataList */ void createTree(List<T> dataList); /** * 添加节点 * @param data */ E addNode(E tree, T data); /** * 删除节点 * @param tree * @param node */ void deleteNode(E tree, E node); /** * 前序遍历:根节点->左节点->右节点 */ void preOrder(List<T> list, E node); /** * 中序遍历：左节点->根节点->右节点 * @return */ void inOrder(List<T> list, E node); /** * 后序遍历：左节点->右节点->根节点 */ void laOrder(List<T> list, E node); /** * 广度优先遍历：层序遍历 * @param list * @param node */ void bfs(List<T> list, E node); } package csdn.dreamzuora.tree; import java.io.Serializable; import java.util.List; /** * Title: 二叉树抽象类 * Description: * * @version 1.0 * @author: weijie * @date: 2020/10/16 14:57 */ public abstract class AbstractTree<T, E> implements Tree<T, E>, Serializable { private static final long serialVersionUID = -8046156919125106629L; /** * 根节点 */ E root; @Override public void createTree(List<T> dataList) { for (T data : dataList){ root = addNode(root, data); } } } package csdn.dreamzuora.tree; import java.util.LinkedList; import java.util.List; /** * Title: 二叉树查找树 * Description: * * @version 1.0 * @author: weijie * @date: 2020/10/16 14:54 */ public class BinaryTree extends AbstractTree<Integer, BinaryNode>{ @Override public BinaryNode addNode(BinaryNode node, Integer data) { if (node == null){ return new BinaryNode(data); } if (node.data > data){ node.left = addNode(node.left, data); }else if (node.data < data){ node.right = addNode(node.right, data); }else { node.data = data; } return node; } @Override public void deleteNode(BinaryNode tree, BinaryNode node) { } @Override public void preOrder(List<Integer> list, BinaryNode node) { if (node == null){ return; } list.add(node.data); preOrder(list, node.left); preOrder(list, node.right); } @Override public void inOrder(List<Integer> list, BinaryNode node) { if (node == null){ return; } inOrder(list, node.left); list.add(node.data); inOrder(list, node.right); } @Override public void laOrder(List<Integer> list, BinaryNode node) { if (node == null){ return; } laOrder(list, node.left); laOrder(list, node.right); list.add(node.data); } @Override public void bfs(List<Integer> list, BinaryNode node) { if (node == null){ return; } LinkedList<BinaryNode> queue = new LinkedList<>(); queue.offer(node); while (!queue.isEmpty()){ BinaryNode child = queue.poll(); list.add(child.data); if (child.left != null){ queue.offer(child.left); } if (child.right != null){ queue.offer(child.right); } } } }

单元测试

package csdn.dreamzuora.tree; import org.junit.Before; import org.junit.Test; import org.junit.jupiter.api.Assertions; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import static org.junit.Assert.*; /** * Title: * Description: * * @version 1.0 * @author: weijie * @date: 2020/10/19 14:47 */ public class BinaryTreeTest { BinaryTree binaryTree = new BinaryTree(); @Before public void createTree(){ List<Integer> list = Arrays.asList(5, 4, 7, 2, 3, 6, 8); binaryTree.createTree(list); } @Test public void preOrder() { List<Integer> showList = new ArrayList<>(); binaryTree.preOrder(showList, binaryTree.root); List<Integer> predictList = Arrays.asList(5, 4, 2, 3, 7, 6, 8); Assertions.assertEquals(predictList.toString(), showList.toString()); } @Test public void inOrder() { List<Integer> showList = new ArrayList<>(); binaryTree.inOrder(showList, binaryTree.root); List<Integer> predictList = Arrays.asList(2, 3, 4, 5, 6, 7, 8); Assertions.assertEquals(predictList.toString(), showList.toString()); } @Test public void laOrder(){ List<Integer> showList = new ArrayList<>(); binaryTree.laOrder(showList, binaryTree.root); List<Integer> predictList = Arrays.asList(3, 2, 4, 6, 8, 7, 5); Assertions.assertEquals(predictList.toString(), showList.toString()); } @Test public void bfs(){ List<Integer> showList = new ArrayList<>(); binaryTree.bfs(showList, binaryTree.root); List<Integer> predictList = Arrays.asList(5, 4, 7, 2, 6, 8, 3); Assertions.assertEquals(predictList.toString(), showList.toString()); } }