目录
二分搜索树
树结构
树的概念
树是一种重要的**非线性**数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。
树的结点
树的每个元素都是一个节点,树有根节点,孩子结点,叶子节点,一棵树只能有一个根节点(对于非空树来说)
树按照最多有n个孩子节点就称为n叉树,如上图就是二叉树,只有两个孩子节点
二叉树
二叉树具有天然的递归结构
- 每个结点的左子树是也二叉树
- 每个结点的右子树是也二叉树
总结
- 一个层数为k 的满二叉树总结点数为：(2^k) -1
- 第i层上的结点数为：2^(i-1)
二分搜索树
概述
二分搜索树(Binary Search Tree) 也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树
二分搜索树的规则
对于二分搜索树的每个节点
- 结点的值大于左子树所有节点的值
- 结点的值小于右子树所有节点的值
二分搜索树的子树也是二分搜索树(递归结构)
注意:二分搜索树中存储的元素必须具有可比性
时间复杂度:
- 平均时间复杂度O(logn)
- 最差情况O(n)—(退化为了链表)
二分搜索树的实现
定义二分搜素树的基本结构和基本方法
要实现可比性,让树的存储内容<T>泛型实现 Comparable 接口,且接口的类型为泛型,从而实现数据可比性
public class BinarySearchTree<T extends Comparable<T>>
先定义树的结构,使用内部类定义树
//树的结点
class Node {
//结点的内容
private T val;
//左孩子结点
private Node left;
//右孩子结点
private Node right;
public Node(T val) {
this.val = val;
}
}
定义二分搜索树的属性方法
//根节点 二叉树的属性
private Node root;
//数的结点个数
private int size = 0;
//构造方法
public BinarySearchTree() {
this.root = null;
this.size = 0;
}
//获取树的节点个数
public int getSize(){
return this.size;
}
//判断树为空
public boolean isEmpty() {
return this.root == null;
}
@Override
public String toString() {
List<T> list = this.middleOrder();
StringBuilder sb = new StringBuilder();
list.forEach(item->sb.append(item+" "));
return sb.toString();
}
按值查找树中的结点
//查找树中的结点
public Node contains(T ele) {
return contains(root, ele);
}
//查找 遍历
private Node contains(Node node, T ele) {
//递归到底的情况
if (node == null) {
return null;
}
//递归操作
if (ele.compareTo(node.val) == 0) {//当前结点与目标值相同,返回当前结点
return node;
} else if (ele.compareTo(node.val) > 0) {//若目标值>当前结点值,从右子树找
return contains(node.right, ele);
} else {//若目标值<当前结点值,从左子树找
return contains(node.left, ele);
}
}
添加结点
//添加
public void add(T ele) {
//使用递归进行添加操作
root = add(root, ele);
this.size += 1;//结点个数+1
}
//添加递归
private Node add(Node root, T ele) {
//递归到底的情况
if (root == null) {
Node node = new Node(ele);
return node;
}
//递归操作
//比较要插入的值与树中已有结点大小,找到合适位置插入
if (ele.compareTo(root.val) > 0) {
root.right = add(root.right, ele);
} else if (ele.compareTo(root.val) < 0) {
root.left = add(root.left, ele);
}
return root;
}
查找最小结点
//查找最小结点
public T findMinNodeDG() {
if (root == null) {
return null;
}
return findMinNodeDG(root).val;
}
//查找最小结点递归
private Node findMinNodeDG(Node root) {
//递归到底的情况
if (root.left == null) {
return root;
}
//递归操作
return findMinNodeDG(root.left);
}
查找最大结点
//查找最大结点
public T findMaxNodeDG() {
if (root == null) {
return null;
}
return findMaxNodeDG(root).val;
}
//查找最大结点递归
private Node findMaxNodeDG(Node root) {
//递归到底的情况
if (root.right == null) {
return root;
}
//递归操作
return findMaxNodeDG(root.right);
}
删除最小结点
/**
* 删除最小结点
*/
public void removeMinNode() {
//先找到最小结点
T minNodeVal = findMinNodeDG();
//判断找到的最小结点
if (minNodeVal == null) {
//进行删除
throw new IllegalArgumentException("找不到该节点");
}
root = removeMinNodeDG(root);
this.size -= 1;
}
//删除最小结点递归
private Node removeMinNodeDG(Node node) {
if (node.left == null) {
//若左孩子为空进行删除操作
Node rightNode = node.right;
node.right = null;
return rightNode;
}
node.left = removeMinNodeDG(node.left);//左孩子不为空继续向左找
return node;
}
删除最大结点
//删除最大结点
public void removeMaxNode() {
//先找到最小结点
T maxNodeVal = findMaxNodeDG();
//判断找到的最小结点
if (maxNodeVal == null) {
//进行删除
throw new IllegalArgumentException("找不到该节点");
}
root = removeMaxNodeDG(root);
this.size -= 1;
}
//删除最大结点递归
private Node removeMaxNodeDG(Node node) {
if (node.right == null) {
//若右孩子为空进行删除操作
Node leftNode = node.left;
node.left = null;
return leftNode;
}
node.right = removeMaxNodeDG(node.right);//右孩子不为空继续向右找
return node;
}
查找任意节点
//查找任意结点
private Node findNodeDG(Node node, T val) {
//递归到底
if (node == null) {
return null;
}
//递归操作
if (node.val.compareTo(val) == 0) {
return node;
} else if (node.val.compareTo(val) > 0) {
return findNodeDG(node.left, val);
} else {
return findNodeDG(node.right, val);
}
}
删除任意节点
//删除任意结点
public T removeNode(T val) {
//边界判断
if (root == null) {
throw new IllegalArgumentException("树为空树!");
}
//查找结点
Node delNode = findNodeDG(root, val);
if (delNode != null) {
//删除操作
removeNodeDG(root, val);
this.size -= 1;
return delNode.val;//返回删除节点的值
}
return null;
}
/**
* 删除以root为根节点的二叉搜索树中值为val的结点
*
* @param node 根节点
* @param val 目标结点的值
* @return 删除目标结点之后二叉搜索树的根节点
*/
private Node removeNodeDG(Node node, T val) {
//找到目标结点时,执行删除操作
if (node.val.compareTo(val) == 0) {
if (node.left == null) {//左子树为空
Node rightNode = node.right;
node.right = null;
return rightNode;
} else if (node.right == null) {//右子树为空
Node leftNode = node.left;
node.left = null;
return leftNode;
} else { //左右子树都不为空
//1.找node的后继,从node.right中找到最小结点
Node s = findMinNodeDG(node.right);
//2.删除node.right中的最小结点并返回
Node rightNode = removeMinNodeDG(node.right);
//3.使用后继结点替换node
s.left = node.left;
s.right = rightNode;
//4.生成新树,新树的root就是node的后继
node.right = node.left = null;
//返回后继结点
return s;
}
}
if (node.val.compareTo(val) > 0) {
node.left = removeNodeDG(node.left, val);
} else {
node.right = removeNodeDG(node.right, val);
}
return node;
}
二叉树的遍历
前序遍历
对于当前节点，先输出该节点，然后输出它的左孩子，最后输出它的右孩子。
//前序遍历
public List<T> preOrder() {
//存储从树中遍历的值
List<T> res = new ArrayList<>();
//使用递归遍历
preOrder(root, res);
//返回存储树中元素的集合
return res;
}
//前序遍历 递归
private void preOrder(Node root, List<T> res) {
//递归到底的情况
if (root == null) {
return;
}
//递归操作
//先遍历root,再遍历左树,然后遍历右树
res.add(root.val);
preOrder(root.left, res);
preOrder(root.right, res);
}
中序遍历
首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回。
//中序遍历
public List<T> middleOrder() {
//存储从树中遍历的值
List<T> res = new ArrayList<>();
//使用递归遍历
middleOrder(root, res);
//返回存储树中元素的集合
return res;
}
//中序遍历 递归
private void middleOrder(Node root, List<T> res) {
//递归到底的情况
if (root == null) {
return;
}
//递归操作
//先遍历左树,再遍历root,然后遍历右数
middleOrder(root.left, res);
res.add(root.val);
middleOrder(root.right, res);
}
后序遍历
对于当前结点，先输出它的左孩子，然后输出它的右孩子，最后输出该结点
//后序遍历
public List<T> subOrder() {
//存储从树中遍历的值
List<T> res = new ArrayList<>();
//使用递归遍历
subOrder(root, res);
//返回存储树中元素的集合
return res;
}
//后序遍历 递归
private void subOrder(Node root, List<T> res) {
//递归到底的情况
if (root == null) {
return;
}
//递归操作
//先遍历左树,再遍历右树,然后取root
preOrder(root.left, res);
preOrder(root.right, res);
res.add(root.val);
}
层序遍历
//层序遍历 (广度优先)
public List<T> layerOrder() {
List<T> res = new ArrayList<>();
if (root != null) {
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
//从队列取出队首元素
Node node = queue.poll();
res.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return res;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/15616.html
