网站的后期维护工作一般做什么,重庆九龙坡区最新消息,wordpress不刷新播放器,海外网站代理顾名思义#xff0c;二叉搜索树是一棵二叉树#xff0c;每个节点就是一个对象#xff0c;这个对象包含属性left、right和parent。left指向节点的左孩子#xff0c;right指向节点的右孩子#xff0c;parent指向节点的父节点#xff08;双亲#xff09;。如果某个孩子节点…顾名思义二叉搜索树是一棵二叉树每个节点就是一个对象这个对象包含属性left、right和parent。left指向节点的左孩子right指向节点的右孩子parent指向节点的父节点双亲。如果某个孩子节点和父节点不存在则相应的属性为null。根节点是树中唯一父节点指针为null的节点。
二叉搜索树中的关键字满足以下性质
假设x是二叉搜索树中的一个节点如果y是x的左子树中的一个节点那么y.key ≤ x.key如果y是x右子树中的一个节点那么y.key ≥ x.key。
两棵二叉搜索树的示意图如下 二叉搜索树支持查询、求最大值、最小值以及追加和删除等操作其基于java的简单实现如下
/*** 数据结构-二叉搜索树*/
public class BinarySearchTree {/*** 树的根节点*/private Node root;/*** 根据关键字搜索节点** param key 关键字* return key所在的节点*/public Node search(int key) {Node node root;while (node ! null key ! node.key) {// 如果key小于当前节点的key则往左孩子节点找否则往右孩子节点找if (key node.key) {node node.left;} else {node node.right;}}return node;}/*** 获取key最小的节点** return key最小的节点*/public Node min() {return min(root);}/*** 获取以node为根的子树中key最小的节点** param node 子树根节点* return 子树中key最小的节点*/public Node min(Node node) {while (node.left ! null) {node node.left;}return node;}/*** 获取key最大的节点** return key最大的节点*/public Node max() {return max(root);}/*** 获取以node为根的子树中key最大的节点** param node 子树根节点* return 子树中key最大的节点*/public Node max(Node node) {while (node.right ! null) {node node.right;}return node;}/*** 向树中添加节点** param key 插入节点的key*/public void add(int key) {Node node root;Node temp null;// 寻找合适的节点添加新节点while (node ! null) {temp node;if (key node.key) {node node.left;} else {node node.right;}}Node newNode new Node();newNode.parent temp;newNode.key key;if (temp null) { // 该树上还没有节点root newNode;} else if (key temp.key) {temp.left newNode;} else {temp.right newNode;}}/*** 删除以key为关键字的节点** param key 关键字*/public void delete(int key) {Node node search(key);if (node.left null) {transplant(node, node.right);} else if (node.right null) {transplant(node, node.left);} else {Node min min(node.right);if (!min.parent.equals(node)) {transplant(min, min.right);min.right node.right;min.right.parent min;} transplant(node, min);min.left node.left;min.left.parent min;}}/*** 用node2为跟的子树替换node1为根的子树** param node1 子树1* param node2 子树2*/private void transplant(Node node1, Node node2) {// node1是根节点if (node1.parent null) {root node2;} else if (node1 node1.parent.left) { // 如果node1是左孩子node1.parent.left node2;} else { // 如果node1是右孩子node1.parent.right node2;}if (node2 ! null) {node2.parent node1.parent;}}public Node getRoot() {return root;}/*** 树上的节点*/public static class Node {/*** 节点关键字*/private int key;/*** 节点的左孩子*/private Node left;/*** 节点的右孩子*/private Node right;/*** 节点的父节点*/private Node parent;public int getKey() {return key;}public Node getLeft() {return left;}public Node getRight() {return right;}public Node getParent() {return parent;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Node node (Node) o;return key node.key Objects.equals(left, node.left) Objects.equals(right, node.right) Objects.equals(parent, node.parent);}Overridepublic int hashCode() {return Objects.hash(key, left, right, parent);}}
}
