【数据结构】树

二叉排序树的实现

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

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

手动构建：

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;}@Overridepublic 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;}@Overridepublic 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();}