java怎么实现平衡二叉树

104次阅读

共计 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
????}
}