Java实现二叉搜索树及相关操作

本文主要是介绍Java实现二叉搜索树及相关操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

package com.tree;import com.tree.BitNode;/**** 二叉搜索树：一个节点的左子节点的关键字小于这个节点，右子节点的关键字大于或等于这个父节点** 注意：不适合插入相同关键字的节点
与平衡二叉树比较：不适合插入有序序列*/
public class SearchBinTree {public static void main(String[] args) {BitNode root = new BitNode();root.data = 6;int[] arr = { 1, 3, 9, 7, 0, 4 };for (int i = 0; i < arr.length; i++) {insert(root, arr[i]);}BinTree.levelTraverse(root);BitNode successor = getSuccessor(root);System.out.println("successor:" + successor.data);System.out.println("delete : " + delete(root, 1));BinTree.levelTraverse(root);// BinTree.levelTraverse(root);//// BitNode min = getMinNode(root);// System.out.println("min = " + min.data);//// BitNode max = getMaxNode(root);// System.out.println("max = " + max.data);}// 构造二叉搜索树public static void insert(BitNode root, int data) {BitNode node = new BitNode();node.data = data;if (root == null) {root = node;} else {if (data < root.data) {if (root.lchild == null) {root.lchild = node;} else {insert(root.lchild, data);}} else {if (root.rchild == null) {root.rchild = node;} else {insert(root.rchild, data);}}}}// 查找最小节点public static BitNode getMinNode(BitNode root) {BitNode current, min = null;current = root;while (current != null) {min = current;current = current.lchild;}return min;}// 查找最大节点public static BitNode getMaxNode(BitNode root) {BitNode current, max = null;current = root;while (current != null) {max = current;current = current.rchild;}return max;}// 查找public static BitNode find(BitNode root, int data) {BitNode current = root;while (current.data != data) {if (data < current.data)current = current.lchild;elsecurrent = current.rchild;if (current == null)return null;}return current;}// 得到简要被删除的节点的后继(中序遍历)public static BitNode getSuccessor(BitNode delNode) {BitNode successorParent = delNode;BitNode successor = delNode;BitNode current = delNode.rchild;while (current != null) {successorParent = successor;successor = current;current = current.lchild;}if (successor != delNode.rchild) {successorParent.lchild = successor.rchild;successor.rchild = delNode.rchild;}return successor;}// 删除一个节点----?删除根节点时会出现错误public static boolean delete(BitNode root, int data) {BitNode current = root;BitNode parent = root;boolean isLeftChild = true;while (current.data != data) {// search for nodeparent = current;if (data < current.data) { // go left?isLeftChild = true;current = current.lchild;} else { // go right?isLeftChild = false;current = current.rchild;}if (current == null) { // end of threturn false; // didn't find it}}// found node to delete// if no children, simply delete itif (current.lchild == null && current.rchild == null) {if (current == root) {// if rootroot = null; // tree is empty} else if (isLeftChild) {parent.lchild = null;// disconnect} else { // from parentparent.rchild = null;}} else if (current.rchild == null) {// if no right child replace with// left subtreeif (current == root) {root = current.lchild;} else if (isLeftChild) {parent.rchild = current.lchild;} else {parent.rchild = current.lchild;}} else if (current.lchild == null) {// if no left child replace with// right subtreeif (current == root) {root = current.rchild;} else if (isLeftChild) {parent.lchild = current.rchild;} else {parent.rchild = current.rchild;}} else {// two chiledren ,so replace with inorde successor//get successor of node to delete(current)BitNode successor = getSuccessor(current);//connect parent of current to successor insteadif(current == root){root = successor;} else if(isLeftChild){parent.lchild = successor;} else {parent.rchild = successor;}//connect successor to current's left childsuccessor.lchild = current.lchild;}return true;}}