1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 |
# treenode.py: node of binary tree
class TreeNode(object):
def __init__(self, d):
self.data = d
self.left = None
self.right = None
# binarytree.py: simple binary search tree
import sys
import treenode
class BinaryTree(object):
def __init__(self):
self.root = None # hidden root node
def insert(self, d):
if self.root == None: # do empty tree first
self.root = treenode.TreeNode(d);
return
else:
loc = self.root # search down from root
while True:
if d < loc.data: # look left
if loc.left != None:
loc = loc.left
else:
loc.left =treenode.TreeNode(d)
return
elif d > loc.data: # look right
if loc.right != None:
loc = loc.right
else:
loc.right=treenode.TreeNode(d)
return
else: # found! Don't insert
return
# inorderTraversal: need because root hidden
def inorderTraversal(self):
self.inorderT(self.root)
# inorderT: recursive function that does the work
def inorderT(self, t):
if t != None:
self.inorderT(t.left)
sys.stdout.write(str(t.data)+' ')
self.inorderT(t.right)
# treetest.py
import sys
import binarytree
class TreeTest(object):
def __init__(self):
self.months = \
["Jan","Feb","Mar","Apr","May","Jun",
"Jul","Aug","Sep","Oct","Nov","Dec"]
def runTest(self):
tree = binarytree.BinaryTree()
for i in range(0,len(self.months)):
tree.insert(self.months[i])
tree.inorderTraversal();
sys.stdout.write('\n')
t = TreeTest()
t.runTest()
| // TreeNode: node in binary tree
public class TreeNode {
public String data; // data at each node
public TreeNode left, right;
public TreeNode(String d) { // construct leaf node
data = d;
left = right = null;
}
}
// Tree: simple binary search tree
public class Tree {
private TreeNode root; // hidden root node
// insert: if new entry, insert in tree
public void insert(String d) {
if (root == null) { // do empty tree first
root = new TreeNode(d);
return;
}
TreeNode loc = root; // search down from root
while (true) {
if (d.compareTo(loc.data) < 0) { // look left
if (loc.left != null) loc = loc.left;
else { loc.left = new TreeNode(d); break; }
}
else if (d.compareTo(loc.data) > 0) { // right
if (loc.right != null) loc = loc.right;
else { loc.right = new TreeNode(d); break;}
}
else break; // found! Don't insert
}
}
// inorderTraversal: need because root is hidden
public void inorderTraversal() {inorderT(root); }
// inorderT: recursive function that does the work
private void inorderT(TreeNode t) {
if (t != null) {
inorderT(t.left);
System.out.print(t.data + " ");
inorderT(t.right);
}
}
}
// TreeTest: test the Tree class, a binary search tree
public class TreeTest {
public static void main(String[] argv) {
String[] months =
{"Jan","Feb","Mar","Apr","May","Jun",
"Jul","Aug","Sep","Oct","Nov","Dec"};
Tree tree = new Tree();
for (int i = 0; i < months.length; i++)
tree.insert(months[i]);
tree.inorderTraversal();
System.out.println();
}
}
|
