數(shù)組與鏈表區(qū)別：

二叉排序樹的創(chuàng)建和遍歷 代碼實現(xiàn)

package tree.binarysorttree;public class BinarySortTreeDemo {public static void main(String []args){int [] arr = {7,3,10,12,5,1,9};BinarySortTree binarySortTree = new BinarySortTree();//循環(huán)添加節(jié)點for (int i = 0; i < arr.length; i++) {binarySortTree.add(new Node(arr[i]));}//中序遍歷binarySortTree.infixOrder();} }//創(chuàng)建二叉排序樹 class BinarySortTree{private Node root;//添加節(jié)點的方法public void add(Node node){if (root == null){root = node;}else {root.add(node);}}//中序遍歷public void infixOrder(){if (root != null){root.infixOrder();}else {System.out.println("二叉排序樹為空,無法遍歷");}} }//創(chuàng)建節(jié)點 class Node{int value;Node left;Node right;public Node(int value) {this.value = value;}//添加節(jié)點的方法//遞歸的形式添加節(jié)點，滿足二叉排序樹public void add(Node node){if(node == null){return;}if (node.value < this.value){//當(dāng)前節(jié)點的左子節(jié)點為空直接掛上if (this.left == null){this.left = node;}else {//不為空遞歸向下this.left.add(node);}}else { //添加的節(jié)點的值大于等于當(dāng)前節(jié)點的值，右節(jié)點為空，掛到右節(jié)點if (this.right == null){this.right = node;}else{//不為空就掛上this.right.add(node);}}}//中序遍歷public void infixOrder(){if (this.left != null){this.left.infixOrder();}System.out.println(this);if (this.right != null){this.right.infixOrder();}}@Overridepublic String toString() {return "Node{" +"value=" + value +'}';} }

刪除：

編寫查找節(jié)點的方法

//查找要刪除的節(jié)點public Node search(int value){if (root == null){return null;}else {return root.search(value);}}//查找父節(jié)點public Node searchParent(int value){if (root == null){return null;}else{return root.searchParent(value);}}

刪除第三種需要用到的，查找以target.right為根節(jié)點節(jié)點的樹的最小值并刪除，然后返回value

//編寫一個方法,查找以傳入節(jié)點為根節(jié)點的二叉排序樹中的最小節(jié)點的值，并刪除此節(jié)點public int delRightTreeMin(Node node){Node target = node;//循環(huán)查找左節(jié)點，就會找到最小值while(target.left != null){target = target.left;}//刪除最小節(jié)點delNode(target.value);return target.value;}

刪除節(jié)點方法

public void delNode(int value){if (root == null){return;}else {//1.找到要刪除的節(jié)點Node targetNode = search(value);if (targetNode == null){return;}//如果二叉排序樹只有一個節(jié)點，并且刪除的此節(jié)點if (root.left == null && root.right == null){root = null;return;}//找到父節(jié)點Node parent = searchParent(value);//如果刪除的節(jié)點是葉子節(jié)點if (targetNode.left == null && targetNode.right == null){//第一種，刪除葉子if (targetNode.value < parent.value){ //比較大小判斷刪除的左葉子還是右葉子parent.left = null;}else {parent.right = null;}}else if (targetNode.left != null && targetNode.right != null){//刪除有兩棵子樹的(因為第二種判斷比較麻煩，所以直接寫在else里)//從target的右子樹找到最小節(jié)點,//用一個臨時變量存儲這個最小節(jié)點的value//刪除最小節(jié)點int min = delRightTreeMin(targetNode.right);//把最小節(jié)點的值賦給targetNodetargetNode.value = min;}else {//第二種，只有一棵子樹//如果要刪除的節(jié)點有左子節(jié)點if (targetNode.left != null){//如果只有根節(jié)點和一個葉子節(jié)點，要刪除根節(jié)點，那就要判斷根節(jié)點的父節(jié)點是否為空if (parent != null) {//如果targetNode是parent的左子節(jié)點if (parent.left.value == value) {parent.left = targetNode.left;} else {//targetNode是parent的右子節(jié)點parent.right = targetNode.left;}}else {root = targetNode.left;}}else {//要刪除的節(jié)點有右子節(jié)點if (parent != null) {if (parent.left.value == value) {//如果targetNode是parent的左子節(jié)點parent.left = targetNode.right;} else {//targetNode是parent的右子節(jié)點parent.right = targetNode.right;}}else {root = targetNode.right;}}}}}

完整代碼

package tree.binarysorttree;public class BinarySortTreeDemo {public static void main(String []args){int [] arr = {7,3,10,12,5,1,9,2};BinarySortTree binarySortTree = new BinarySortTree();//循環(huán)添加節(jié)點for (int i = 0; i < arr.length; i++) {binarySortTree.add(new Node(arr[i]));}//中序遍歷binarySortTree.infixOrder();//測試刪除binarySortTree.delNode(2);binarySortTree.delNode(5);binarySortTree.delNode(9);binarySortTree.delNode(12);binarySortTree.delNode(7);binarySortTree.delNode(3);binarySortTree.delNode(10);System.out.println();binarySortTree.infixOrder();} }//創(chuàng)建二叉排序樹 class BinarySortTree{private Node root;public Node getRoot() {return root;}//查找要刪除的節(jié)點public Node search(int value){if (root == null){return null;}else {return root.search(value);}}//查找父節(jié)點public Node searchParent(int value){if (root == null){return null;}else{return root.searchParent(value);}}//編寫一個方法,查找以傳入節(jié)點為根節(jié)點的二叉排序樹中的最小節(jié)點的值，并刪除此節(jié)點public int delRightTreeMin(Node node){Node target = node;//循環(huán)查找左節(jié)點，就會找到最小值while(target.left != null){target = target.left;}//刪除最小節(jié)點delNode(target.value);return target.value;}//刪除節(jié)點public void delNode(int value){if (root == null){return;}else {//1.找到要刪除的節(jié)點Node targetNode = search(value);if (targetNode == null){return;}//如果二叉排序樹只有一個節(jié)點，并且刪除的此節(jié)點if (root.left == null && root.right == null){root = null;return;}//找到父節(jié)點Node parent = searchParent(value);//如果刪除的節(jié)點是葉子節(jié)點if (targetNode.left == null && targetNode.right == null){//第一種，刪除葉子if (targetNode.value < parent.value){ //比較大小判斷刪除的左葉子還是右葉子parent.left = null;}else {parent.right = null;}}else if (targetNode.left != null && targetNode.right != null){//刪除有兩棵子樹的(因為第二種判斷比較麻煩，所以直接寫在else里)//從target的右子樹找到最小節(jié)點,//用一個臨時變量存儲這個最小節(jié)點的value//刪除最小節(jié)點int min = delRightTreeMin(targetNode.right);//把最小節(jié)點的值賦給targetNodetargetNode.value = min;}else {//第二種，只有一棵子樹//如果要刪除的節(jié)點有左子節(jié)點if (targetNode.left != null){//如果只有根節(jié)點和一個葉子節(jié)點，要刪除根節(jié)點，那就要判斷根節(jié)點的父節(jié)點是否為空if (parent != null) {//如果targetNode是parent的左子節(jié)點if (parent.left.value == value) {parent.left = targetNode.left;} else {//targetNode是parent的右子節(jié)點parent.right = targetNode.left;}}else {root = targetNode.left;}}else {//要刪除的節(jié)點有右子節(jié)點if (parent != null) {if (parent.left.value == value) {//如果targetNode是parent的左子節(jié)點parent.left = targetNode.right;} else {//targetNode是parent的右子節(jié)點parent.right = targetNode.right;}}else {root = targetNode.right;}}}}}//添加節(jié)點的方法public void add(Node node){if (root == null){root = node;}else {root.add(node);}}//中序遍歷public void infixOrder(){if (root != null){root.infixOrder();}else {System.out.println("二叉排序樹為空,無法遍歷");}} }//創(chuàng)建節(jié)點 class Node{int value;Node left;Node right;public Node(int value) {this.value = value;}//查找要刪除的節(jié)點public Node search(int value){if (value == this.value){//找到return this;}else if(value < this.value){//應(yīng)該向左繼續(xù)查找//如果左子節(jié)點為空就不能找了，說明不存在if (this.left == null) {return null;}return this.left.search(value);}else {if (this.right == null){return null;}return this.right.search(value);}}//查找要刪除節(jié)點的父節(jié)點public Node searchParent(int value){if ((this.left != null && this.left.value == value)||(this.right != null && this.right.value == value)){return this;}else {//如果查找的值小于當(dāng)前節(jié)點的值，并且當(dāng)前節(jié)點的左子節(jié)點不為空if (value < this.value && this.left != null){return this.left.searchParent(value);//像左子樹遞歸查找}else if (value >= this.value && this.right != null){return this.right.searchParent(value);//像右子樹遞歸查找}else {return null; //沒有父節(jié)點}}}//添加節(jié)點的方法//遞歸的形式添加節(jié)點，滿足二叉排序樹public void add(Node node){if(node == null){return;}if (node.value < this.value){//當(dāng)前節(jié)點的左子節(jié)點為空直接掛上if (this.left == null){this.left = node;}else {//不為空遞歸向下this.left.add(node);}}else { //添加的節(jié)點的值大于等于當(dāng)前節(jié)點的值，右節(jié)點為空，掛到右節(jié)點if (this.right == null){this.right = node;}else{//不為空就掛上this.right.add(node);}}}//中序遍歷public void infixOrder(){if (this.left != null){this.left.infixOrder();}System.out.println(this);if (this.right != null){this.right.infixOrder();}}@Overridepublic String toString() {return "Node{" +"value=" + value +'}';} }

總結(jié)

以上是生活随笔為你收集整理的数据结构 - 二叉排序树BST(创建、遍历、删除节点)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。