Skip to content

Commit 450e6bb

Browse files
gotheregothere
committed
more sources
more source code
1 parent 07f0c67 commit 450e6bb

25 files changed

+1317
-1
lines changed

‎source_code/BinarySearchTree.java

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,123 @@
1+
/*
2+
* @Author: Beinan
3+
* @Date: 2015-01-08 20:52:49
4+
* @Last Modified by: Beinan
5+
* @Last Modified time: 2015-01-08 22:04:33
6+
*/
7+
8+
public class BinarySearchTree {
9+
TreeNode root = null;
10+
11+
class TreeNode{
12+
int value;
13+
int position;
14+
TreeNode left = null, right = null;
15+
TreeNode(int value, int position){
16+
this.value = value;
17+
this.position = position;
18+
}
19+
}
20+
21+
public void add(int value, int position){
22+
if(root == null){
23+
root = new TreeNode(value, position);
24+
} else {
25+
add(value, position, root);
26+
}
27+
}
28+
29+
private void add(int value, int position, TreeNode node){
30+
if(node == null)
31+
throw new RuntimeException("treenode cannot be null");
32+
if(node.value == value)
33+
return; //ignore the duplicated value
34+
if(value < node.value){
35+
if(node.left == null){
36+
node.left = new TreeNode(value, position);
37+
}else{
38+
add(value, position, node.left);
39+
}
40+
}else{
41+
if(node.right == null){
42+
node.right = new TreeNode(value, position);
43+
}else{
44+
add(value, position, node.right);
45+
}
46+
}
47+
}
48+
49+
public int search(int value){
50+
return search(value, root);
51+
}
52+
53+
private int search(int value, TreeNode node){
54+
if(node == null)
55+
return -1; //not found
56+
else if(value < node.value){
57+
System.out.println("Searching left");
58+
return search(value, node.left);
59+
}
60+
else if(value > node.value){
61+
System.out.println("Searching right");
62+
return search(value, node.right);
63+
}
64+
else
65+
return node.position;
66+
}
67+
68+
public void travel(){
69+
travel(root);
70+
}
71+
public void travel(TreeNode node){
72+
if(node == null)
73+
return;
74+
travel(node.left);
75+
System.out.println(" " + node.value);
76+
travel(node.right);
77+
}
78+
public int depth(){
79+
return depth(root);
80+
}
81+
82+
private int depth(TreeNode node){
83+
if(node == null)
84+
return 0;
85+
int leftDepth = depth(node.left);
86+
int rightDepth = depth(node.right);
87+
return Math.max(leftDepth, rightDepth) + 1;
88+
}
89+
public void levelOrder(){
90+
int depth = depth();
91+
for(int level = 0; level < depth; level ++){
92+
printLevel(root, level);
93+
System.out.println("\n-------------------");
94+
}
95+
}
96+
private void printLevel(TreeNode node, int level){
97+
if(node == null)
98+
return;
99+
if(level == 0){
100+
System.out.print(" " + node.value);
101+
}else{
102+
printLevel(node.left, level - 1);
103+
printLevel(node.right, level - 1);
104+
}
105+
}
106+
public static void main(String[] args) {
107+
BinarySearchTree bst = new BinarySearchTree();
108+
int a[] = { 3, 4, 2, 1, 7, 5, 8, 9, 0, 6};
109+
for(int i = 0; i < a.length; i++){
110+
bst.add(a[i], i);
111+
}
112+
113+
System.out.println("Tree Depth:" + bst.depth());
114+
bst.levelOrder();
115+
//bst.travel();
116+
//System.out.println(bst.search(8));
117+
//System.out.println(bst.search(3));
118+
//System.out.println(bst.search(6));
119+
//System.out.println(bst.search(30));
120+
121+
122+
}
123+
}

‎source_code/MergeKList.java

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
/*
2+
* Derived from http://www.programcreek.com/2013/02/leetcode-merge-k-sorted-lists-java/
3+
*
4+
* @Author: Beinan
5+
* @Date: 2015-01-18 22:07:49
6+
* @Last Modified by: Beinan
7+
* @Last Modified time: 2015-01-25 14:15:24
8+
*/
9+
import java.util.ArrayList;
10+
import java.util.Comparator;
11+
import java.util.PriorityQueue;
12+
13+
14+
public class MergeKList {
15+
16+
static class ListNode {
17+
int value;
18+
ListNode next;
19+
20+
ListNode(int value) {
21+
this.value = value;
22+
}
23+
}
24+
25+
public void mergeKLists(ArrayList<ListNode> lists) {
26+
//PriorityQueue is a sorted queue
27+
PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.size(),
28+
new Comparator<ListNode>() {
29+
public int compare(ListNode a, ListNode b) {
30+
return a.value - b.value;
31+
}
32+
});
33+
34+
for (ListNode list : lists) {
35+
q.add(list);
36+
}
37+
while (q.size() > 0) {
38+
ListNode temp = q.poll();
39+
System.out.println(temp.value);
40+
if (temp.next != null)
41+
q.add(temp.next);
42+
}
43+
}
44+
45+
public static void main(String[] args){
46+
ListNode h1 = new ListNode(3);
47+
h1.next = new ListNode(5);
48+
h1.next.next = new ListNode(8);
49+
ListNode h2 = new ListNode(2);
50+
h2.next = new ListNode(4);
51+
h2.next.next = new ListNode(9);
52+
ListNode h3 = new ListNode(4);
53+
h3.next = new ListNode(5);
54+
ListNode h4 = new ListNode(5);
55+
ArrayList<ListNode> lists = new ArrayList<ListNode>();
56+
lists.add(h1);
57+
lists.add(h2);
58+
lists.add(h3);
59+
lists.add(h4);
60+
61+
new MergeKList().mergeKLists(lists);
62+
}
63+
}

‎source_code/binary_exp_tree.cpp

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
/*
2+
* @Author: Beinan
3+
* @Date: 2015-01-17 23:03:29
4+
* @Last Modified by: Beinan
5+
* @Last Modified time: 2015-01-18 17:08:16
6+
*/
7+
8+
#include <iostream>
9+
#include <stack>
10+
#include <limits>
11+
using namespace std;
12+
13+
struct treenode{
14+
char payload;
15+
treenode* left;
16+
treenode* right;
17+
treenode(int value) : payload(value), left(nullptr), right(nullptr) {}
18+
};
19+
20+
21+
class BET{
22+
treenode *root;
23+
public:
24+
BET() : root(nullptr) {}
25+
void parse(const char exp[]) {
26+
const char* p = exp;
27+
stack<treenode*> s;
28+
while(*p != '\0'){
29+
if(*p >='0' && *p <='9'){
30+
s.push(new treenode(*p));
31+
}else{
32+
treenode* new_node = new treenode(*p);
33+
new_node->right = s.top();
34+
s.pop();
35+
new_node->left = s.top();
36+
s.pop();
37+
s.push(new_node);
38+
}
39+
p++;
40+
}
41+
if(s.size() != 1){
42+
cout << "Illegal Expression:";
43+
root = nullptr;
44+
}
45+
else
46+
root = s.top();
47+
}
48+
49+
int evaluate() {
50+
if(root == nullptr)
51+
return std::numeric_limits<int>::max();
52+
return evaluate(root);
53+
}
54+
private:
55+
int evaluate(treenode* node){
56+
switch(node->payload){
57+
case '-': return evaluate(node->left) - evaluate(node->right);
58+
case '+': return evaluate(node->left) + evaluate(node->right);
59+
case '*': return evaluate(node->left) * evaluate(node->right);
60+
default: return node->payload - '0';
61+
}
62+
}
63+
};
64+
int main(){
65+
BET bet;
66+
bet.parse("752+*");
67+
cout << bet.evaluate() << endl;
68+
bet.parse("753+*753+*+");
69+
cout << bet.evaluate() << endl;
70+
bet.parse("7");
71+
cout << bet.evaluate() << endl;
72+
bet.parse("77+88+");
73+
cout << bet.evaluate() << endl;
74+
75+
return 0;
76+
}

‎source_code/binary_heap.h

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
/*
2+
* @Author: Beinan
3+
* @Date: 2015-01-05 12:59:46
4+
* @Last Modified by: Beinan
5+
* @Last Modified time: 2015-01-17 18:00:41
6+
*/
7+
8+
#include <vector>
9+
#include <algorithm> //for swap
10+
#include <iostream>
11+
12+
template <typename T>
13+
class binary_heap{
14+
std::vector<T> data;
15+
protected:
16+
virtual bool compare(T a, T b) = 0;
17+
public:
18+
19+
void insert(T value){
20+
data.push_back(value);
21+
int pos = data.size() - 1;
22+
while(pos > 0){
23+
int parent = (pos - 1) / 2;
24+
if(parent < 0 || !compare(value, data[parent])){
25+
break; //less than parent,
26+
}
27+
std::swap(data[pos], data[parent]);
28+
pos = parent;
29+
}
30+
dump();
31+
}
32+
33+
T root(){
34+
return data[0];
35+
}
36+
37+
//delete the root of the heap
38+
void delete_root(){
39+
data[0] = data.back();
40+
data.pop_back();
41+
heapify(0);
42+
return;
43+
}
44+
45+
bool empty(){
46+
return data.empty();
47+
}
48+
49+
int size(){
50+
return data.size();
51+
}
52+
void dump(){
53+
for(int i = 0; i < data.size(); i++){
54+
std::cout << data[i] << " ";
55+
}
56+
std::cout << "\n";
57+
}
58+
private:
59+
void heapify(int pos){
60+
61+
dump();
62+
int left = 2 * pos + 1;
63+
int right = 2 * pos + 2;
64+
int largest_pos = pos;
65+
if(left < data.size() && compare(data[left], data[largest_pos]))
66+
largest_pos = left;
67+
if(right < data.size() && compare(data[right], data[largest_pos]))
68+
largest_pos = right;
69+
if(largest_pos != pos){
70+
std::swap(data[pos], data[largest_pos]);
71+
heapify(largest_pos);
72+
}
73+
74+
}
75+
};
76+
77+
template <typename T>
78+
class max_binary_heap : public binary_heap<T>{
79+
protected:
80+
virtual bool compare(T a, T b)
81+
{
82+
return a > b;
83+
}
84+
};
85+
86+
template <typename T>
87+
class min_binary_heap : public binary_heap<T>{
88+
protected:
89+
virtual bool compare(T a, T b)
90+
{
91+
return a < b;
92+
}
93+
};

0 commit comments

Comments
 (0)