FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
algorithm_python/binary_tree2.py at master · mickelfeng/algorithm_python · GitHub
mickelfeng
algorithm_python
Repository navigation
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
algorithm_python
/
binary_tree2.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
125 lines (109 loc) · 3.5 KB
Breadcrumbs
algorithm_python
/
binary_tree2.py
Copy path
File metadata and controls
125 lines (109 loc) · 3.5 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#! /usr/bin/env python
#coding:utf-8
# The code is from:http://code.activestate.com/recipes/286239-binary-ordered-tree/
# A binary ordered tree example
class
CNode
:
left
,
right
,
data
=
None
,
None
,
0
def
__init__
(
self
,
data
):
# initializes the data members
self
.
left
=
None
self
.
right
=
None
self
.
data
=
data
class
CBOrdTree
:
def
__init__
(
self
):
# initializes the root member
self
.
root
=
None
def
addNode
(
self
,
data
):
# creates a new node and returns it
return
CNode
(
data
)
def
insert
(
self
,
root
,
data
):
# inserts a new data
if
root
==
None
:
# it there isn't any data
# adds it and returns
return
self
.
addNode
(
data
)
else
:
# enters into the tree
if
data
<=
root
.
data
:
# if the data is less than the stored one
# goes into the left-sub-tree
root
.
left
=
self
.
insert
(
root
.
left
,
data
)
else
:
# processes the right-sub-tree
root
.
right
=
self
.
insert
(
root
.
right
,
data
)
return
root
def
lookup
(
self
,
root
,
target
):
# looks for a value into the tree
if
root
==
None
:
return
0
else
:
# if it has found it...
if
target
==
root
.
data
:
return
1
else
:
if
target
<
root
.
data
:
# left side
return
self
.
lookup
(
root
.
left
,
target
)
else
:
# right side
return
self
.
lookup
(
root
.
right
,
target
)
def
minValue
(
self
,
root
):
# goes down into the left
# arm and returns the last value
while
(
root
.
left
!=
None
):
root
=
root
.
left
return
root
.
data
def
maxDepth
(
self
,
root
):
if
root
==
None
:
return
0
else
:
# computes the two depths
ldepth
=
self
.
maxDepth
(
root
.
left
)
rdepth
=
self
.
maxDepth
(
root
.
right
)
# returns the appropriate depth
return
max
(
ldepth
,
rdepth
)
+
1
def
size
(
self
,
root
):
if
root
==
None
:
return
0
else
:
return
self
.
size
(
root
.
left
)
+
1
+
self
.
size
(
root
.
right
)
def
printTree
(
self
,
root
):
# prints the tree path
if
root
==
None
:
pass
else
:
self
.
printTree
(
root
.
left
)
print
root
.
data
,
self
.
printTree
(
root
.
right
)
def
printRevTree
(
self
,
root
):
# prints the tree path in reverse
# order
if
root
==
None
:
pass
else
:
self
.
printRevTree
(
root
.
right
)
print
root
.
data
,
self
.
printRevTree
(
root
.
left
)
if
__name__
==
"__main__"
:
# create the binary tree
BTree
=
CBOrdTree
()
# add the root node
root
=
BTree
.
addNode
(
0
)
# ask the user to insert values
for
i
in
range
(
0
,
5
):
data
=
int
(
raw_input
(
"insert the node value nr %d: "
%
i
))
# insert values
BTree
.
insert
(
root
,
data
)
print
BTree
.
printTree
(
root
)
print
BTree
.
printRevTree
(
root
)
print
data
=
int
(
raw_input
(
"insert a value to find: "
))
if
BTree
.
lookup
(
root
,
data
):
print
"found"
else
:
print
"not found"
print
BTree
.
minValue
(
root
)
print
BTree
.
maxDepth
(
root
)
print
BTree
.
size
(
root
)
Back
|
FazBrowse Home
|
New Git URL