// 返回左子樹的高度
public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}
// 返回右子樹的高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}
// 返回 以該結點為根結點的樹的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
//左旋轉方法
private void leftRotate() {
//創建新的結點，以當前根結點的值
Node newNode = new Node(value);
//把新的結點的左子樹設置成當前結點的左子樹
newNode.left = left;
//把新的結點的右子樹設置成帶你過去結點的右子樹的左子樹
newNode.right = right.left;
//把當前結點的值替換成右子結點的值
value = right.value;
//把當前結點的右子樹設置成當前結點右子樹的右子樹
right = right.right;
//把當前結點的左子樹(左子結點)設置成新的結點
left = newNode;
}
//右旋轉
private void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
// 查找要删除的結點
/**
*
* @param value
* 希望删除的結點的值
* @return 如果找到返回該結點，否則返回null
*/
public Node search(int value) {
if (value == this.value) { // 找到就是該結點
return this;
} else if (value < this.value) {// 如果查找的值小於當前結點，向左子樹遞歸查找
// 如果左子結點為空
if (this.left == null) {
return null;
}
return this.left.search(value);
} else { // 如果查找的值不小於當前結點，向右子樹遞歸查找
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
// 查找要删除結點的父結點
/**
*
* @param value
* 要找到的結點的值
* @return 返回的是要删除的結點的父結點，如果沒有就返回null
*/
public Node searchParent(int value) {
// 如果當前結點就是要删除的結點的父結點，就返回
if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
return this;
} else {
// 如果查找的值小於當前結點的值, 並且當前結點的左子結點不為空
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; // 沒有找到父結點
}
}
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
// 添加結點的方法
// 遞歸的形式添加結點，注意需要滿足二叉排序樹的要求
public void add(Node node) {
if (node == null) {
return;
}
// 判斷傳入的結點的值，和當前子樹的根結點的值關系
if (node.value < this.value) {
// 如果當前結點左子結點為null
if (this.left == null) {
this.left = node;
} else {
// 遞歸的向左子樹添加
this.left.add(node);
}
} else { // 添加的結點的值大於 當前結點的值
if (this.right == null) {
this.right = node;
} else {
// 遞歸的向右子樹添加
this.right.add(node);
}
}
//當添加完一個結點後，如果: (右子樹的高度-左子樹的高度) > 1 , 左旋轉
if(rightHeight() - leftHeight() > 1) {
//如果它的右子樹的左子樹的高度大於它的右子樹的右子樹的高度
if(right != null && right.leftHeight() > right.rightHeight()) {
//先對右子結點進行右旋轉
right.rightRotate();
//然後在對當前結點進行左旋轉
leftRotate(); //左旋轉..
} else {
//直接進行左旋轉即可
leftRotate();
}
return ; //必須要!!!
}
//當添加完一個結點後，如果 (左子樹的高度 - 右子樹的高度) > 1, 右旋轉
if(leftHeight() - rightHeight() > 1) {
//如果它的左子樹的右子樹高度大於它的左子樹的高度
if(left != null && left.rightHeight() > left.leftHeight()) {
//先對當前結點的左結點(左子樹)->左旋轉
left.leftRotate();
//再對當前結點進行右旋轉
rightRotate();
} else {
//直接進行右旋轉即可
rightRotate();
}
}
}
// 中序遍曆
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}