樹的主要算法有插入，查找，顯示，遍歷，刪除，其中顯示和刪除略微復雜。

package chap08.tree;import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack;class Node {public int iData;public double dData;public Node leftChild;public Node rightChild;public void displayNode() {System.out.print("{" + iData + ", " + dData + "}");} }class Tree {// first node of treeprivate Node root; public Tree() {root = null;} /** 查找*/public Node find(int key) { // (assumes non-empty tree)Node current = root; // start at rootwhile (current.iData != key) // while no match, {if (key < current.iData) { current = current.leftChild;}else {current = current.rightChild;}if (current == null) {return null; }}return current; // found it } /** 插入*/public void insert(int id, double dd) {Node newNode = new Node(); // make new nodenewNode.iData = id; // insert datanewNode.dData = dd;if (root == null) { // no node in rootroot = newNode;}else // root occupied {Node current = root; // start at root Node parent;while (true) // (exits internally) {parent = current;if (id < current.iData) {current = current.leftChild;if (current == null) { // insert on leftparent.leftChild = newNode;return;}} else {current = current.rightChild;if (current == null) { // insert on rightparent.rightChild = newNode;return;}} } } } /** 刪除*/public boolean delete(int key) { // (assumes non-empty list)Node current = root;Node parent = root;boolean isLeftChild = true;// search for nodewhile (current.iData != key) {parent = current;if (key < current.iData) // go left? {isLeftChild = true;current = current.leftChild;} else {isLeftChild = false;current = current.rightChild;}if (current == null) // end of the line,return false; // didn't find it } // if no children, simply delete itif (current.leftChild == null && current.rightChild == null) {if (current == root) {root = null; }else if (isLeftChild) {parent.leftChild = null; // disconnect }else {// from parentparent.rightChild = null;}}// if no right child, replace with left subtreeelse if (current.rightChild == null) {if (current == root) {root = current.leftChild;}else if (isLeftChild) {parent.leftChild = current.leftChild;}else {parent.rightChild = current.leftChild;}}// if no left child, replace with right subtreeelse if (current.leftChild == null)if (current == root)root = current.rightChild;else if (isLeftChild)parent.leftChild = current.rightChild;elseparent.rightChild = current.rightChild;// 有兩個孩子，則用中序后繼替代else {// get successor of node to delete (current)Node successor = getSuccessor(current);// connect parent of current to successor insteadif (current == root) {root = successor;}else if (isLeftChild) {parent.leftChild = successor;}else {parent.rightChild = successor;}// connect successor to current's left childsuccessor.leftChild = current.leftChild;} return true; } /** 獲取后繼* 返回具有倒數第二高的值的節點* 找到右孩子，然后右孩子的左子孫*/private Node getSuccessor(Node delNode) {Node successorParent = delNode;Node successor = delNode;// go to right childNode current = delNode.rightChild; while (current != null) { successorParent = successor;successor = current;// go to left childcurrent = current.leftChild; }// if successor not right childif (successor != delNode.rightChild) { // make connectionssuccessorParent.leftChild = successor.rightChild;successor.rightChild = delNode.rightChild;}return successor;}public void traverse(int traverseType) {switch (traverseType) {case 1:System.out.print("\nPreorder traversal: ");preOrder(root);break;case 2:System.out.print("\nInorder traversal: ");inOrder(root);break;case 3:System.out.print("\nPostorder traversal: ");postOrder(root);break;}System.out.println();}/** 先序遍歷*/private void preOrder(Node localRoot) {if (localRoot != null) {System.out.print(localRoot.iData + " ");preOrder(localRoot.leftChild);preOrder(localRoot.rightChild);}}/** 中序遍歷*/private void inOrder(Node localRoot) {if (localRoot != null) {inOrder(localRoot.leftChild);System.out.print(localRoot.iData + " ");inOrder(localRoot.rightChild);}}/** 后序遍歷*/private void postOrder(Node localRoot) {if (localRoot != null) {postOrder(localRoot.leftChild);postOrder(localRoot.rightChild);System.out.print(localRoot.iData + " ");}}/** 在控制臺打印顯示樹 * */public void displayTree() {// 全局棧，初始放入樹的根節點Stack globalStack = new Stack();globalStack.push(root);// 打印空格的數量int nBlanks = 32;// 是否為空的標識boolean isRowEmpty = false;while (isRowEmpty == false) {// 本地棧Stack localStack = new Stack();// 設置標識為空，后邊再根據實際情況判斷其是否不為空isRowEmpty = true;// 打印一定數量的空格，為了將節點 放置在適當的位置以滿足視覺效果上樹的形狀for (int j = 0; j < nBlanks; j++) {System.out.print(' ');}while (globalStack.isEmpty() == false) {// 當標識不為空時，從全局棧彈出棧頂節點Node temp = (Node) globalStack.pop();if (temp != null) {// 如果當前從全局棧彈出的棧頂元素 不為空，則打印當前節點數值，同時將其左右孩子節點放入本地棧 System.out.print(temp.iData);// 先放左孩子，后方右孩子，后邊轉移到全局棧后，可以反序，從而保證左孩子在右孩子頂端 localStack.push(temp.leftChild);localStack.push(temp.rightChild);// 如果當前全局棧彈出的節點有左孩子或右孩子if (temp.leftChild != null || temp.rightChild != null) {// 設置標識不為空isRowEmpty = false;}} else {// 如果當前從全局棧彈出的棧頂元素 為空，則打印"--"替代節點數值，同時將兩個空值放入本地棧System.out.print("-");localStack.push(null);localStack.push(null);}for (int j = 0; j < nBlanks * 2 - 1; j++) {System.out.print(' ');}} System.out.println();System.out.println();nBlanks /= 2;while (localStack.isEmpty() == false) {// 將本地棧的節點放入全局棧，進行反序，從而保證先處理左孩子 globalStack.push(localStack.pop());}} } } class TreeApp {public static void main(String[] args) throws IOException {int value;Tree theTree = new Tree();theTree.insert(50, 1.5);theTree.insert(25, 1.2);theTree.insert(75, 1.7);theTree.insert(12, 1.5);theTree.insert(37, 1.2);theTree.insert(43, 1.7);theTree.insert(30, 1.5);theTree.insert(33, 1.2);theTree.insert(87, 1.7);theTree.insert(93, 1.5);while (true) {System.out.print("Enter first letter of show, insert, find, delete, or traverse: ");int choice = getChar();switch (choice) {case 's':theTree.displayTree();break;case 'i':System.out.print("Enter value to insert: ");value = getInt();theTree.insert(value, value + 0.9);break;case 'f':System.out.print("Enter value to find: ");value = getInt();Node found = theTree.find(value);if (found != null) {System.out.print("Found: ");found.displayNode();System.out.print("\n");} else {System.out.print("Could not find ");}System.out.print(value + '\n');break;case 'd':System.out.print("Enter value to delete: ");value = getInt();boolean didDelete = theTree.delete(value);if (didDelete) {System.out.print("Deleted " + value + '\n');}else {System.out.print("Could not delete ");}System.out.print(value + '\n');break;case 't':System.out.print("Enter type 1, 2 or 3: ");value = getInt();theTree.traverse(value);break;default:System.out.print("Invalid entry\n");} } } /** 獲取輸入 */public static String getString() throws IOException {InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;}public static char getChar() throws IOException {String s = getString();return s.charAt(0);}public static int getInt() throws IOException {String s = getString();return Integer.parseInt(s);} }

?

轉載于:https://www.cnblogs.com/thlzhf/p/4088972.html

總結

以上是生活随笔為你收集整理的Java数据结构与算法(20) - ch08树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。