溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了Java排序二叉樹怎么定義的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Java排序二叉樹怎么定義文章都會有所收獲，下面我們一起來看看吧。
二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。是數據結構中的一類。
對于二叉排序樹的任何一個非葉子節點， 要求左子節點的值比當前節點的值小，右子節點的值比當前節點的值大。
對二叉排序樹進行中序遍歷，結果就是按從小到大排序的。
public class binarySortTree {
class Node{
int value;
Node left;
Node right;
public Node(int value){
this.value = value;
}
public void display(){
System.out.print(this.value + " ");
}
}
Node root;
}排序二叉樹添加節點的十分簡單，無論使用遞歸還是循環，思路都一樣，這里我用遞歸的方式講解。
每次添加一個節點時，判斷value(添加節點的值)與root的值的大小關系： 若root.value < value， 說明該節點應該添加在root的右子樹上。如果右子樹為空，直接添加：root.right = new Node(value)；如果右子樹不為空，那么遞歸進右子樹(令root.right為root)。
若root.value >= value， 說明該節點應該添加在root的左子樹上。如果左子樹為空，直接添加：root.left = new Node(value)；如果左子樹不為空，那么遞歸進右子樹(令root.left為root)。
代碼如下：
//添加節點
//此方法可以類內部方法的調用
private void add(Node root,int value){
//添加節點的值大于根節點的值，該節點添加到根節點的右子樹上
if(value > root.value){
//根節點的右子樹為空，直接添加
if(root.right == null){
root.right = new Node(value);
}
//根節點右子樹不為空，遞歸往右子樹插
else{
add(root.right,value);
}
}
//添加節點的值小于或者等于根節點的值，該節點應該添加到左子樹
else{
//左子樹為空，直接添加
if(root.left == null){
root.left = new Node(value);
}
//左子樹不為空，遞歸往左子樹添加
else{
add(root.left, value);
}
}
}
//此方法在類內部和類外部都可以調用
public void add(int value){
//當前樹為空樹
if(root == null){
root = new Node(value);
return;
}
add(root, value);
}因為二叉排序樹中序遍歷的結果就是排序好的，所以這里只提供中序遍歷。
代碼如下：
//中序遍歷樹
private void inPrevOrder(Node root){
if(root == null) return;
inPrevOrder(root.left);
root.display();
inPrevOrder(root.right);
}
public void inPrevOrder(){
System.out.print("中序遍歷：");
inPrevOrder(root);
}該方法是查找value在二叉樹中對應的位置，是為刪除節點提供的方法。
/**
* 通過value查找二叉樹中的節點
* @param root 被查找樹的根節點
* @param value 要查找的值
* @return 返回查找到的節點
*/
private Node searchNode(Node root, int value){
//被查找樹為null，要查找節點不存在
if(root == null)
return null;
//找到了，返回節點
else if(root.value == value){
return root;
}
//該節點不是要查找節點，繼續查找
else{
//該節點的值大于value，往該節點的左子樹遞歸查找
if(root.value > value){
return searchNode(root.left, value);
}
//該節點的值小于value,往該節點的右子樹遞歸查找
else{
return searchNode(root.right, value);
}
}
}該方法是查找二叉樹中一個節點的父節點，也是為刪除節點提供的方法。
/**
* 查找某節點的父節點，并返回
* @param root 被查找樹的根節點
* @param node 要查找的節點
* @return 返回被查找節點的父節點
*/
private Node searchParentNode(Node root, Node node){
//被查找樹為null或者根節點就是要查找的節點，那么要查找節點的父節點不存在
if(root == null || root == node){
return null;
}
else if(root.left != null && root.left == node || root.right != null && root.right == node){
return root;
}
else{
if(root.value > node.value){
return searchParentNode(root.left, node);
}
else{
return searchParentNode(root.right, node);
}
}
}刪除節點是排序二叉樹中最麻煩的方法，因為它有很多種情況。
方法如下：
第一種情況：刪除的節點是葉子節點
(1)需求先去找到要刪除的結點targetNode(2)找到targetNode的父結點parent
(3)確定targetNode是parent的左子結點還是右子結點
3.1如果targetNode是parent的左子結點:parent.left = null;
3.2如果targetNode是parent的右子結點:parent.right = null;
第二種情況:刪除只有一顆子樹的節點
(1)需求先去找到要刪除的結點targetNode(2)找到targetNode的父結點parent
(3)確定targetNode的子結點是左子結點還是右子結點
(4)確定targetNode是parent的左子結點還是右子結點
(5)如果targetNode有左子結點
5.1如果targetNode是parent的左子結點parent.left = targetNode.left;
5.2如果targetNode是parent的右子結點parent.right = targetNode.left;
(6)如果targetNode有右子結點
6.1如果targetNode是 parent 的左子結點parent.left = targetNode.right;
6.2如果targetNode是parent 的右子結點parent.right = targetNode.right
第三種情況：刪除的節點有左右兩個子樹
(1)需求先去找到要刪除的結點targetNode(2)在右子樹找到最小的節點，用一個temp保存這個節點的值，然后刪除這個最小節點(該最小節點一定是滿足第一種情況的)
(3)targetNode.value = temp
除了以上情況，還要考慮要刪除的節點就是根節點的情況(此時它的父節點為null)，下面會在代碼中展示，代碼如下：
public void remove(int vlaue){
//找到要刪除的節點
Node targetNode = searchNode(root,vlaue);
//要刪除節點不存在
if(targetNode == null) return;
//找到要刪除節點的父節點
Node targetNodeParent = searchParentNode(root,targetNode);
//要刪除節點為葉子節點
if(targetNode.left == null && targetNode.right == null){
//要刪除的節點就是根節點
if(targetNodeParent == null){
root = null;
}
else{
//要刪除節點是其父節點的左節點
if(targetNodeParent.left == targetNode){
targetNodeParent.left = null;
}
else{
targetNodeParent.right = null;
}
}
}
//要刪除節點只有一個左子樹
else if(targetNode.left != null && targetNode.right == null){
//要刪除的節點就是根節點
if(targetNodeParent == null) {
root = root.left;
}
//要刪除節點是其父節點的左節點
else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){
targetNodeParent.left = targetNode.left;
}
//要刪除節點是其父節點的右節點
else{
targetNodeParent.right = targetNode.left;
}
}
//要刪除節點只有一個右子樹
else if(targetNode.right != null && targetNode.left == null){
//要刪除的節點就是根節點
if(targetNodeParent == null) {
root = root.right;
return;
}
//要刪除節點是其父節點的左節點
else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){
targetNodeParent.left = targetNode.right;
}
//要刪除節點是其父節點的右節點
else{
targetNodeParent.right = targetNode.right;
}
}
//要刪除節點右左右都有節點
else{
//找到右子樹最小的節點
Node minNode = targetNode.right;
while(minNode.left != null){
minNode = minNode.left;
}
int temp = minNode.value;
//找到右子樹上最小節點的父節點
Node minNodeParent = searchParentNode(targetNode.right,minNode);
//右子樹根節點就是最小節點
if(minNodeParent == null){
targetNode.right = minNode.right;
}
else{
//要刪除節點是其父節點的左節點
minNodeParent.left = minNode.right;
}
targetNode.value = temp;
}
}關于“Java排序二叉樹怎么定義”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Java排序二叉樹怎么定義”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
