【Java】高级数据结构算法 -- BST树

目录

基本概念

定义

前序、中序、后序遍历

前驱节点、后继节点（主要用于删除有两个孩子的节点）

代码实现（BST树的基本接口实现）

BST树的创建

插入（非递归、递归）

删除（递归、非递归）

查询（递归、非递归）

BST树的前序、中序、后序、层序遍历的递归实现

二叉搜索树( Tree)，(又:二叉搜索树，二叉排序树)它或者是一棵空树，或者是具有下列性质的二叉树: 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

基本概念 定义

二叉搜索树是一棵二叉树，如图所示。这样一棵树可以使用一个链表结构表示，其中每个结点就是一个对象。除了结点中的关键字外，每个结点还包含属性left、right、，它们分别指向结点的左孩子、右孩子和双亲。如果某个孩子结点和父结点不存在，则相应属性的值为。根结点是树中唯一父结点为nulll的结点。

前序、中序、后序遍历

二叉搜索树中的关键字总数以满足二叉搜索树性质的方式来存储：设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key≤x.key；如果y是x右子树中的一个结点，那么y.key≥x.key。

二叉搜索树的性质允许通过简单的递归算法来输出树中所有的关键字，有三种方式：先序遍历（VLR）、中序遍历(LVR)、后序遍历(LRV)。其中，前序遍历中输出根的关键字在其左右子树的关键字之前；中序遍历中输出根的关键词位于其左子树的关键字和右子树的关键字之间；后序遍历中输出根的关键字在左右子树的关键字之后。

前中后序遍历始终保持左孩子在右孩子之前，改变的只是父节点的遍历顺序，层序遍历则是在二叉树的基础上逐层遍历。下图二为上面二叉树前中后序遍历后的排序结果。

遍历一棵有n个结点的二叉搜索树需要耗费Θ(n)时间。

前驱节点、后继节点（主要用于删除有两个孩子的节点）

前驱节点：（待删除节点的左子树中，值最大的节点）

1.若一个节点有左子树，那么该节点的前驱节点是其左子树中val值最大的节点（也就是左子树中所谓的）

2.若一个节点没有左子树，那么判断该节点和其父节点的关系

2.1 若该节点是其父节点的右边孩子，那么该节点的前驱结点即为其父节点。

2.2 若该节点是其父节点的左边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的右边孩子，那么Q就是该节点的后继节点

        node = cur.left;while(cur.right != null)node = node.right;//node -> cur的前驱节点

后继节点：（待删除节点的右子树中，值最小的节点）

1.若一个节点有右子树，那么该节点的后继节点是其右子树中val值最小的节点（也就是右子树中所谓的）

2.若一个节点没有右子树，那么判断该节点和其父节点的关系

2.1 若该节点是其父节点的左边孩子，那么该节点的后继结点即为其父节点

2.2 若该节点是其父节点的右边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的左边孩子，那么Q就是该节点的后继节点

        node = cur.right;while(cur.left != null)node = node.left;//node -> cur的后继节点

代码实现（BST树的基本接口实现） BST树的创建

/*** BST树的节点类型* @param */
class BSTNode>{private T data; // 数据域private BSTNode left; // 左孩子域private BSTNode right; // 右孩子域public BSTNode(T data, BSTNode left, BSTNode right) {this.data = data;this.left = left;this.right = right;}public T getData() {return data;}public void setData(T data) {this.data = data;}public BSTNode getLeft() {return left;}public void setLeft(BSTNode left) {this.left = left;}public BSTNode getRight() {return right;}public void setRight(BSTNode right) {this.right = right;}
}

/*** BST树的实现* @param */
class BST>{private BSTNode root; // 指向根节点//BST树的初始化    public BST() {this.root = null;}

插入（非递归、递归）

/*** BST树的非递归插入操作* @param data*/public void non_insert(T data){// 1.判断如果root是null，如果root是null，直接生成根节点，让root指向，结束if(root == null){this.root = new BSTNode<>(data, null, null);return;}// 2.如果root不为空，从根节点开始搜索一个合适的位置，放新节点BSTNode cur = this.root;BSTNode parent = null; // this.rootwhile(cur != null){if(cur.getData().compareTo(data) > 0){parent = cur;cur = cur.getLeft();} else if(cur.getData().compareTo(data) < 0){parent = cur;cur = cur.getRight();} else {return;}}// 3.生成新节点，把节点的地址，写入父节点相应的地址域if(parent.getData().compareTo(data) > 0){parent.setLeft(new BSTNode(data, null, null));} else {parent.setRight(new BSTNode(data, null, null));}}

     /*** BST的递归插入函数接口* @param data*/public void insert(T data){this.root = insert (this.root,data);}//递归插入的具体实现函数private BSTNode insert(BSTNode root, T data) {if(root == null){return new BSTNode<> (data,null,null);}if(root.getData ().compareTo (data) > 0){root.setLeft ((insert (root.getLeft (),data)));}else if(root.getData ().compareTo (data) < 0){root.setRight (insert (root.getLeft (),data));}else {;}return root;}

删除（递归、非递归）

/*** 非递归实现BST树的删除操作* @param data*/public void non_remove(T data){if(this.root == null){return;}// 1. 先搜索BST树，找到待删除的节点BSTNode cur = this.root;BSTNode parent = null;while(cur != null){if(cur.getData().compareTo(data) > 0){parent = cur;cur = cur.getLeft();} else if(cur.getData().compareTo(data) < 0){parent = cur;cur = cur.getRight();} else {break;}}if(cur == null){ // 表示BST树中没有值为data的节点return;}// 2. 判断删除节点是否有两个孩子，如果有，用前驱的值代替，直接删除前驱if(cur.getLeft() != null && cur.getRight() != null){// 找前驱节点，用前驱节点的值代替待删节点的值，然后直接删除前驱节点curBSTNode old = cur;parent = cur;cur = cur.getLeft();while(cur.getRight() != null){parent = cur;cur = cur.getRight();}old.setData(cur.getData()); // 前驱节点的值代替待删节点的值}// 3. 删除有一个孩子的节点，或者没有孩子的节点（看作有一个孩子，孩子是null）BSTNode child = cur.getLeft();if(child == null){child = cur.getRight();}if(parent == null){ // 删除的就是根节点this.root = child;} else {if(parent.getLeft() == cur){parent.setLeft(child);} else {parent.setRight(child);}}}

/*** BST的递归删除函数接口* @param data*/public void remove(T data){this.root = remove (this.root,data);}/*** 递归删除的具体实现函数* @param root* @param data* @return*/
private BSTNode remove(BSTNode root, T data) {if(root == null){return null;}if(root.getData().compareTo(data) > 0){root.setLeft(remove(root.getLeft(), data));} else if(root.getData().compareTo(data) < 0){root.setRight(remove(root.getRight(), data));} else {if(root.getLeft() != null && root.getRight() != null){BSTNode pre = root;pre = pre.getLeft();while(pre.getRight() != null){pre = pre.getRight();}root.setData(pre.getData());root.setLeft(remove(root.getLeft(), pre.getData()));} else {if(root.getLeft() != null){return root.getLeft();} else if(root.getRight() != null){return root.getRight();} else {return null;}}}return root;}

查询（递归、非递归）

/**  * 非递归* 在BST树种，搜索值为data的节点，找到返回true，找不到返回false* @param data* @return*/public boolean non_query(T data){BSTNode cur = this.root;while(cur != null){if(cur.getData().compareTo(data) > 0){cur = cur.getLeft();} else if(cur.getData().compareTo(data) < 0){cur = cur.getRight();} else {return true;}}return false;}
}

/*** 递归查找元素data* @return*/public BSTNode query(T data){return query(this.root, data);}private BSTNode query(BSTNode root, T data) {if(root == null)return null;if(root.getData().compareTo(data) > 0){return query(root.getLeft(), data);} else if(root.getData().compareTo(data) < 0){return query(root.getRight(), data);} else {return root;}}

BST树的前序、中序、后序、层序遍历的递归实现

前序遍历

/*** 前序遍历BST树的API接口*/public void preOrder(){System.out.print("递归前序遍历:");preOrder(this.root);System.out.println();}/*** 前序遍历BST树的递归操作 VLR* @param root*/private void preOrder(BSTNode root) {if(root != null){System.out.print(root.getData() + " ");preOrder(root.getLeft());preOrder(root.getRight());}}

中序遍历

/*** 中序遍历BST树的API接口*/public void inOrder(){System.out.print("递归中序遍历:");inOrder(this.root);System.out.println();}/*** 中序遍历BST树的递归操作 LVR* @param root*/private void inOrder(BSTNode root) {if(root != null){inOrder(root.getLeft());System.out.print(root.getData() + " ");inOrder(root.getRight());}}

后序遍历

/*** 后序遍历BST树的API接口*/public void postOrder(){System.out.print("递归后序遍历:");postOrder(this.root);System.out.println();}/*** 后序遍历BST树的递归操作 LRV* @param root*/private void postOrder(BSTNode root) {if(root != null){postOrder(root.getLeft());postOrder(root.getRight());System.out.print(root.getData() + " ");}}

层序遍历

/*** 层序遍历BST树的API接口*/public void levelOrder(){System.out.print("递归层序遍历:");int hight = level();for (int i = 0; i < hight; i++) {levelOrder(this.root, i);}System.out.println();}/*** 层序遍历的递归实现* @param root* @param i*/private void levelOrder(BSTNode root, int i) {if(root != null){if(i == 0){System.out.print(root.getData() + " ");return;}levelOrder(root.getLeft(), i-1);levelOrder(root.getRight(), i-1);}}