要實現平衡二叉樹,可以使用紅黑樹或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
????} }
以上是使用AVL樹實現平衡二叉樹的示例代碼,其中包含了插入節點、平衡節點和中序遍歷等操作。你可以根據需要進行修改和擴展。