正文之前
经过几天下午四点到现在的功夫，然后结合算法导论和自己的一些小尝试，总算把Java版本的二叉树给做的完美了~ emm 不信的话大家伙尽管测试。。。终于！！！树形结构！用Java实现出来确实很麻烦啊！因为是传递引用，所以要特别注意。。一不小心就出错了。。而且我经常犯一些傻逼错误！真的是想哭！！！！
正文
import java.util.Arrays;
import java.util.Random;
import java.util.LinkedList;
import java.util.Queue;
class node{
private int key;
node leftChild;
node rightChild;
node parent;
node(int x){
this.key=x;
}
node(){};
public int getKey(){
return this.key;
}
}
class Tree{
node head;
int size;
Tree(){this.size = 0;}
public node getHead(){
return this.head;
}
private void walk(Queue<String> queue,node par, int level){
String l = "";
for (int i =0;i<level;++i) l+=" ---->>>> ";
if (level == 1) queue.add(""+ par.getKey());
if(par.leftChild!=null){
queue.add(l+par.leftChild.getKey());
walk(queue,par.leftChild,level+1);
}
if (par.rightChild!=null){
queue.add(l+par.rightChild.getKey());
walk(queue,par.rightChild,level+1);
}
}
public String toString(){
System.out.println("输出树形: ");
Queue<String> queue = new LinkedList<>();
String out = "";
if (this.head!=null){
String one = "ok";
walk(queue,this.head,1);
int count = 0;
while(one!=null) {
one = queue.poll();
count++;
if(one!=null)
out += (count +" : "+ one+"\n");
}
}
return out;
}
}
public class TestTree{
private static node __findNode(node par,int z){
if (par==null || par.getKey() == z)
return par;
if (z<par.getKey()) return __findNode(par.leftChild,z);
else return __findNode(par.rightChild,z);
}
public static node findNode(Tree tree,int z){
node par = tree.getHead();
return __findNode(par,z);
}
public static void transplant(Tree tree, node u, node r){
if (u.parent == null) tree.head = r;
else if (u == u.parent.leftChild){
u.parent.leftChild = r;
}
else {
u.parent.rightChild = r;
}
if (r!=null)
u.parent = r.parent;
}
public static void nodeDelete(Tree tree, node z){
tree.size-=1;
if (z.leftChild==null)
transplant(tree,z,z.rightChild);
else if (z.rightChild==null)
transplant(tree,z,z.leftChild);
else {
node y = minNode(z.rightChild);
if (y.parent!=z){
transplant(tree,y,y.rightChild);
y.rightChild = z.rightChild;
y.rightChild.parent = y;
}
transplant(tree,z,y);
y.leftChild = z.leftChild;
y.leftChild.parent = y;
}
System.out.println("Deleted : "+ z.getKey()+"\n");
}
private static node minNode(node no){
node x = no;
while (x.leftChild!=null)
x=x.leftChild;
return x;
}
public static void insertSort(int []arr, int n){
for (int i = 1; i < n; ++i)
{
int e = arr[i];
int j=i;
for (; j > 0; --j)
{
if (e < arr[j-1])
arr[j] = arr[j-1];
else
break;
}
arr[j] = e;
}
}
public static void insertToTree(Tree tree,int x){
System.out.println("Insert into the Tree : "+x+"\n");
tree.size+=1;
node newnode = new node(x);
node tmp = tree.getHead();
if ( tmp==null)
tree.head = newnode;
while(tmp!=null) {
if (x < tmp.getKey()) {
if (tmp.leftChild==null || x > tmp.leftChild.getKey()) {
newnode.parent = tmp;
newnode.leftChild = tmp.leftChild;
tmp.leftChild = newnode;
return;
}
else
tmp = tmp.leftChild;
}
else {
if ( tmp.rightChild==null || x < tmp.rightChild.getKey()) {
newnode.parent = tmp;
newnode.rightChild = tmp.rightChild;
tmp.rightChild = newnode;
return;
}
else
tmp = tmp.rightChild;
}
}
}
public static Tree generateTree(int[] arr){
Tree tree = new Tree();
// insertSort(arr,arr.length);
insertToTree(tree,arr[arr.length/2]);
for (int i=0;i<arr.length;++i) {
if (i!=arr.length/2) {
tree.size+=1;
node newnode = new node(arr[i]);
node tmp = tree.getHead();
while(tmp!=null) {
if (arr[i] < tmp.getKey()) {
if (tmp.leftChild==null) {
newnode.parent = tmp;
newnode.leftChild = null;
tmp.leftChild = newnode;
break;
}
else
tmp = tmp.leftChild;
}
else {
if ( tmp.rightChild==null) {
newnode.parent = tmp;
newnode.rightChild =null;
tmp.rightChild = newnode;
break;
}
else
tmp = tmp.rightChild;
}
}
}
}
return tree;
}
public static void main(String[] args) {
double start = System.currentTimeMillis();
Random rdm = new Random(System.currentTimeMillis());
int [] randomArr = new int[20];
for(int i=0;i<20;i++)
randomArr[i] = Math.abs(rdm.nextInt())%500 +1;
Tree tree = generateTree(randomArr);
System.out.println(Arrays.toString(randomArr));
System.out.println(tree.toString());
nodeDelete(tree,findNode(tree,randomArr[Math.abs(rdm.nextInt())%tree.size+1]));
System.out.println(tree.toString());
insertToTree(tree,Math.abs(rdm.nextInt())%500 +1);
System.out.println(tree.toString());
double end = System.currentTimeMillis();
System.out.println("Usage of Time: "+(end-start));
}
}
注释什么的就不写了。都是很简单的部分，大概也就几个递归搞得我比较烦恼。。emm 然后就是删除我是直接借鉴了《算法导论》的伪代码实现的Java版本，真的厉害啊。。照着做就OK了。。。完全没想太多。。不过好歹还是吃透了。而且辅助函数都是自己写的好伐~
emm 下面看看使用过程的output：
Insert into the Tree : 241
[340, 286, 171, 462, 20, 262, 436, 184, 30, 50, 241, 373, 301, 461, 329, 120, 91, 375, 98, 105]
输出树形:
1 : 241
2 : ---->>>> 171
3 : ---->>>> ---->>>> 20
4 : ---->>>> ---->>>> ---->>>> 30
5 : ---->>>> ---->>>> ---->>>> ---->>>> 50
6 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 120
7 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 91
8 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 98
9 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 105
10 : ---->>>> ---->>>> 184
11 : ---->>>> 340
12 : ---->>>> ---->>>> 286
13 : ---->>>> ---->>>> ---->>>> 262
14 : ---->>>> ---->>>> ---->>>> 301
15 : ---->>>> ---->>>> ---->>>> ---->>>> 329
16 : ---->>>> ---->>>> 462
17 : ---->>>> ---->>>> ---->>>> 436
18 : ---->>>> ---->>>> ---->>>> ---->>>> 373
19 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 375
20 : ---->>>> ---->>>> ---->>>> ---->>>> 461
Deleted : 120
输出树形:
1 : 241
2 : ---->>>> 171
3 : ---->>>> ---->>>> 20
4 : ---->>>> ---->>>> ---->>>> 30
5 : ---->>>> ---->>>> ---->>>> ---->>>> 50
6 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 91
7 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 98
8 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 105
9 : ---->>>> ---->>>> 184
10 : ---->>>> 340
11 : ---->>>> ---->>>> 286
12 : ---->>>> ---->>>> ---->>>> 262
13 : ---->>>> ---->>>> ---->>>> 301
14 : ---->>>> ---->>>> ---->>>> ---->>>> 329
15 : ---->>>> ---->>>> 462
16 : ---->>>> ---->>>> ---->>>> 436
17 : ---->>>> ---->>>> ---->>>> ---->>>> 373
18 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 375
19 : ---->>>> ---->>>> ---->>>> ---->>>> 461
Insert into the Tree : 47
输出树形:
1 : 241
2 : ---->>>> 171
3 : ---->>>> ---->>>> 47
4 : ---->>>> ---->>>> ---->>>> 20
5 : ---->>>> ---->>>> ---->>>> ---->>>> 30
6 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 50
7 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 91
8 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 98
9 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 105
10 : ---->>>> ---->>>> 184
11 : ---->>>> 340
12 : ---->>>> ---->>>> 286
13 : ---->>>> ---->>>> ---->>>> 262
14 : ---->>>> ---->>>> ---->>>> 301
15 : ---->>>> ---->>>> ---->>>> ---->>>> 329
16 : ---->>>> ---->>>> 462
17 : ---->>>> ---->>>> ---->>>> 436
18 : ---->>>> ---->>>> ---->>>> ---->>>> 373
19 : ---->>>> ---->>>> ---->>>> ---->>>> ---->>>> 375
20 : ---->>>> ---->>>> ---->>>> ---->>>> 461
Usage of Time: 3.0
Process finished with exit code 0
正文之后
我是实在懒得去toString搞得尽善尽美了，现在这个样子大概也能看吧。。就一个先序遍历，，emm 爱看不看。。反正我是觉得基本没bug了。。。哈哈哈~
网友评论