java怎么實現平衡二叉樹

136次閱讀

共計 2999 個字符，預計需要花費 8 分鐘才能閱讀完成。

要實現平衡二叉樹，可以使用紅黑樹或 AVL 樹這樣的自平衡二叉搜索樹。
以下是使用 AVL 樹實現平衡二叉樹的示例代碼：

// AVL 樹節點類
class Node {????int?val;
????int?height;
????Node?left;
????Node?right;
????Node(int?val)?{
????????this.val?=?val;
????????this.height?=?1;
????}
}
//?平衡二叉樹類
class?AVLTree?{
????private?Node?root;
????//?獲取節點的高度 
????private?int?getHeight(Node?node)?{
????????if?(node?==?null)?{
????????????return?0;
????????}
????????return?node.height;
????}
????//?更新節點的高度 
????private?void?updateHeight(Node?node)?{
????????node.height?=?Math.max(getHeight(node.left),?getHeight(node.right))?+?1;
????}
????//?獲取節點的平衡因子 
????private?int?getBalanceFactor(Node?node)?{
????????if?(node?==?null)?{
????????????return?0;
????????}
????????return?getHeight(node.left)?-?getHeight(node.right);
????}
????//?右旋操作 
????private?Node?rightRotate(Node?node)?{
????????Node?newRoot?=?node.left;
????????node.left?=?newRoot.right;
????????newRoot.right?=?node;
????????updateHeight(node);
????????updateHeight(newRoot);
????????return?newRoot;
????}
????//?左旋操作 
????private?Node?leftRotate(Node?node)?{
????????Node?newRoot?=?node.right;
????????node.right?=?newRoot.left;
????????newRoot.left?=?node;
????????updateHeight(node);
????????updateHeight(newRoot);
????????return?newRoot;
????}
????//?平衡節點 
????private?Node?balance(Node?node)?{
????????if?(node?==?null)?{
????????????return?null;
????????}
????????updateHeight(node);
????????int?balanceFactor?=?getBalanceFactor(node);
????????if?(balanceFactor?>?1)?{
????????????if?(getBalanceFactor(node.left)?>=?0)?{
????????????????return?rightRotate(node);
????????????}?else?{
????????????????node.left?=?leftRotate(node.left);
????????????????return?rightRotate(node);
????????????}
????????}?else?if?(balanceFactor?<?-1)?{
????????????if?(getBalanceFactor(node.right)?<=?0)?{
????????????????return?leftRotate(node);
????????????}?else?{
????????????????node.right?=?rightRotate(node.right);
????????????????return?leftRotate(node);
????????????}
????????}
????????return?node;
????}
????//?插入節點 
????public?void?insert(int?val)?{
????????root?=?insert(root,?val);
????}
????private?Node?insert(Node?node,?int?val)?{
????????if?(node?==?null)?{
????????????return?new?Node(val);
????????}
????????if?(val?<?node.val)?{
????????????node.left?=?insert(node.left,?val);
????????}?else?if?(val?>?node.val)?{
????????????node.right?=?insert(node.right,?val);
????????}?else?{
????????????//?如果樹中已經存在相同值的節點，則不進行插入 
????????????return?node;
????????}
????????return?balance(node);
????}
????//?中序遍歷 
????public?void?inorderTraversal()?{
????????inorderTraversal(root);
????}
????private?void?inorderTraversal(Node?node)?{
????????if?(node?==?null)?{
????????????return;
????????}
????????inorderTraversal(node.left);
????????System.out.print(node.val?+?"?");
????????inorderTraversal(node.right);
????}
}
//?測試代碼
public?class?Main?{
????public?static?void?main(String[]?args)?{
????????AVLTree?tree?=?new?AVLTree();
????????tree.insert(3);
????????tree.insert(2);
????????tree.insert(1);
????????
????????tree.inorderTraversal();??//?輸出：1?2?3
????}
}