Skip to content

Commit 19d2644

Browse files
githublmkgithublmk
authored
Merge pull request #2 from githublmk/githublmk-patch-shujujiegou
数据结构
2 parents b9df490 + 8245120 commit 19d2644

File tree

14 files changed

+785
-0
lines changed

14 files changed

+785
-0
lines changed

‎shujujiegou/Tree.iml

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<module type="JAVA_MODULE" version="4">
3+
<component name="NewModuleRootManager" inherit-compiler-output="true">
4+
<exclude-output />
5+
<content url="file://$MODULE_DIR$">
6+
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
7+
</content>
8+
<orderEntry type="inheritedJdk" />
9+
<orderEntry type="sourceFolder" forTests="false" />
10+
</component>
11+
</module>

‎shujujiegou/src/com/lmk/arraybinarytree/ArrayBinaryTree.java

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package com.lmk.arraybinarytree;
2+
3+
public class ArrayBinaryTree {
4+
private int[] root;
5+
6+
public ArrayBinaryTree() {
7+
}
8+
9+
public ArrayBinaryTree(int[] root) {
10+
this.root = root;
11+
}
12+
13+
public int[] getRoot() {
14+
return root;
15+
}
16+
17+
public void setRoot(int[] root) {
18+
this.root = root;
19+
}
20+
21+
public void before(){
22+
before(0);
23+
}
24+
25+
/**
26+
* 先序遍历
27+
* @param index
28+
*/
29+
public void before(int index) {
30+
if(index>this.root.length-1){
31+
return;
32+
}
33+
System.out.println(this.root[index]);
34+
35+
if(2*index+1 <this.root.length){
36+
before(2*index +1);
37+
}
38+
if(2*index +2<this.root.length){
39+
before(2*index +2);
40+
}
41+
}
42+
43+
public void middle(){
44+
middle(0);
45+
}
46+
/**
47+
* 中序遍历
48+
* @param index
49+
*/
50+
public void middle(int index){
51+
if(index>this.root.length-1){
52+
return;
53+
}
54+
if(2*index +1<this.root.length){
55+
middle(2*index+1);
56+
}
57+
System.out.println(this.root[index]);
58+
if(2*index +2<this.root.length){
59+
middle(2*index+2);
60+
}
61+
}
62+
63+
public void after(){
64+
after(0);
65+
}
66+
/**
67+
* 后序遍历
68+
* @param index
69+
*/
70+
public void after(int index){
71+
if(index>this.root.length-1){
72+
return;
73+
}
74+
if(2*index+1<this.root.length){
75+
after(2*index+1);
76+
}
77+
if(2*index+2<this.root.length){
78+
after(2*index+2);
79+
}
80+
System.out.println(this.root[index]);
81+
}
82+
}

‎shujujiegou/src/com/lmk/arraybinarytree/TestArrayBinaryTree.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package com.lmk.arraybinarytree;
2+
3+
public class TestArrayBinaryTree {
4+
5+
/**
6+
* 顺序存储二叉树
7+
* 左子子节点 2n +1
8+
* 右子节点 2n +2
9+
* 父节点 （n-1）/2
10+
* 1
11+
* 2 3
12+
* 4 5 6 7
13+
* @param args
14+
*/
15+
16+
public static void main(String[] args) {
17+
ArrayBinaryTree tree =new ArrayBinaryTree();
18+
int[] array =new int[]{1,2,3,4,5,6,7};
19+
tree.setRoot(array);
20+
System.out.println("------先序--------");
21+
tree.before();
22+
System.out.println("------中序-------");
23+
tree.middle();
24+
System.out.println("-------后序--------");
25+
tree.after();
26+
}
27+
}

‎shujujiegou/src/com/lmk/binarytree/BinaryTree.java

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package com.lmk.binarytree;
2+
3+
public class BinaryTree {
4+
5+
private TreeNode root;
6+
7+
public BinaryTree(){}
8+
9+
public BinaryTree(TreeNode root){
10+
this.root = root;
11+
}
12+
13+
public TreeNode getRoot() {
14+
return root;
15+
}
16+
17+
public void setRoot(TreeNode root) {
18+
this.root = root;
19+
}
20+
21+
//先序查找
22+
public TreeNode beforeSearch(int value){
23+
if(this.root ==null){
24+
return null;
25+
}else{
26+
return this.root.beforeSearch(value);
27+
}
28+
}
29+
/**
30+
* 中序查找
31+
*/
32+
public TreeNode middleSearch(int value){
33+
if(this.root==null){
34+
return null;
35+
}else{
36+
return this.root.middleSearch(value);
37+
}
38+
39+
}
40+
41+
public TreeNode afterSearch(int value){
42+
if(this.root == null){
43+
return null;
44+
}else {
45+
return this.root.afterSearch(value);
46+
}
47+
48+
}
49+
50+
/**
51+
* 删除值为i的节点
52+
* @param i
53+
*/
54+
public void delete(int i) {
55+
/*
56+
判断根节点的值是否等于i，等于i根节点置空
57+
*/
58+
if(root !=null&&root.getValue() ==i){
59+
root =null;
60+
}else{
61+
root.delete(i);
62+
}
63+
64+
65+
}
66+
67+
public void middle() {
68+
69+
if(root==null){
70+
return;
71+
}
72+
root.middle();
73+
74+
}
75+
}

‎shujujiegou/src/com/lmk/binarytree/TestBinaryTree.java

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package com.lmk.binarytree;
2+
3+
public class TestBinaryTree {
4+
5+
/**
6+
*
7+
* @param args
8+
* 1
9+
* 2 3
10+
* 4 5 6 7
11+
*/
12+
public static void main(String[] args) {
13+
14+
15+
16+
TreeNode root =new TreeNode(1);
17+
BinaryTree tree =new BinaryTree(root);
18+
19+
TreeNode left1 = new TreeNode(2);
20+
root.setLeftNode(left1);
21+
22+
TreeNode right1 = new TreeNode(3);
23+
root.setRightNode(right1);
24+
25+
TreeNode left21 = new TreeNode(4);
26+
left1.setLeftNode(left21);
27+
28+
TreeNode right21 = new TreeNode(5);
29+
left1.setRightNode(right21);
30+
31+
TreeNode left22 = new TreeNode(6);
32+
right1.setLeftNode(left22);
33+
34+
TreeNode right22 =new TreeNode(7);
35+
right1.setRightNode(right22);
36+
System.out.println("------------删除节点-------------");
37+
tree.delete(1);
38+
tree.middle();
39+
40+
System.out.println("------先序--------");
41+
TreeNode beforeResult = tree.beforeSearch(6);
42+
if(beforeResult !=null){
43+
System.out.println(beforeResult.getValue());
44+
}
45+
System.out.println(beforeResult);
46+
System.out.println(left22==beforeResult);
47+
System.out.println("-----中序--------");
48+
TreeNode restltMiddle = tree.middleSearch(4);
49+
System.out.println(restltMiddle!=null?restltMiddle.getValue()+"|"+restltMiddle:restltMiddle);
50+
System.out.println(left21==restltMiddle);
51+
52+
System.out.println("----后序---------");
53+
TreeNode resultAfter = tree.afterSearch(6);
54+
System.out.println(resultAfter!=null?resultAfter.getValue()+"|"+resultAfter:resultAfter);
55+
System.out.println(left22==resultAfter);
56+
}
57+
58+
}

‎shujujiegou/src/com/lmk/binarytree/TreeNode.java

Lines changed: 138 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,138 @@
1+
package com.lmk.binarytree;
2+
3+
public class TreeNode {
4+
5+
private int value;
6+
7+
private TreeNode leftNode;
8+
9+
private TreeNode rightNode;
10+
11+
public TreeNode(){
12+
13+
}
14+
15+
public TreeNode(int value) {
16+
this.value = value;
17+
}
18+
19+
public int getValue() {
20+
return value;
21+
}
22+
23+
public void setValue(int value) {
24+
this.value = value;
25+
}
26+
27+
public TreeNode getLeftNode() {
28+
return leftNode;
29+
}
30+
31+
public void setLeftNode(TreeNode leftNode) {
32+
this.leftNode = leftNode;
33+
}
34+
35+
public TreeNode getRightNode() {
36+
return rightNode;
37+
}
38+
39+
public void setRightNode(TreeNode rightNode) {
40+
this.rightNode = rightNode;
41+
}
42+
43+
public TreeNode beforeSearch(int value) {
44+
if(this.value == value){
45+
return this;
46+
}
47+
if(this.leftNode !=null){
48+
TreeNode temp = leftNode.beforeSearch(value);
49+
if(temp!=null){
50+
return temp;
51+
}
52+
53+
}
54+
if(this.rightNode !=null) {
55+
TreeNode temp =rightNode.beforeSearch(value);
56+
if(temp !=null){
57+
return temp;
58+
}
59+
60+
}
61+
return null;
62+
}
63+
64+
public TreeNode middleSearch(int value) {
65+
66+
if(leftNode !=null){
67+
TreeNode temp = leftNode.middleSearch(value);
68+
if(temp !=null){
69+
return temp;
70+
}
71+
}
72+
if(this.value == value ){
73+
return this;
74+
}
75+
if(rightNode !=null){
76+
TreeNode temp = rightNode.middleSearch(value);
77+
if(temp !=null){
78+
return temp;
79+
}
80+
}
81+
return null;
82+
}
83+
84+
/**
85+
* 后序查找
86+
* @param value
87+
* @return
88+
*/
89+
public TreeNode afterSearch(int value) {
90+
TreeNode temp =null;
91+
if(this.leftNode !=null){
92+
temp =leftNode.afterSearch(value);
93+
if(temp !=null){
94+
return temp;
95+
}
96+
}
97+
98+
if(this.rightNode !=null){
99+
temp = rightNode.afterSearch(value);
100+
if(temp !=null){
101+
return temp;
102+
}
103+
}
104+
if(this.value == value){
105+
return this;
106+
}
107+
return temp;
108+
}
109+
110+
public void delete(int i) {
111+
112+
113+
if(leftNode!=null&&leftNode.getValue()==i){
114+
leftNode =null;
115+
}
116+
if(rightNode!=null&&rightNode.getValue()==i){
117+
rightNode=null;
118+
}
119+
if(leftNode!=null){
120+
leftNode.delete(i);
121+
}
122+
if(rightNode !=null){
123+
rightNode.delete(i);
124+
}
125+
}
126+
127+
public void middle() {
128+
129+
System.out.println(this.value);
130+
131+
if(this.leftNode!=null){
132+
leftNode.middle();
133+
}
134+
if(this.rightNode!=null){
135+
rightNode.middle();
136+
}
137+
}
138+
}

0 commit comments

Comments
 (0)