Basic code about tree and sort

package com.solution.test;

/*
Enter your code here. Read input from STDIN. Print output to STDOUT
Your class should be named Solution
*/

import java.util.*;

public class Solution {
static LinkedList stack = new LinkedList();

static TreeNode BuildTree(int low, int high, int[] array) {
if (low > high)
return null;
int mid = 0;
TreeNode node = new TreeNode();
node.left = node.right = null;
mid = (low + high) / 2;
node.value = array[mid];
node.left = BuildTree(low, mid – 1, array);
node.right = BuildTree(mid + 1, high, array);
return node;
}

static void Inorder(TreeNode T) {
TreeNode p = T;
stack.addLast(p);
while (!stack.isEmpty()) {
TreeNode t = stack.getLast();
while (t != null) {
t = t.left;
stack.addLast(t);
}
stack.removeLast();
if (!stack.isEmpty()) {
t = stack.removeLast();
System.out.print(t.value + “,”);
stack.addLast(t.right);
}
}
}

static void Preorder(TreeNode T) {
TreeNode p = T;
stack.addLast(p);
while (!stack.isEmpty()) {
TreeNode t = stack.removeLast();
System.out.print(t.value + “,”);
if (t.right != null)
stack.addLast(t.right);
if (t.left != null)
stack.addLast(t.left);
}
}

static void Postorder(TreeNode T) {
TreeNode p = T, pre = null;
while (p != null || !stack.isEmpty()) {
while (p != null) {
stack.addLast(p);
p = p.left;
}
p = stack.getLast();
if (p.right == null || p.right == pre) {
System.out.print(p.value + “,”);
stack.removeLast();
pre = p;
p = null;
} else {
p = p.right;
}
}
}

static int TreeLevel(TreeNode T) {
if (T == null)
return 0;
TreeNode queue[] = new TreeNode[6];
int front = -1, rear = -1, last = -1, level = 0;
queue[++rear] = T;
TreeNode p = null;
last = rear;
while (front != rear) {
p = queue[(++front) % 6];
System.out.print(p.value + “,”);
if (p.left != null)
queue[(++rear) % 6] = p.left;
if (p.right != null)
queue[(++rear) % 6] = p.right;
if (front == last) {
level++;
last = rear;
}
}
return level;
}

static TreeNode CommonNode(TreeNode T, TreeNode left, TreeNode right) {
if (T == null || left == null || right == null) {
return null;
} else if (T.value < left.value && T.value left.value && T.value > right.value)
return CommonNode(T.left, left, right);
else
return T;
}

static TreeNode LCA(TreeNode T, TreeNode left, TreeNode right) {
if (T == null)
return null;
if (T == left || T == right)
return T;
TreeNode L = LCA(T.left, left, right);
TreeNode R = LCA(T.right, left, right);
if (L != null && R != null)
return T;
return L != null ? L : R;
}

static TreeNode SearchBST(TreeNode T, int key, TreeNode f) {
if (T == null)
return f;
if (T.value == key)
return T;
else if (T.value > key)
return SearchBST(T.left, key, T);
else
return SearchBST(T.right, key, T);
}

static boolean InsertBST(TreeNode T, int value) {
TreeNode p = SearchBST(T, value, null);
if (p != null) {
TreeNode s = new TreeNode();
s.value = value;
s.left = s.right = null;
if (p.value value) {
p.left = s;
return true;
}
return false;
}
return false;
}

static void InsertSort(int[] n) {
int tag = 0;
if (n == null || n.length <= 1)
return;
for (int i = 1; i n[i]) {
tag = n[i];
n[i] = n[i – 1];

int j = i – 2;
for (; j >= 0 && n[j ] > tag; j–) {
n[j + 1] = n[j];
}
n[j + 1] = tag;
}
}
}

static void QuickSort(int[] n, int low, int high){
if(n==null)
return;
if(low<high){
int mid = PartitionSort(n, low, high);
QuickSort(n, low, mid-1);
QuickSort(n, mid+1, high);
}
}

static int PartitionSort(int[] n, int low, int high) {
int key = n[low];
while(low<high){
while(low=key)
high–;
n[low] = n[high];
while(low<high&&n[low]<=key)
low++;
n[high] = n[low];
}
n[low] = key;
return low;
}

static void HeapAdjust(int[] n, int s, int m){
int rc = n[s];
for(int j=2*s; j<m; j*=2){
if(n[j]<n[j+1]) j++;
if(n[j]=0; i–)
HeapAdjust(n, i, n.length-1); //build the heap
for(int i : n){
System.out.print(i);
}
System.out.println();
for(int i=n.length-1; i>=1; i–){
int temp = n[0];
n[0] = n[i];
n[i] = temp;
HeapAdjust(n, 0, i-1) //exchange the max to the last
}
}

public static void main(String args[]) {
int array[] = {
3,4,9,1,7,2,5,6,8,0
};
InsertSort(array);
QuickSort(array, 0, array.length-1);
HeapSort(array);
for(int i : array){
System.out.print(i);
}
TreeNode T = BuildTree(0, array.length – 1, array);
System.out.print(CommonNode(T, T.right.left.right,
T.right.right.right).value);
System.out.print(LCA(T, T.right.left.right,
T.right.right.right).value);
InsertBST(T, 6);
Inorder(T);
System.out.println();
Preorder(T);
System.out.println();
Postorder(T);
System.out.println();
System.out.print(TreeLevel(T));
}
}

class TreeNode {
TreeNode left;
TreeNode right;
int value;
}

Advertisements

5 thoughts on “Basic code about tree and sort

  1. Merge Sort
    static void MergeSort(int[] array, int[] num, int low, int high){
    if(low==high)
    array[low] = num[low];
    else{
    int[] temp = new int[num.length];
    int mid = (low+high)/2;
    MergeSort(temp, num, low, mid);
    MergeSort(temp, num, mid+1, high);
    Merge(array, temp, low, mid, high);
    }
    }

    static void Merge(int[] array, int[] num, int low, int mid, int high){
    System.out.println(low+”:”+mid+”:”+high);
    int i=low, j=mid+1, k=low;
    for(; i<=mid&&j<=high; k++){
    if(num[i]<num[j])
    array[k] = num[i++];
    else
    array[k] = num[j++];
    }
    while(i<=mid)
    array[k++] = num[i++];
    while(j<=high)
    array[k++] = num[j++];
    }

  2. static void PrintTree(TreeNode T){
    if(T==null){
    System.out.print(“#”+”,”);
    return;
    }
    System.out.print(T.value+”,”);
    PrintTree(T.left);
    PrintTree(T.right);
    }

    static int count = -1;

    static TreeNode ReadTree(char[] num) {
    count++;
    TreeNode T= new TreeNode();
    if (count >= num.length)
    return null;
    else{
    if (num[count] != ‘#’) {
    T.value = num[count]-‘0’;
    T.left = ReadTree(num);
    T.right = ReadTree(num);
    }else{
    T = null;
    }
    }
    return T;
    }

  3. static int pre[] = {10,8,9,12,11,13};
    static int in[] = {8,9,10,11,12,13};
    static int post[] = {9,8,11,13,12,10};

    static TreeNode PreMidTree(int i, int j, int len){
    if(len<=0)
    return null;
    TreeNode T = new TreeNode();
    T.value = pre[i];
    int m = PositionInorder(pre[i]);
    T.left = PreMidTree(i+1, j, m-j);
    T.right = PreMidTree(i+(m-j)+1, m+1, len-(m-j)-1);
    return T;
    }

    private static int PositionInorder(int i) {
    // TODO Auto-generated method stub
    for(int s=0; s<in.length; s++){
    if(in[s] == i)
    return s;
    }
    return -1;
    }

    static TreeNode PostMidTree(int i, int j, int len){
    if(len<=0)
    return null;
    TreeNode T = new TreeNode();
    T.value = post[i];
    int m = PositionInorder(post[i]);
    T.right = PostMidTree(i-1, m+1, len-(m-j)-1);
    T.left = PostMidTree(i-(len-(m-j)-1)-1, j, m-j);
    return T;
    }

  4. static void HeapAdjust(int[] n, int s, int m) {
    int rc = n[s];
    for (int j = 2 * s; j < m; j *= 2) {
    if (n[j] n[j])
    break;
    n[s] = n[j];
    s = j;
    }
    n[s] = rc;
    }

    static void HeapSort(int[] n) {
    for (int i = n.length / 2; i >= 0; i–)
    HeapAdjust(n, i, n.length – 1); // build the heap
    for (int i = n.length – 1; i >= 1; i–) {
    int temp = n[0];
    n[0] = n[i];
    n[i] = temp;
    HeapAdjust(n, 0, i – 1); // exchange the max to the last
    }
    }

  5. static void HeapAdjust(int[] n, int s, int m){
    int rc = n[s];
    for(int j=2*s; j<=m; j*=2){
    if(j<m&&n[j]n[j])
    break;
    n[s] = n[j];
    s = j;
    }
    n[s] = rc;
    }

    static void heapSort(int[] n) {
    for (int i = n.length/2; i >=1; i–) {
    HeapAdjust(n, i, n.length-1); //build the heap
    }
    for(int i=0; i 1; i–) {
    int temp = n[1];
    n[1] = n[i];
    n[i] = temp;//exchange the max to the last
    HeapAdjust(n, 1, i-1);
    }
    }
    注意从j=2×s中必须要求s从1开始。不能为0!!!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s