java 实现 二叉树转二叉排序树(搜索树、查找树)

IT黑名单 2017-11-2 17:13:12

首先,何为二叉排序树?

二叉排序树是一颗空树或者具有以下性质的二叉树:

普通二叉树转换为二叉排序树的思路:

App.java //客户端入口类 num记录转换次数

public class App {
	public static void main(String[] args) throws Exception {
		work("21 22 33 34 25 26 27");
	}

	private static Node createTree(String[] array, int index) {
		Node tn = null;
		if (index < array.length) {
			tn = new Node(Integer.parseInt(array[index]));
			tn.setLeftChild(createTree(array, 2 * index + 1));
			tn.setRightChild(createTree(array, 2 * index + 2));
		}
		return tn;
	}
	private static int num = 0;
	private static void sort(BinaryTree tree, Node node) {
		if (node == null) {
			return;
		}
		Node left = node.getLeftChild();
		Node right = node.getRightChild();
		if (null == left)
			return;
		else {
			if (node.getValue() < left.getValue()) {
				num++;
				int value = left.getValue();
				tree.delete(value);
				tree.insert(value);
				sort(tree, node);
			} else {
				sort(tree, left);
			}
		}

		if (null == right)
			return;
		else {
			if (node.getValue() > right.getValue()) {
				num++;
				tree.delete(right.getValue());
				tree.insert(right.getValue());
				sort(tree, node);
			} else {
				sort(tree, right);
			}
		}
	}
	private static void work(String lineTwo) throws Exception {
		String[] array = lineTwo.split(" ");
		BinaryTree tree = new BinaryTree();
		tree.setRoot(createTree(array, 0));
		System.out.println(tree);
		sort(tree, tree.getRoot());
		System.out.println(num);
	}
}

BinaryTree.java // 二叉树类,其insert remove方法按二叉排序树实现

public class BinaryTree {
	private Node root;
	
	public BinaryTree() {}
	public BinaryTree(int value) {
		root = new Node(value);
	}
	
	public void insert(int value) {
		insert(value, this.root);
	}

	public void insert(int value, Node root) {
		Node node = new Node(value);
		if (null == this.root) {
			this.root = node;
		} else {
			if (root.getValue() > node.getValue()) {
				if (null != root.getLeftChild()) {
					insert(value, root.getLeftChild());
				} else {
					root.setLeftChild(new Node(value));
				}
			} else if (root.getValue() < node.getValue()) {
				if (null != root.getRightChild()) {
					insert(value, root.getRightChild());
				} else {
					root.setRightChild(new Node(value));
				}
			} else {
				root.setFrequency(root.getFrequency() + 1);
			}
		}
	}

	public boolean delete(int value) {
		Node node = remove(value, this.root);
		return null != node;
	}
	private Node remove(int value, Node node) {
		if(value==node.getValue()){
			if (node.getLeftChild() == null && node.getRightChild() == null) {
				Node parent = getParent(node);
				if(node == parent.getLeftChild())
					parent.setLeftChild(null);
				if(node==parent.getRightChild())
					parent.setRightChild(null);
				node = null;
			} else if (node.getLeftChild() != null && node.getRightChild() == null) {
				Node parent = getParent(node);
				if(node == parent.getLeftChild())
					parent.setLeftChild(node.getLeftChild());
				if(node==parent.getRightChild())
					parent.setRightChild(null);
				node = node.getLeftChild();
			} else if (node.getLeftChild() == null && node.getRightChild() != null) {
				Node parent = getParent(node);
				if(node == parent.getLeftChild())
					parent.setLeftChild(null);
				if(node==parent.getRightChild())
					parent.setRightChild(node.getRightChild());
				node = node.getRightChild();
			} else {
				Node newRoot = node.getRightChild();
				while (newRoot.getRightChild() != null) {
					newRoot = newRoot.getRightChild();
				}
				node.setValue(newRoot.getValue());
				remove(newRoot.getValue(), newRoot);
			}
		}else {
			if(null!=node.getLeftChild())
			remove(value, node.getLeftChild());
			if(null!=node.getRightChild())
				remove(value, node.getRightChild());
		}
		
		return node;
	}
	public boolean isLeft(Node node, Node subNode) {
		return subNode == node.getLeftChild();
	}
	public Node getParent(Node node){  
        if(node == root || root == null){
            return root;  
        }  
        return getParent(root,node);
    }  
	private Node getParent(Node subTreeNode, Node node) {  
        if(subTreeNode == null){
            return null;  
        }  
        if(subTreeNode.getLeftChild() == node || subTreeNode.getRightChild() == node){  
            return subTreeNode;
        }  
        Node parent = getParent(subTreeNode.getLeftChild(), node);
        if(parent != null){  
            return parent;  
        }  
        return getParent(subTreeNode.getRightChild(), node);
    } 
	
	public Node getRoot() {
		return root;
	}
	public void setRoot(Node root) {
		this.root = root;
	}
	
}

Node.java // 节点类 记录节点值、左右子节点  节点值重复时用计数器 frequency
public class Node {
	private int value;
	private Node leftChild = null;
	private Node rightChild = null;
	private int frequency = 1;
	
	public Node(int value) {
		this.value = value;
	}
	public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value = value;
	}
	public Node getLeftChild() {
		return leftChild;
	}
	public void setLeftChild(Node leftChild) {
		this.leftChild = leftChild;
	}
	public Node getRightChild() {
		return rightChild;
	}
	public void setRightChild(Node rightChild) {
		this.rightChild = rightChild;
	}
	public int getFrequency() {
		return frequency;
	}
	public void setFrequency(int frequency) {
		this.frequency = frequency;
	}
}


转载请注明来源【IT黑名单

本文链接:http://blog.itblacklist.cn/20171102/8461.html

© Copyright 2016 IT黑名单 Inc.All Rights Reserved. 豫ICP备15018592号-2