Java数据结构和算法--树
(1)二叉树
package ChapterEight;class Tree {class Node {public long value;public Node leftChild;public Node rightChild;public Node(long value) {this.value = value;leftChild = null;rightChild = null;}}public Node root;public Tree() {root = null;}// 向树中插入一个节点public void insert(long value) {Node newNode = new Node(value);// 树是空的if (root == null)root = newNode;else {Node current = root;Node parentNode;while (true) {parentNode = current;if (value < current.value) {current = current.leftChild;// 要插入的节点为左孩子节点if (current == null) {parentNode.leftChild = newNode;return;}} else {// 要插入的节点为右孩子节点current = current.rightChild;if (current == null) {parentNode.rightChild = newNode;return;}}}}}// 先续遍历树中的所有节点public void preOrder(Node currentRoot) {if (currentRoot != null) {System.out.print(currentRoot.value + " ");preOrder(currentRoot.leftChild);preOrder(currentRoot.rightChild);}}// 中续遍历树中的所有节点public void inOrder(Node currentNode) {if (currentNode != null) {inOrder(currentNode.leftChild);System.out.print(currentNode.value + " ");inOrder(currentNode.rightChild);}}// 后续遍历树中的所有节点public void postOrder(Node currentNode) {if (currentNode != null) {postOrder(currentNode.leftChild);postOrder(currentNode.rightChild);System.out.print(currentNode.value + " ");}}public void traverse(int traverseType) {switch (traverseType) {case 1:preOrder(root);break;case 2:inOrder(root);break;case 3:postOrder(root);break;default:break;}}// 依据树节点的值删除树中的一个节点public boolean delete(int value) {// 遍历树过程中的当前节点Node current = root;// 要删除节点的父节点Node parent = root;// 记录树的节点为左孩子节点或右孩子节点boolean isLeftChild = true;while (current.value != value) {parent = current;// 要删除的节点在当前节点的左子树里if (value < current.value) {isLeftChild = true;current = current.leftChild;}// 要删除的节点在当前节点的右子树里else {isLeftChild = false;current = current.rightChild;}// 在树中没有找到要删除的节点if (current == null)return false;}// 要删除的节点为叶子节点if (current.leftChild == null && current.rightChild == null) {// 要删除的节点为根节点if (current == root)root = null;// 要删除的节点为左孩子节点else if (isLeftChild)parent.leftChild = null;// 要删除的节点为右孩子节点elseparent.rightChild = null;}// 要删除的节点有左孩子节点，没有右孩子节点else if (current.rightChild == null) {// 要删除的节点为根节点if (current == null)root = current.leftChild;// 要删除的节点为左孩子节点else if (isLeftChild)parent.leftChild = current.leftChild;// 要删除的节点为右孩子节点elseparent.rightChild = current.leftChild;}// 要删除的节点没有左孩子节点，有右孩子节点else if (current.leftChild == null) {// 要删除的节点为根节点if (current == root)root = root.rightChild;// 要删除的节点为左孩子节点else if (isLeftChild)parent.leftChild = current.rightChild;// 要删除的节点为右孩子节点elseparent.rightChild = current.rightChild;}// 要删除的接节点既有左孩子节点又有右孩子节点else {Node successor = getSuccessor(current);// 要删除的节点为根节点if (current == root)root = successor;// 要删除的节点为左孩子节点else if (isLeftChild)parent.leftChild = successor;// 要删除的节点为右孩子节点elseparent.rightChild = successor;}return true;}// 找到要删除节点的替补节点private Node getSuccessor(Node delNode) {// 替补节点的父节点Node successorParent = delNode;// 删除节点的替补节点Node successor = delNode;Node current = delNode.rightChild;while (current != null) {// successorParent指向当前节点的上一个节点successorParent = successor;// successor变为当前节点successor = current;current = current.leftChild;}// 替补节点的右孩子节点不为空if (successor != delNode.rightChild) {successorParent.leftChild = successor.rightChild;successor.rightChild = delNode.rightChild;}return successor;}}public class TreeApp {public static void main(String[] args) {Tree tree = new Tree();tree.insert(8);tree.insert(50);tree.insert(45);tree.insert(21);tree.insert(32);tree.insert(18);tree.insert(37);tree.insert(64);tree.insert(88);tree.insert(5);tree.insert(4);tree.insert(7);System.out.print("PreOrder : ");tree.traverse(1);System.out.println();System.out.print("InOrder : ");tree.traverse(2);System.out.println();System.out.print("PostOrder : ");tree.traverse(3);System.out.println();System.out.println(tree.delete(7));System.out.print("PreOrder : ");tree.traverse(1);System.out.println();System.out.print("InOrder : ");tree.traverse(2);System.out.println();System.out.print("PostOrder : ");tree.traverse(3);System.out.println();}}