Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite4be7de

Browse files
committed
Initial commit
0 parents  commite4be7de

File tree

52 files changed

+3225
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

52 files changed

+3225
-0
lines changed

‎.idea/.gitignore

Lines changed: 2 additions & 0 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

‎.idea/description.html

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

‎.idea/misc.xml

Lines changed: 12 additions & 0 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

‎.idea/modules.xml

Lines changed: 8 additions & 0 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

‎.idea/project-template.xml

Lines changed: 3 additions & 0 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

‎.idea/uiDesigner.xml

Lines changed: 124 additions & 0 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

‎.idea/vcs.xml

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.
362 KB
Binary file not shown.

‎DataStructure&Algorithm.iml

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

‎Dr. Sesh Venugopal's Web Page.pdf

177 KB
Binary file not shown.

‎src/GCD/GCDFinder.java

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
packageGCD;
2+
3+
publicclassGCDFinder {
4+
5+
/**
6+
* This method takes two positive integers and finds their gcd using
7+
* Euclid's algorithm
8+
* @param a
9+
* @param b
10+
* @return
11+
*/
12+
publicintgcd(inta,intb) {
13+
if (b ==0)returna;
14+
returngcd(b,a %b);
15+
}
16+
17+
publicstaticvoidmain(String[]args) {
18+
System.out.println(newGCDFinder().gcd(25,10));// should print 5
19+
}
20+
}

‎src/bst/BFS.java

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
packagebst;
2+
3+
importjava.util.LinkedList;
4+
importjava.util.Queue;
5+
importjava.util.SortedMap;
6+
7+
publicclassBFS {
8+
staticvoidbfsTraversal (TreeNodenode) {
9+
Queue<TreeNode>q =newLinkedList<TreeNode>();
10+
11+
q.offer(node);
12+
while (!q.isEmpty()) {
13+
node =q.poll();
14+
System.out.println(node.getData() +" ");
15+
if (node.getLeft() !=null)q.offer(node.getLeft());
16+
if (node.getRight() !=null)q.add(node.getRight());
17+
}
18+
}
19+
}

‎src/bst/BinarySearchTree.java

Lines changed: 172 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,172 @@
1+
packagebst;
2+
3+
publicclassBinarySearchTree {
4+
privateTreeNoderoot;
5+
6+
publicvoidinsert (Integerdata){
7+
if (root ==null)
8+
root =newTreeNode(data);
9+
else
10+
root.insert(data);
11+
}
12+
13+
publicIntegersmallest() {
14+
if (this.root !=null)
15+
returnthis.root.smallest();
16+
returnnull;
17+
}
18+
19+
publicIntegerlargest() {
20+
if (this.root !=null)
21+
returnthis.root.largest();
22+
returnnull;
23+
}
24+
publicintheight() {
25+
if (this.root ==null)return0;
26+
returnthis.root.height();
27+
}
28+
29+
publicTreeNodefind(Integerdata) {
30+
if (root !=null)
31+
returnroot.find(data);
32+
returnnull;
33+
}
34+
35+
// Soft delete
36+
publicvoidsoftDelete(Integerdata) {
37+
find(data).delete();
38+
}
39+
40+
// iterative implementaion
41+
publicvoiddelete(Integerdata) {
42+
TreeNodeparent =this.root;
43+
TreeNodecurrent =this.root;
44+
booleanisLeftChild =false;
45+
46+
if (current ==null)
47+
return;// tree is empty
48+
49+
while (current !=null &&current.getData() !=data) {
50+
parent =current;
51+
52+
if (data <current.getData()) {
53+
current =current.getLeft();
54+
isLeftChild =true;
55+
}else {
56+
current =current.getRight();
57+
isLeftChild =false;
58+
}
59+
}
60+
61+
if (current ==null)return;// node to be deleted not found
62+
63+
// case 1: leaf node
64+
if (current.getLeft() ==null &&current.getRight() ==null) {
65+
if (current ==root) {
66+
root =null;// no elements in tree now
67+
}else {
68+
if (isLeftChild)
69+
parent.setLeft(null);
70+
else
71+
parent.setRight(null);
72+
}
73+
74+
}
75+
// case 2: broken down further into 2 separate cases
76+
elseif (current.getRight() ==null) {// current has left child
77+
if (current ==root) {
78+
root =current.getLeft();
79+
}elseif (isLeftChild) {
80+
parent.setLeft(current.getLeft());
81+
}else {
82+
parent.setRight(current.getLeft());
83+
}
84+
}elseif (current.getLeft() ==null) {// current has right child
85+
if (current ==root) {
86+
root =current.getRight();
87+
}elseif (isLeftChild) {
88+
parent.setLeft(current.getRight());
89+
}else {
90+
parent.setRight(current.getRight());
91+
}
92+
}
93+
// case 3 - Most complicated (node to be deleted has 2 children)
94+
else {
95+
TreeNodesuccessor =getSuccessor(current);
96+
if (current ==root)
97+
root =successor;
98+
elseif (isLeftChild) {
99+
parent.setLeft(successor);
100+
}else {
101+
parent.setRight(successor);
102+
}
103+
successor.setLeft(current.getLeft());
104+
}
105+
}
106+
privateTreeNodegetSuccessor(TreeNodenode) {
107+
TreeNodeparentOfSuccessor =node;
108+
TreeNodesuccessor =node;
109+
TreeNodecurrent =node.getRight();
110+
while (current !=null) {
111+
parentOfSuccessor =successor;
112+
successor =current;
113+
current =current.getLeft();
114+
}
115+
if (successor !=node.getRight()) {
116+
parentOfSuccessor.setLeft(successor.getRight());
117+
successor.setRight(node.getRight());
118+
}
119+
returnsuccessor;
120+
}
121+
122+
publicvoidtraverseInOrder() {
123+
if (this.root !=null)
124+
this.root.traverseInOrder();
125+
System.out.println();
126+
}
127+
128+
publicintnumOfLeafNodes() {
129+
if (this.root ==null)return0;
130+
returnthis.root.numOfLeafNodes();
131+
}
132+
133+
publicstaticBinarySearchTreecreateFromSortedArray(int[]data) {
134+
BinarySearchTreebst =newBinarySearchTree();
135+
if (data !=null &&data.length >0) {
136+
bst.root =TreeNode.addSorted(data,0,data.length-1);
137+
}
138+
returnbst;
139+
}
140+
141+
// for test
142+
publicstaticvoidmain(String[]args) {
143+
// BinarySearchTree bt = createBinarySearchTree();
144+
145+
int[]sample = {212,580,6,7,28,84,112,434};
146+
BinarySearchTreebst =newBinarySearchTree();
147+
for (intx :sample) {
148+
bst.insert(x);
149+
}
150+
System.out.println(bst.find(65));
151+
System.out.println(bst.smallest());
152+
System.out.println(bst.largest());
153+
//bst.delete(84);
154+
System.out.println(bst.numOfLeafNodes());
155+
System.out.println(bst.height());
156+
bst.traverseInOrder();
157+
}
158+
159+
// private static BinarySearchTree createBinarySearchTree() {
160+
// BinarySearchTree bt = new BinarySearchTree();
161+
//
162+
// bt.insert(6);
163+
// bt.insert(4);
164+
// bt.insert(8);
165+
// bt.insert(3);
166+
// bt.insert(5);
167+
// bt.insert(7);
168+
// bt.insert(9);
169+
//
170+
// return bt;
171+
// }
172+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp