Java基础复习笔记10数据结构-排序二叉树
?
package dateStructer.tree.orderTree;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queue;/** * 排序二叉树 * * @author liuyan */public class OrderTree {static class Node {Integer data;Node parent;Node left;Node right;public Node(Integer data, Node parent, Node left, Node right) {this.data = data;this.parent = parent;this.left = left;this.right = right;}@Overridepublic String toString() {return "[data:" + this.data + "]";}}private Node root;public OrderTree(Integer data) {root = new Node(data, null, null, null);}/** * 添加新节点 * * @param data */public void addNode(Integer data) {if (root == null) {root = new Node(data, null, null, null);return;}// 从根节点开始Node nowNode = root;Node newParent = null;do {newParent = nowNode;if (nowNode.data > data) {nowNode = nowNode.left;} else {nowNode = nowNode.right;}} while (nowNode != null);if (newParent.data > data) {newParent.left = new Node(data, newParent, null, null);} else {newParent.right = new Node(data, newParent, null, null);}}/** * 查找节点对象 * * @param data * @return */public Node findNode(Integer data) {Node nowNode = root;while (nowNode != null) {if (nowNode.data == data) {return nowNode;}if (nowNode.data > data) {nowNode = nowNode.left;} else {nowNode = nowNode.right;}}return null;}/** * 删除节点 * * @param data */public void deleteNode(Integer data) {Node tagNode = findNode(data);if (tagNode == null) {return;}if (tagNode == root) {root = null;}if (tagNode.left == null && tagNode.right == null) {if (tagNode.parent.left == tagNode) {tagNode.parent.left = null;} else if (tagNode.parent.right == tagNode) {tagNode.parent.right = null;}return;}if (tagNode.left == null && tagNode.right != null) {if (tagNode.parent.left == tagNode) {tagNode.parent.left = tagNode.right;} else if (tagNode.parent.right == tagNode) {tagNode.parent.right = tagNode.right;}return;}if (tagNode.left != null && tagNode.right == null) {if (tagNode.parent.left == tagNode) {tagNode.parent.left = tagNode.left;} else if (tagNode.parent.right == tagNode) {tagNode.parent.right = tagNode.left;}return;}Node leftMaxNode = tagNode.left;while (leftMaxNode.right != null) {leftMaxNode = leftMaxNode.right;}leftMaxNode.parent.right = null;leftMaxNode.parent = tagNode.parent;if (tagNode == tagNode.parent.left) {leftMaxNode.parent.left = leftMaxNode;} else {leftMaxNode.parent.right = leftMaxNode;}leftMaxNode.left = tagNode.left;leftMaxNode.right = tagNode.right;tagNode.left = null;tagNode.right = null;tagNode.parent = null;}public static List<Node> deepFirst(Node root) {List<Node> list = new ArrayList<Node>();Queue<Node> queue = new ArrayDeque<Node>();queue.add(root);while (!queue.isEmpty()) {list.add(queue.peek());Node twoLinkNode = queue.poll();if (twoLinkNode.left != null) {queue.add(twoLinkNode.left);}if (twoLinkNode.right != null) {queue.add(twoLinkNode.right);}}return list;}/** * @param args */public static void main(String[] args) {OrderTree orderTree = new OrderTree(7);orderTree.addNode(4);orderTree.addNode(1);orderTree.addNode(2);orderTree.addNode(5);orderTree.addNode(5);orderTree.addNode(13);orderTree.addNode(10);orderTree.addNode(12);orderTree.addNode(15);orderTree.addNode(14);orderTree.addNode(18);System.out.println(deepFirst(orderTree.root));orderTree.deleteNode(4);System.out.println(deepFirst(orderTree.root));}}
[[data:7], [data:4], [data:13], [data:1], [data:5], [data:10], [data:15], [data:2], [data:5], [data:12], [data:14], [data:18]]//删除后[[data:7], [data:2], [data:13], [data:1], [data:5], [data:10], [data:15], [data:5], [data:12], [data:14], [data:18]]
?
?
