package datastruct;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BinarySearchTree<T extends Comparable<T>> {
TreeNode<T> root;
private T value;
private T postValue;
int count = 0;
int postCnt = 0;
private int temp = Integer.MIN_VALUE;
TreeNode<T> pre;
private T preValue;
private int preCnt;
public BinarySearchTree(T[] arr) {
root = createBinarySearchTree(arr, 0, arr.length - 1);
}
/**
*
* @param arr
* @param left
* @param right
* @return <p>
* Description:从有序的数组中构造一颗二叉搜索树
* </p>
*/
public TreeNode<T> createBinarySearchTree(T[] arr, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
// int mid=(left+right)/2;
TreeNode<T> root = new TreeNode(arr[mid]);
root.left = createBinarySearchTree(arr, left, mid - 1);
root.right = createBinarySearchTree(arr, mid + 1, right);
return root;
}
public <T extends Comparable<T>> TreeNode<T> getFather(TreeNode<T> root,
TreeNode<T> p, TreeNode<T> q) {
if (root == null || p.equals(root) || q.equals(root)) {
return root;
}
if (root.value.compareTo(p.value) > 0
&& root.value.compareTo(q.value) > 0) {
TreeNode<T> left = getFather(root.left, p, q);
return left;
}
if (root.value.compareTo(p.value) < 0
&& root.value.compareTo(q.value) < 0) {
TreeNode<T> right = getFather(root.right, p, q);
return right;
}
return root;
}
/*
* 寻找二叉查找树的第 k 个元素
*/
public T getK(TreeNode<T> root, int k) {
// /boolean flag=false;
Holder holder = new Holder();
inOrderTraversal(root, k, holder);
return value;
}
public void inOrderTraversal(TreeNode<T> root, int k, Holder holder) {
if (holder.flag == true) {
return;
}
if (root == null) {
return;
}
inOrderTraversal(root.left, k, holder);
count++;
if (count == k) {
value = root.value;
holder.flag = true;
// return;
}
System.out.println(count + "." + root.value + holder.flag);
inOrderTraversal(root.right, k, holder);
}
/**
*
* @param root
* @param p
* @return <p>
* Description: 查找指定元素的后继
* </p>
*/
public T getPostElement(TreeNode root, TreeNode p) {
Holder holder = new Holder();
inOrderTraversal(root, p, holder);
return postValue;
}
public void inOrderTraversal(TreeNode<T> root, TreeNode node, Holder holder) {
if (holder.flag == true) {
return;
}
if (root == null) {
return;
}
inOrderTraversal(root.left, node, holder);
postCnt++;
// System.out.println(postCnt+"."+root.value+holder.flag);
if (root.value.equals(node.value)) {
temp = postCnt;
}
if (postCnt == temp + 1) {
postValue = root.value;
holder.flag = true;
}
inOrderTraversal(root.right, node, holder);
}
public T getPreElement(TreeNode root, TreeNode p) {
inOrderTraversalPre(root, p);
return preValue;
}
public void inOrderTraversalPre(TreeNode<T> root, TreeNode node) {
if (root == null) {
return;
}
inOrderTraversalPre(root.left, node);
preCnt++;
if (preCnt == 1) {
preValue = null;
pre = root;
}
// System.out.println(preCnt+"."+root.value);
else {
if (!root.value.equals(node.value)) {
pre = root;
}
if (root.value.equals(node.value)) {
preValue = pre.value;
}
}
inOrderTraversalPre(root.right, node);
}
public boolean findTarget(TreeNode<Integer> root, Integer target) {
List<TreeNode> list = new ArrayList();
inOrder(root, list);
int left = 0;
int right = list.size() - 1;
while (left < right) {
TreeNode<Integer> node1 = list.get(left);
TreeNode<Integer> node2 = list.get(right);
if (node1.value + node2.value == target) {
return true;
} else if (node1.value + node2.value > target) {
right = right - 1;
} else {
left = left + 1;
}
}
return false;
}
public void inOrder(TreeNode<Integer> root, List list) {
if (root == null) {
return;
}
inOrder(root.left, list);
list.add(root);
inOrder(root.right, list);
}
public void printInorder(TreeNode root) {
if (root == null) {
return;
}
printInorder(root.left);
System.out.println(root.value);
printInorder(root.right);
}
/**
*
* @param head
* @return <p>
* Description:找有序链表的中间位置的前驱
* </p>
*/
public MyNode getPreOfMid(MyNode head) {
MyNode fast = head;
MyNode slow = head;
MyNode pre = head;
while (fast != null && fast.getNext() != null) {
pre = slow;
slow = slow.getNext();
fast = fast.getNext().getNext();
}
// System.out.println(slow.getData());
return pre;
}
public TreeNode sortedListToBST(MyNode head) {
if (head == null) {
return null;
}
if (head.getNext() == null) {
return new TreeNode(head.getData());
}
MyNode pre = getPreOfMid(head);
MyNode mid = pre.getNext();
pre.setNext(null);// 断开链表
TreeNode root = new TreeNode(mid.getData());
root.left = sortedListToBST(head);
root.right = sortedListToBST(mid.getNext());
return root;
}
public TreeNode<Integer> findMin(TreeNode<Integer> root) {
if (root == null) {
return null;
}
if (root.left == null) {
return root;
} else {
return findMin(root.left);
}
}
public TreeNode deleteMin(TreeNode root) {
if (root == null) {
return null;
} else if (root.left == null) {
TreeNode rightNode=root.right;
root.right=null;
return rightNode;
} else {
root.left = deleteMin(root.left);
return root;
}
}
public TreeNode delete(TreeNode<Integer> root, Integer vaInteger) {
if (root == null) {
return null;
}
if (root.value.compareTo(vaInteger)>0) {
// System.out.println("less than"+root.value);
root.left = delete(root.left, vaInteger);
return root;
} else if (root.value.compareTo(vaInteger)<0) {
// System.out.println("greater than"+root.value);
root.right = delete(root.right, vaInteger);
return root;
} else {
if (root.left == null) {
// System.out.println("left is null");
TreeNode rightNode=root.right;
root.right=null;
return rightNode;
} else if (root.right == null) {
// System.out.println("right child is null,left child is"+root.left.value);
TreeNode leftNode=root.left;
root.left=null;
return leftNode;
} else {
System.out.println("both not null"+root.value+","+root.left.value+","+root.right.value);
//TreeNode t = root;
TreeNode newroot = findMin(root.right);
newroot.left = root.left;
newroot.right = deleteMin(root.right);
System.out.println(root.value+","+root.left+","+root.right);
root.left=null;
root.right=null;
return newroot;
}
}
}
public static void main(String args[]) {
// Integer[] arr={0,2,3,4,5,6,7,8,9,10};
Integer[] arr = { 1, 2, 3, 4, 5, 6 };
Arrays.sort(arr);
BinarySearchTree<Integer> tree = new BinarySearchTree(arr);
//tree.printInorder(tree.root);
// System.out.println(tree.root.value);
// TreeNode<Integer> node1=new TreeNode(new Integer(0));
// TreeNode<Integer> node2=new TreeNode(new Integer(4));
// TreeNode<Integer> node3=new TreeNode(new Integer(2));
//
// TreeNode node=tree.getFather(tree.root,node1,node2);
// System.out.println(node.value);
// System.out.println("--------------");
// List<TreeNode> list=new ArrayList<TreeNode>();
// tree.inOrder(tree.root,list);
// for(TreeNode node4:list){
// System.out.println(node4.value);
// }
// System.out.println("--------------");
// boolean flag=tree.findTarget(tree.root, 21);
// System.out.println(flag);
// int e=tree.getK(tree.root, 2);
// System.out.println(e);
System.out.println("--------------");
// System.out.println("post");
// System.out.println(tree.getPostElement(tree.root, node2));
// System.out.println("pre");
//
// System.out.println(tree.getPreElement(tree.root, node2));
// System.out.println(tree.getPreElement(tree.root, node3));
MyNode head = new MyNode();
head.setData(-10);
MyNode node1 = new MyNode();
node1.setData(-3);
MyNode node2 = new MyNode();
node2.setData(0);
MyNode node3 = new MyNode();
node3.setData(5);
MyNode node4 = new MyNode();
node4.setData(9);
head.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
TreeNode root = tree.sortedListToBST(head);
//// System.out.println(root.value);
//List<TreeNode> list = new ArrayList();
// tree.inOrder(root, list);
//
// for(TreeNode node:list){
// System.out.print(node.value+",");
// }
// System.out.println(tree.deleteMin(tree.root.right.right).value);
TreeNode newRoot=tree.delete(root,0);
tree.printInorder(newRoot);
// System.out.println(newRoot.getValue());
// List<TreeNode> newList=new ArrayList();
// tree.inOrder(newRoot, newList);
// for(TreeNode node:newList){
// System.out.print(node.value+",");
// }
}
}
https://blog.csdn.net/itermeng/article/details/77763237
网友评论