【数据结构】树

二叉排序树的实现

二叉排序树：左子节点小于父节点，右子节点大于父节点。

每一个节点在内存当中都是一个对象，通过类构建节点。(类是构建对象的模板)

手动构建： 

public class Test {
	public static void main(String[] args) {
		TreeNode node1 = new TreeNode(5);
		TreeNode node2 = new TreeNode(7);
		TreeNode node3 = new TreeNode(4);
		TreeNode node4 = new TreeNode(2);
		TreeNode node5 = new TreeNode(0);
		TreeNode node6 = new TreeNode(3);
		
		node1.setRightTreeNode(node2);
		node1.setLeftTreeNode(node3);
		node3.setLeftTreeNode(node4);
		node4.setLeftTreeNode(node5);
		node3.setRightTreeNode(node6);
		System.out.println(node1.toString());
	}
}

public class TreeNode {
	private int value;
	private TreeNode leftTreeNode;
	private TreeNode rightTreeNode;
	
	public TreeNode(int data) {
		this.value = data;
	}
	
	public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value = value;
	}
	public TreeNode getLeftTreeNode() {
		return leftTreeNode;
	}
	public void setLeftTreeNode(TreeNode leftTreeNode) {
		this.leftTreeNode = leftTreeNode;
	}
	public TreeNode getRightTreeNode() {
		return rightTreeNode;
	}
	public void setRightTreeNode(TreeNode rightTreeNode) {
		this.rightTreeNode = rightTreeNode;
	}
	
	@Override
	public String toString() {
		return "TreeNode [value=" + value + ", leftTreeNode=" + leftTreeNode + ", rightTreeNode=" + rightTreeNode + "]";
	}
}

自动构建：

public class Test {
	public static void main(String[] args) {
		BinaryTree binaryTree = new BinaryTree();
		binaryTree.insert(5);
		binaryTree.insert(7);
		binaryTree.insert(4);
		binaryTree.insert(2);
		binaryTree.insert(0);
		binaryTree.insert(3);
		System.out.println(binaryTree.root);
	}
}

public class BinaryTree {
	//定义一个头指针
	public TreeNode root;
	
	public void insert(int value) {
		//新建节点
		TreeNode newNode = new TreeNode(value);
		if (root == null) {
			root = newNode;
			return;
		}
		//定义一个指针来遍历整个树
		TreeNode currentNode = root;
		//定义一个指针指向currentNode的前一个节点，目的是为了方便插入
		TreeNode preNode;
		
		while (true) {
			preNode = currentNode;
			if (newNode.getValue() > currentNode.getValue()) {  //向右走
				currentNode = currentNode.getRightTreeNode();
				if (currentNode == null) {
					preNode.setRightTreeNode(newNode);
					return;
				}
			} else {  //向左走
				currentNode = currentNode.getLeftTreeNode();
				if (currentNode == null) {
					preNode.setLeftTreeNode(newNode);
					return;
				}
			}
		}
	}
}

public class TreeNode {
	private int value;
	private TreeNode leftTreeNode;
	private TreeNode rightTreeNode;
	
	public TreeNode(int data) {
		this.value = data;
	}
	
	public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value = value;
	}
	public TreeNode getLeftTreeNode() {
		return leftTreeNode;
	}
	public void setLeftTreeNode(TreeNode leftTreeNode) {
		this.leftTreeNode = leftTreeNode;
	}
	public TreeNode getRightTreeNode() {
		return rightTreeNode;
	}
	public void setRightTreeNode(TreeNode rightTreeNode) {
		this.rightTreeNode = rightTreeNode;
	}
	
	@Override
	public String toString() {
		return "TreeNode [value=" + value + ", leftTreeNode=" + leftTreeNode + ", rightTreeNode=" + rightTreeNode + "]";
	}
}

查询

深度优先遍历

中序遍历：023457

public void inOrder(TreeNode root) {
	if (root == null) {
		return;
	}
	inOrder(root.getLeftTreeNode());
	System.out.println(root.getValue());
	inOrder(root.getRightTreeNode());
}

先序遍历：542037

public void beforeOrder(TreeNode root) {
	if (root == null) {
			return;
	}
	System.out.println(root.getValue());
	beforeOrder(root.getLeftTreeNode());
	beforeOrder(root.getRightTreeNode());
}

后序遍历：032475

public void afterOrder(TreeNode root) {
	if (root == null) {
			return;
	}
	afterOrder(root.getLeftTreeNode());
	afterOrder(root.getRightTreeNode());
	System.out.println(root.getValue());
}

广度优先遍历

队列：先进先出

public void levelOrder() {
	//首先新建一个队列
	LinkedList<TreeNode> queue = new LinkedList<>();
	queue.add(root);  //将根节点放入
	while(!queue.isEmpty()) {
		//头节点出队列
		root = queue.pop();
		if(root.getLeftTreeNode() != null) {
			queue.add(root.getLeftTreeNode());
		}
		if(root.getRightTreeNode() != null) {
			queue.add(root.getRightTreeNode());
		}
	}
}

删除

删除叶子节点

① 找到要删除的节点target。

② 找到target的父节点parent(要考虑父节点是否存在)。

③ 确定要删除的target节点和parent节点的关系，是左子树还是右子树。

④ 根据第三步的情况进行删除。

删除只有一个节点的子树

① 找到要删除的节点target。

② 找到target的父节点parent(要考虑父节点是否存在)。

③ 确定要删除的target节点和parent节点的关系，是左子树还是右子树。

④ 确定target有的是左子树还是右子树。

⑤ 如果target有左子树

        target是parent的左子树：parent.left = target.left

        target是parent的右子树：parent.right = target.left

⑥ 如果target有右子树

        target是parent的左子树：parent.left = target.right

        target是parent的右子树：parent.right = target.right

删除有两个节点的子树

① 找到要删除的节点target。

② 找到target的父节点parent(要考虑父节点是否存在)。

③ 找到target右子树的最小值(或左子树的最大值)

④ 将右子树的最小值(或左子树的最大值)和target交换，然后删除右子树的最小值(或左子树的最大值)节点。

//找到要删除的节点
	public TreeNode search(TreeNode root, int value) {
		if (root == null) {
			return null;
		}
		if (value == root.getValue()) {
			return root;
		}else if(value < root.getValue()) {
			//判断左子树是否为空
			if (root.getLeftTreeNode() == null) {
				return null;
			}
			return search(root.getLeftTreeNode(), value);
		}else {
			//判断右子树是否为空
			if (root.getRightTreeNode() == null) {
				return null;
			}
			return search(root.getRightTreeNode(), value);
		}
	}
	//找到待删除的父节点
	public TreeNode searchParent(TreeNode root, int value) {
		if (root == null) {
			return null;
		}
		if ((root.getLeftTreeNode() != null && root.getLeftTreeNode().getValue() == value) || 
				(root.getRightTreeNode() != null) && root.getRightTreeNode().getValue() == value)) {
			return root;
		}else {
			if (root.getLeftTreeNode() != null && value < root.getValue()) {
				return searchParent(root.getLeftTreeNode(), value);
			}else if (root.getRightTreeNode() != null && value >= root.getValue()) {
				return search(root.getRightTreeNode(), value);
			}else {
				return null;
			}
		}
	}
	//找到右子树的最小值
	public int rightTreeNodeMin(TreeNode node) {
		TreeNode currentNode = node;
		while (currentNode.getLeftTreeNode() != null) {
			currentNode = currentNode.getLeftTreeNode();
		}
		return currentNode.getValue();
	}