Tree的遍歷與node定義學習

/* * 二叉樹節點 */public class Node {//數據項public long data;//左子節點public Node leftChild;//右子節點public Node rightChild;/** * 構造方法 * @param data */public Node(long data) {this.data = data;}}/* * 二叉樹 */public class Tree {//根節點public Node root;/** * 插入節點 * @param value */public void insert(long value,String sValue) {//封裝節點Node newNode = new Node(value);//引用當前節點Node current = root;//引用父節點Node parent;//如果root為null,也就是第一插入的時候if(root == null) {root = newNode;return;} else {while(true) {//父節點指向當前節點parent = current;//如果當前指向的節點數據比插入的要大,則向左走if(current.data > value) {current = current.leftChild;if(current == null) {parent.leftChild = newNode;return;}} else {current = current.rightChild;if(current == null) {parent.rightChild = newNode;return;}}}}}/** * 查找節點 * @param value */public Node find(long value) {//引用當前節點,從根節點開始Node current = root;//循環,只要查找值不等于當前節點的數據項while(current.data != value) {//進行比較,比較查找值和當前節點的大小if(current.data > value) {current = current.leftChild;} else {current = current.rightChild;}//如果查找不到if(current == null) {return null;}}return current;}/** * 刪除節點  刪除節點需要父子兩層指針 * @param value */public boolean delete(long value) {//引用當前節點,從根節點開始Node current = root;//應用當前節點的父節點Node parent = root;//是否為左節點boolean isLeftChild = true;while(current.data != value) {parent = current;//進行比較,比較查找值和當前節點的大小if(current.data > value) {current = current.leftChild;isLeftChild = true;} else {current = current.rightChild;isLeftChild = false;}//如果查找不到if(current == null) {return false;}}//刪除葉子節點,也就是該節點沒有子節點if(current.leftChild == null && current.rightChild == null) {if(current == root) {root = null;} else if(isLeftChild) {parent.leftChild = null;} else {parent.rightChild = null;}//current的右節點空,判斷current是parrent的左孩子?右孩子?決定current的leftchild插入位置} else if(current.rightChild == null) {if(current == root) {root = current.leftChild;}else if(isLeftChild) {parent.leftChild = current.leftChild;} else {//是右節點,比parent節點要大parent.rightChild = current.leftChild;}//current只有右孩子的情況,其次判斷current是parent的左右孩子,判斷插入parent的位置} else if(current.leftChild == null) {if(current == root) {root = current.rightChild;} else if(isLeftChild) {//current是parent的左孩子parent.leftChild = current.rightChild;} else {//current是parent的右孩子parent.rightChild = current.rightChild;}} else {//current既有左孩子,也有右孩子Node successor = getSuccessor(current);// 先處理刪除節點的父if(current == root) {root = successor;} else if(isLeftChild) {parent.leftChild = successor;} else{parent.rightChild = successor;}// 處理刪除節點的左節點successor.leftChild = current.leftChild;}return true;}public Node getSuccessor(Node delNode) {Node successor = delNode;Node successorParent = delNode;Node current = delNode.rightChild;//尋找右子樹的最左側節點,比被刪除節點稍微大一點while(current != null) {successorParent = successor;successor = current;current = current.leftChild; // 刪除節點的右子樹的最左側孩子節點}//被刪除的右孩子,不等于找到的最左側節點,successor就是右子樹的最左側孩子,successorParent是父節點//不等于就是找到了,if(successor != delNode.rightChild) {//將最左節點的右節點給父節點是左,比較小,所以放再leftsuccessorParent.leftChild = successor.rightChild;// 直接放到位置了successor.rightChild = delNode.rightChild;}return successor;}/** * 前序遍歷 */public void frontOrder(Node localNode) {if(localNode != null) {//訪問根節點System.out.println(localNode.data + " ");//前序遍歷左子樹frontOrder(localNode.leftChild);//前序遍歷右子樹frontOrder(localNode.rightChild);}}/** * 中序遍歷 */public void inOrder(Node localNode) {if(localNode != null) {//中序遍歷左子樹inOrder(localNode.leftChild);//訪問根節點System.out.println(localNode.data + " ");//中旬遍歷右子樹inOrder(localNode.rightChild);}}/** * 后序遍歷 */public void afterOrder(Node localNode) {if(localNode != null) {//后序遍歷左子樹afterOrder(localNode.leftChild);//后序遍歷右子樹afterOrder(localNode.rightChild);//訪問根節點System.out.println(localNode.data + " " );}}}