平衡二叉树的java实现 -

sudongfeng

浏览: 8193 次
性别:
来自: 北京

最近访客更多访客>>

beer2008cn

woodding2008

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

平衡二叉树的java实现

博客分类：

数据结构与算法

数据结构二叉树

平衡二叉树求解步骤：

（1）插入节点
（2）找出不平衡因子，在插入过程中找到不平衡因子
（3）旋转，根据不平衡因子判断旋转方式
（4）生成新的平衡二叉树

在求解过程中，最重要步骤详解：

找出不平衡因子（也就是左右子树的高度差值为2或-2的情况）

方法1步骤：
a.节点中添加两个属性，左子树高度、右子树高度。
b.插入节点
c.返回的过程中动态的计算插入节点过程中经过的节点的左子树或右子树的高度。并计算各个节点的因子.
d.当节点因子为0时，返回过程中停止计算树的高度。当节点因子为2或-2时，即为不平衡因子，进行旋转
e.所有的旋转分为四种类型：LL顺时针旋转， RR逆时针旋转， LR先逆时针、然后顺时针，RL先顺时针在逆时针，旋转过程中调整各个节点的左右子树高度
f.旋转完成周调整，父节点的对应的左子树或者右子树的高度

这个方法通过给节点添加左右子树高度属性的方法，优点：节点的左右子树，只需要管理自己的高度，分而自治减少复杂性。代码中实现的是这个方法

package ProductCosume;

import java.util.Queue;
import java.util.Stack;

public class BinaryTreeTest {

	enum BalanceFactory {
		LeftFactory(1), RightFactory(-1), EqualFacotry(0), LeftLossBalanceFactory(
				2), RightLossBalanceFactory(-2), InvalideFactory(-3);
		int value = 0;

		private BalanceFactory(int value) {
			this.value = value;
		}
	}

	// 节点
	static class Node {

		public Node(int value) {
			key = value;
		}

		int key;
		private BalanceFactory af = BalanceFactory.EqualFacotry;

		Node leftNode = null;
		Node rightNode = null;
		Node parentNode = null;

		int leftNodeHeight = 0;
		int rightNodeHeight = 0;

		public int getNodeHeight() {
			return leftNodeHeight > rightNodeHeight ? leftNodeHeight
					: rightNodeHeight;
		}

		// 获取平衡因子
		public BalanceFactory getAf() {
			int factor = leftNodeHeight - rightNodeHeight;
			BalanceFactory resultBalanceFactory = null;
			switch (factor) {
			case 0:
				resultBalanceFactory = BalanceFactory.EqualFacotry;
				break;
			case 1:
				resultBalanceFactory = BalanceFactory.LeftFactory;
				break;
			case -1:
				resultBalanceFactory = BalanceFactory.RightFactory;
				break;
			case 2:
				resultBalanceFactory = BalanceFactory.LeftLossBalanceFactory;
				break;
			case -2:
				resultBalanceFactory = BalanceFactory.RightLossBalanceFactory;
				break;
			default:
				resultBalanceFactory = BalanceFactory.InvalideFactory;
				break;
			}
			af = resultBalanceFactory;
			return af;
		}
	}

	boolean isTaller = false;

	// 插入新的节点
	public Node inserNode(Node tree, Node node) {

		if (tree == null) {
			tree = node;
			return tree;
		}

		if (tree.key == node.key)
			return tree;

		Node parentNode = tree.parentNode;

		if (tree.key > node.key) {
			// 左路插入
			if (tree.leftNode == null) {
				tree.leftNode = node;
				node.parentNode = tree;
				tree.leftNodeHeight = tree.leftNodeHeight + 1;
				tree.getAf();
				isTaller = true;
				System.out.println("root:" + tree.key + " left insert "
						+ "  node:" + node.key);
				if (tree.getAf() == BalanceFactory.EqualFacotry)
					isTaller=false;
				return tree;
			} else {
				inserNode(tree.leftNode, node);
				if(isTaller){
					tree.leftNodeHeight = tree.leftNode.getNodeHeight() + 1;
					if (tree.getAf() == BalanceFactory.EqualFacotry)
						isTaller = false;
				}
			}
		} else {
			// 右路插入
			if (tree.rightNode == null) {
				tree.rightNode = node;
				node.parentNode = tree;
				tree.rightNodeHeight += 1;
				isTaller = true;
				System.out.println("root:" + tree.key + " right insert "
						+ "  node:" + node.key);
				if (tree.getAf() == BalanceFactory.EqualFacotry)
					isTaller=false;
				return tree;
			} else {
				inserNode(tree.rightNode, node);
				if(isTaller){
					tree.rightNodeHeight = tree.rightNode.getNodeHeight() + 1;
					if (tree.getAf() == BalanceFactory.EqualFacotry)
						isTaller = false;
				}
			}
		}

		if (isTaller) {
			boolean isRightNode = false;
			
			//非常重要：通过父亲类来判断插入到那一边
			if(parentNode!=null){
				if(parentNode.leftNode!=null&&parentNode.leftNode.key==tree.key)
					isRightNode = false;
				else
					isRightNode= true;
			}
			if (BalanceFactory.LeftLossBalanceFactory == tree.getAf()
					|| BalanceFactory.RightLossBalanceFactory == tree.getAf()) {
				
				tree = rotateTree(tree);
				if (parentNode != null){
					if(isRightNode)
						parentNode.rightNode = tree;
					else
						parentNode.leftNode = tree;
				}
			}
		}

		return tree;
	}

	// 破坏平衡旋转平衡二叉树
	public Node rotateTree(Node tree) {
		Node rootNode = tree;
		if (rootNode == null)
			return tree;
		System.out.println("旋转前------------------------------");
		widthSearch(rootNode);
		Node secondNode = null;

		if (rootNode.getAf() == BalanceFactory.RightLossBalanceFactory) {

			// 右边失去平衡
			secondNode = rootNode.rightNode;
			if (secondNode.af == BalanceFactory.RightFactory) {
				// RR类型
				System.out.println("RR类型旋转-------------");
				antiClockWiseRoate(tree);
			}

			if (secondNode.af == BalanceFactory.LeftFactory) {
				// RL类型的
				System.out.println("RL类型旋转-------------");
				clockwiseRotate(secondNode);
				secondNode = secondNode.parentNode;//注意，第二个点变化了
				widthSearch(secondNode);
				rootNode.rightNode = secondNode;
				antiClockWiseRoate(rootNode);
			}

		} else {
			// 左边失去平衡
			secondNode = rootNode.leftNode;
			if (secondNode.af == BalanceFactory.LeftFactory) {
				// LL类型
				System.out.println("LL类型旋转-------------");
				clockwiseRotate(tree);
			}

			if (secondNode.af == BalanceFactory.RightFactory) {
				// LR类型的
				System.out.println("LR类型旋转-------------");
				antiClockWiseRoate(secondNode);
				secondNode = secondNode.parentNode;//注意，第二个点变化了
				rootNode.leftNode = secondNode;
				widthSearch(secondNode);
				clockwiseRotate(tree);
			}
		}

		System.out.println("旋转后------------------------------");
		widthSearch(secondNode);

		System.out.println("旋转结束------------------------------");
		return secondNode;
	}

	// LL树 顺时针旋转
	public void clockwiseRotate(Node tree) {
		if (tree == null || tree.leftNode == null)
			return;

		Node secondNode = tree.leftNode;
		secondNode.parentNode = tree.parentNode;
		tree.parentNode = secondNode;
		tree.leftNode = secondNode.rightNode;
		secondNode.rightNode = tree;

		tree.leftNodeHeight = secondNode.rightNodeHeight;
		secondNode.rightNodeHeight = tree.getNodeHeight() + 1;
	}

	// RR树 逆时针旋转
	public void antiClockWiseRoate(Node tree) {
		if (tree == null || tree.rightNode == null)
			return;

		Node secondNode = tree.rightNode;
		secondNode.parentNode = tree.parentNode;
		tree.parentNode = secondNode;
		tree.rightNode = secondNode.leftNode;
		secondNode.leftNode = tree;

		tree.rightNodeHeight = secondNode.leftNodeHeight;
		secondNode.leftNodeHeight = tree.getNodeHeight() + 1;

	}

	public static void main(String[] args) {
		BinaryTreeTest binaryTreeTest = new BinaryTreeTest();
		Node node = new Node(8);
		binaryTreeTest.inserNode(null, node);

		Node node2 = new Node(10);
		Node node3 = new Node(16);
		Node node4 = new Node(6);
		Node node5 = new Node(3);
		Node node6 = new Node(78);
		Node node7 = new Node(9);
		Node node8 = new Node(24);
		Node node9 = new Node(15);
		Node node10 = new Node(19);
		Node node11 = new Node(2);
		Node node12 = new Node(45);
		Node node13 = new Node(65);
		Node node14 = new Node(78);
		Node node15 = new Node(102);
		Node node16 = new Node(1);
		Node node17 = new Node(32);
		Node node18 = new Node(33);

		Node root = binaryTreeTest.inserNode(node, node2);
		root = binaryTreeTest.inserNode(root, node3);
		root = binaryTreeTest.inserNode(root, node4);
		root = binaryTreeTest.inserNode(root, node5);
		root = binaryTreeTest.inserNode(root, node6);
		root = binaryTreeTest.inserNode(root, node7);
		root = binaryTreeTest.inserNode(root, node8);
		root = binaryTreeTest.inserNode(root, node9);
		root = binaryTreeTest.inserNode(root, node10);
		root = binaryTreeTest.inserNode(root, node11);
		root = binaryTreeTest.inserNode(root, node12);

		System.out.println("------------------------------");
		binaryTreeTest.widthSearch(root);

		root = binaryTreeTest.inserNode(root, node13);
		root = binaryTreeTest.inserNode(root, node14);
		root = binaryTreeTest.inserNode(root, node15);
		root = binaryTreeTest.inserNode(root, node16);
		root = binaryTreeTest.inserNode(root, node17);
		root = binaryTreeTest.inserNode(root, node18);
		binaryTreeTest.widthSearch(root);
	}

	public void widthSearch(Node node) {
		if (node != null) {
			System.out.println("node:" + node.key);
			widthSearch(node.leftNode);
			widthSearch(node.rightNode);
		}
	}

}

方法2：不需要左右子树的高度属性，每次计算各自的平衡因子

分享到：