二叉搜索树的创建
2018-01-19 本文已影响12人
随时学丫
快速排序
递归
- 从数组中选取一个基准值，最开始默认选择数组第一个。
- 重新排列数组，所有比基准值小的放在基准值左边，所有比基准值大的放在基准值右边。
- 不断递归重复以上步骤直到数组排序完成。
非递归
借助栈（先进后出）来存储每次迭代的下标，用于计算基准值
先将left和right入栈，以栈为空为循环终止条件，将right和left弹栈，根据left和tight来计算当前基准值，再根据快速排序的思想，比基准值大的放在基准值右边，比基准值小的放在基准值左边，使用 if 判断，并将当前的下标存入栈，不断的进行入栈弹栈和基准值的计算，达到数组快速排序的目的。
时间复杂度
最坏情况：每次选取的基准值都是最小或者最大值，那么每次都需要排序，需要比较n(n-1)/2次，为 O(n2)
平均情况：每次都基准值都是中间值，n不断进行二分，只能二分log2n次，最终需要计较nlogn次，为O(nlogn)
空间复杂度
需要借助一个栈来实现递归，若每次划分均匀，递归的高度是O(logn)，故递归后需要的栈空间为O(logn)。最坏的情况下，递归的高度是O(n)，需要的空间为O(n)。
稳定性
快速排序是不稳定的
快速排序有两个方向，左边的下标left一直往右走，条件是a[left]<=a[pivot]（pivot为中枢元素数组下标），一般取数组第0个元素。右边的下标right一直往左走，条件是a[right]>=a[pivot]。当left<=right，重复上面的过程，直到left>right。在中枢元素a[pivot]和a[j]交换时，有可能把前面元素的稳定性打乱，比如序列为{5,3,3,4,3,8,9,10,11}，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素 3 的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素a[pivot]和a[right] 交换的时候。
二叉查找树
定义
二叉查找树是一棵有序树，具有下列性质：
- 若任意节点的左子树不空，则左子树上所有节点的值均小雨它的根节点的值。
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。
- 任意节点的左、右子树也为二叉查找树。
- 没有键值相等的节点。
构建二叉查找树
递归
二叉查找树构建要先计算中间值，也就是根节点在数组中的值，创建根节点之后，在递归遍历左子树和右子树进行构建。
非递归
借助两个栈，一个存储数组中的左、右子树的数据下标以及根节点的下标，一个用于存储二叉树的当前节点，循环条件是存储下标的栈不为空，将左右子树的下标进行弹栈，并计算根节点下标，根据根节点下标创建根节点，然后分别存储左子树的左右下标，创建左子树，存储右子树左右下标，创建右子树，将下标和左右子树分别存储到对应的栈，栈是先进后出，存入顺序和获取数据的顺序相反。接着一直循环重复上面的步骤，直到二叉查找树被创建完成。
package dali;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
public class Sort {
public static void main(String[] args) {
int[] arr = { 12, 3, 5, 15, 9, 8, 6, 2, 7 };
// quickSort(arr, 0, arr.length-1);
nonRecrutQuickSort(arr);
System.out.println("快速排序");
printArr(arr);
Node root = null;
Node node = null;
// System.out.println("递归构造二叉查找树");
// node = retrutSortedArrayToBST(root, arr, 0, arr.length - 1);
System.out.println("非递归构造二叉查找树");
node = nonRetrutSortedArrayToBST(arr);
System.out.println("前序递归遍历");
printTree(recrutPreorderTraversal(node));
System.out.println("前序非递归遍历");
printTree(nonRecrutPreorderTraversal(node));
System.out.println("中序递归遍历");
printTree(recrutInorderTraversal(node));
System.out.println("中序非递归遍历");
printTree(nonRecrutInorderTraversal(node));
System.out.println("后序递归遍历");
printTree(recrutPostorderTraversal(node));
System.out.println("后序非递归遍历");
printTree(nonRecrutPostorderTraversal(node));
}
//递归快速排序
public static void quickSort(int[] arr, int left, int right) {
if (left > right)
return;
int mid = partition(arr, left, right);
quickSort(arr, left, mid - 1);
quickSort(arr, mid + 1, right);
}
//非递归快速排序
public static void nonRecrutQuickSort(int[] arr) {
if (arr.length == 0)
return;
int left = 0;
int right = arr.length - 1;
int pivotPos;
Stack<Integer> stack = new Stack<>();
stack.push(left);
stack.push(right);
while (!stack.isEmpty()) {
right = stack.pop();
left = stack.pop();
pivotPos = partition(arr, left, right);
if (left < pivotPos - 1) {
stack.push(left);
stack.push(pivotPos - 1);
}
if (right > pivotPos + 1) {
stack.push(pivotPos + 1);
stack.push(right);
}
}
}
//计算基准值
public static int partition(int[] arr, int left, int right) {
if (arr.length == 0)
return 0;
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot)
right--;
arr[left] = arr[right];
while (left < right && arr[left] <= pivot)
left++;
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
//打印数组
public static void printArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
//打印二叉树
public static void printTree(List<Integer> queue) {
for (Integer val : queue) {
System.out.print(val + " ");
}
System.out.println();
}
// 非递归后序遍历
public static List<Integer> nonRecrutPostorderTraversal(Node root) {
LinkedList<Integer> queue = new LinkedList<>();
if (root == null)
return queue;
LinkedList<Node> stack = new LinkedList<>();
Node pre = null;
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
Node peekNode = stack.peek();
//根节点被访问的前提：无右子树或右子树已被访问过
if (peekNode.right != null && pre != peekNode.right) {
root = peekNode.right;
} else {
stack.poll();
queue.add(peekNode.val);
pre = peekNode;
}
}
}
return queue;
}
// 递归后序遍历
public static List<Integer> recrutPostorderTraversal(Node root) {
LinkedList<Integer> queue = new LinkedList<>();
if (root == null)
return queue;
recrutPostorderTraversal(root, queue);
return queue;
}
private static void recrutPostorderTraversal(Node root, LinkedList<Integer> queue) {
if (root == null)
return;
if (root.left != null)
recrutPostorderTraversal(root.left, queue);
if (root.right != null)
recrutPostorderTraversal(root.right, queue);
queue.add(root.val);
}
// 非递归中序遍历
public static List<Integer> nonRecrutInorderTraversal(Node root) {
LinkedList<Integer> queue = new LinkedList<>();
if (root == null)
return queue;
LinkedList<Node> stack = new LinkedList<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
queue.add(root.val);
root = root.right;
}
}
return queue;
}
// 递归中序遍历
public static List<Integer> recrutInorderTraversal(Node root) {
LinkedList<Integer> queue = new LinkedList<>();
if (root == null)
return queue;
recrutInorderTraversal(root, queue);
return queue;
}
private static void recrutInorderTraversal(Node root, LinkedList<Integer> queue) {
if (root == null)
return;
if (root.left != null)
recrutInorderTraversal(root.left, queue);
queue.add(root.val);
if (root.right != null)
recrutInorderTraversal(root.right, queue);
}
// 非递归前序遍历
public static List<Integer> nonRecrutPreorderTraversal(Node root) {
LinkedList<Integer> queue = new LinkedList<>();
if (root == null)
return queue;
LinkedList<Node> stack = new LinkedList<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
queue.add(root.val);
root = root.left;
} else {
root = stack.pop();
root = root.right;
}
}
return queue;
}
// 递归前序遍历
public static List<Integer> recrutPreorderTraversal(Node root) {
LinkedList<Integer> queue = new LinkedList<>();
if (root == null)
return queue;
recrutPreorderTraversal(root, queue);
return queue;
}
private static void recrutPreorderTraversal(Node root, LinkedList<Integer> queue) {
if (root == null)
return;
queue.add(root.val);
if (root.left != null)
recrutPreorderTraversal(root.left, queue);
if (root.right != null)
recrutPreorderTraversal(root.right, queue);
}
// 递归构建二叉查找树
public static Node retrutSortedArrayToBST(Node root, int[] nums, int start, int end) {
if (start > end) {
return null;
} else {
int mid = (start + end) / 2;
root = new Node(nums[mid]);
root.left = retrutSortedArrayToBST(root.left, nums, start, mid - 1);
root.right = retrutSortedArrayToBST(root.right, nums, mid + 1, end);
}
return root;
}
// 非递归构建二叉查找树
public static Node nonRetrutSortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0)
return null;
Stack<Integer> stack = new Stack<Integer>();
Stack<Node> tree = new Stack<Node>();
stack.add(nums.length - 1);
stack.add(0);
Node root = new Node(0);
tree.add(root);
while (!stack.isEmpty()) {
int left = stack.pop();
int right = stack.pop();
int mid = left + (right - left) / 2;
Node node = tree.pop();
node.val = nums[mid];
int r = mid - 1, l = left;
if (l <= r) {
node.left = new Node(0);
tree.add(node.left);
stack.push(r);
stack.push(l);
}
l = mid + 1;
r = right;
if (l <= r) {
node.right = new Node(0);
tree.add(node.right);
stack.push(r);
stack.push(l);
}
}
return root;
}
static class Node {
int val;
Node left;
Node right;
public Node(int val) {
this.val = val;
}
}
}
//--------------------运行结果-------------------------
快速排序
2 3 5 6 7 8 9 12 15
非递归构造二叉查找树
前序递归遍历
7 3 2 5 6 9 8 12 15
前序非递归遍历
7 3 2 5 6 9 8 12 15
中序递归遍历
2 3 5 6 7 8 9 12 15
中序非递归遍历
2 3 5 6 7 8 9 12 15
后序递归遍历
2 6 5 3 8 15 12 9 7
后序非递归遍历
2 6 5 3 8 15 12 9 7
生成的二叉树
二叉树.png
