# 树结构
from pythonds.basic.stack import Stack #pip install pythonds
from pythonds.trees.binaryTree import BinaryTree
from collections import defaultdict
import json#JSON-esque
def tree():
return defaultdict(tree)def dicts(t):
return {k: dicts(t[k]) for k in t}#迭代
def add(t, keys):
for key in keys: t = t[key]users = tree();
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux';print(json.dumps(users));taxonomy = tree();
taxonomy['Animalia']['Chordata']['Mammalia']['Carnivora']['Felidae']['Felis']['cat']
taxonomy['Animalia']['Chordata']['Mammalia']['Carnivora']['Felidae']['Panthera']['lion']
taxonomy['Animalia']['Chordata']['Mammalia']['Carnivora']['Canidae']['Canis']['dog']
taxonomy['Animalia']['Chordata']['Mammalia']['Carnivora']['Canidae']['Canis']['coyote']
taxonomy['Plantae']['Solanales']['Solanaceae']['Solanum']['tomato']
taxonomy['Plantae']['Solanales']['Solanaceae']['Solanum']['potato']
taxonomy['Plantae']['Solanales']['Convolvulaceae']['Ipomoea']['sweet potato']print(dicts(taxonomy));dtstr=add(taxonomy,'Animalia,Chordata,Mammalia,Cetacea,Balaenopteridae,Balaenoptera,blue whale'.split(','))def buildParseTree(fpexp):
fplist = fpexp.split()
pStack = Stack()
eTree = BinaryTree('')
pStack.push(eTree)
currentTree = eTree
for i in fplist:
if i == '(':
currentTree.insertLeft('')
pStack.push(currentTree)
currentTree = currentTree.getLeftChild()
elif i not in ['+', '-', '*', '/', ')']:
currentTree.setRootVal(int(i))
parent = pStack.pop()
currentTree = parent
elif i in ['+', '-', '*', '/']:
currentTree.setRootVal(i)
currentTree.insertRight('')
pStack.push(currentTree)
currentTree = currentTree.getRightChild()
elif i == ')':
currentTree = pStack.pop()
else:
raise ValueError
return eTreept = buildParseTree("( ( 10 + 5 ) * 3 )")
pp= pt.postorder() #defined and explained in the next section
输出结果：
{“harold”: {“username”: “hrldcpr”}, “handler”: {“username”: “matthandlersux”}}
{‘Animalia’: {‘Chordata’: {‘Mammalia’: {‘Carnivora’: {‘Felidae’: {‘Panthera’: {‘lion’: {}}, ‘Felis’: {‘cat’: {}}}, ‘Canidae’: {‘Canis’: {‘dog’: {}, ‘coyote’: {}}}}}}}, ‘Plantae’: {‘Solanales’: {‘Convolvulaceae’: {‘Ipomoea’: {‘sweet potato’: {}}}, ‘Solanaceae’: {‘Solanum’: {‘tomato’: {}, ‘potato’: {}}}}}}
10
5
+
3
*
(‘In’, ‘the’)
(‘the’, ‘beginning’)
(‘beginning’, ‘god’)
(‘god’, ‘created’)
(‘created’, ‘the’)
(‘the’, ‘heaven’)
(‘heaven’, ‘and’)
(‘and’, ‘the’)
(‘the’, ‘earth’)
(‘earth’, ‘.’)
涂聚文，geovindu
geovindu-PC
192.168.20.210
hello word 你好，世界
win32
1267650600228229401496703205376
输入的内容:
2.
import uuid;#Python3.5class TreeNode(object):
def __init__(self, data = -1, lchild = None, rchild = None):
self.data = data
self.lchild = lchild
self.rchild = rchildclass BinaryTree(object):
def __init__(self):
self.root = TreeNode() def add(self, data):
node = TreeNode(data)
if self.isEmpty():
self.root = node
else:
tree_node = self.root
queue = []
queue.append(self.root) while queue:
tree_node = queue.pop(0)
if tree_node.lchild == None:
tree_node.lchild = node
return
elif tree_node.rchild == None:
tree_node.rchild = node
return
else:
queue.append(tree_node.lchild)
queue.append(tree_node.rchild) def pre_order(self, start):
node = start
if node == None:
return print(node.data),
if node.lchild == None and node.rchild == None:
return
self.pre_order(node.lchild)
self.pre_order(node.rchild) def pre_order_loop(self):
if self.isEmpty():
return stack = []
node = self.root
while node or stack:
while node:
print(node.data),
stack.append(node)
node = node.lchild
if stack:
node = stack.pop()
node = node.rchild def in_order(self, start):
node = start
if node == None:
return
self.in_order(node.lchild)
print(node.data),
self.in_order(node.rchild) def in_order_loop(self):
if self.isEmpty():
return stack = []
node = self.root
while node or stack:
while node:
stack.append(node)
node = node.lchild if stack:
node = stack.pop()
print(node.data),
node = node.rchild def post_order(self, start):
node = start
if node == None:
return
self.post_order(node.lchild)
self.post_order(node.rchild)
print(node.data), def post_order_loop(self):
if self.isEmpty():
return node = self.root
stack = []
queue = []
queue.append(node)
while queue:
node = queue.pop()
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
stack.append(node)
while stack:
print(stack.pop().data), #if lchild and rchild are None or lchild and rchild are printed, print the parent node node and pop out of the stack
#else lchild and rchild push into the stack
def post_order_loop1(self):
if self.isEmpty():
return stack = []
top = -1
node = self.root
stack.append(node)
#we need to recognize the last printed node
top += 1
pre = None
while stack:
node = stack[-1]
if node.lchild is None and node.rchild is None:
print(node.data),
pre = node
top -= 1
elif not pre and (node.lchild == pre or node.rchild == pre):
print(node.data),
pre = node
top -= 1
else:
if node.rchild:
if top < len(stack)-1:
stack[top] = node.rchild
else:
stack.append(node.rchild)
if node.lchild:
if top < len(stack)-1:
stack[top] = node.lchild
else:
stack.append(node.lchild) def level_order(self):
node = self.root
if node == None:
return queue = []
queue.append(node) while queue:
node = queue.pop(0)
print(node.data),
if node.rchild:
queue.append(node.rchild)
if node.lchild:
queue.append(node.lchild)
print def isEmpty(self):
return True if self.root.data == -1 else Falseclass NodeTu:
def __init__(self, value, next=None):
self.value = value;
self.next = next;class NodeDu:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
测试：
import nltk;
import pandas;
import matplotlib;
import math;
import os;
import unittest;
#from nltk.parse.featurechart import trees
import NodeDu;
import copy;
import NodeTu;
import TreeNode;
from nltk.tree import ParentedTree;#Python 3.5#from platform import node#1. tree data structure
arr = []
for i in range(10):
arr.append(i)
print(arr);tree =TreeNode.BinaryTree();
for i in arr:
tree.add(i)
print('level_order:');
tree.level_order();
print('pre order:');
tree.pre_order(tree.root)
print('\npre order loop:');
tree.pre_order_loop()
print('\nin_order:');
tree.in_order(tree.root)
print('\nin_order loop:');
tree.in_order_loop()
print('\npost_order:');
tree.post_order(tree.root)
print('\npost_order_loop:');
tree.post_order_loop()
print('\npost_order_loop1:');
tree.post_order_loop1()a11=NodeTu.NodeTu(6);
a12=NodeTu.NodeTu(5);
a13=NodeTu.NodeTu(4);
a14=NodeTu.NodeTu(3);
a15=NodeTu.NodeTu(2);a12=a11.next;
a13=a14.next;
a14=a15.next;a16=a11.next;print(a15.value);
print(a11.value);a1 = NodeDu.NodeDu(6);
b1 = NodeDu.NodeDu(5);
b2 = NodeDu.NodeDu(2);
c1 = NodeDu.NodeDu(4);
c2 = NodeDu.NodeDu(1);
c3 = NodeDu.NodeDu(1);
d1 = NodeDu.NodeDu(3);
d2 = NodeDu.NodeDu(0); a1.left = b1;
a1.right = b2;
b1.left = c1;
b1.right = c2;
b2.left = c3;
c1.left = d1;
c1.right = d2;s = [];def gos(node, path=[]):
if node:
path.append(node.value)
if node.left:
path1 = copy.copy(path)
gos(node.left, path1)
if node.right:
path2 = copy.copy(path)
gos(node.right, path2)
else:
s.append(copy.copy(path))gos(a1);
print(s); #
ptree = ParentedTree.fromstring('(ROOT (S (NP (JJ Congressional) \
(NNS representatives)) (VP (VBP are) (VP (VBN motivated) \
(PP (IN by) (NP (NP (ADJ shiny) (NNS money))))))) (. .))')def traverse(t):
try:
t.label()
except AttributeError:
return
else:
if t.height() == 2: #child nodes
print(t.parent());
return for child in t:
traverse(child)tra=traverse(ptree);
print(tra);ptree = ParentedTree.fromstring('(ROOT (S (NP (PRP It)) \
(VP (VBZ is) (ADJP (RB so) (JJ nice))) (. .)))')leaf_values = ptree.leaves();if 'nice' in leaf_values:
leaf_index = leaf_values.index('nice')
tree_location = ptree.leaf_treeposition(leaf_index)
print(tree_location);
print(ptree[tree_location]);
输出：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
level_order:
0
2
1
6
5
4
3
9
8
7
pre order:
0
1
3
7
8
4
9
2
5
6
pre order loop:
0
1
3
7
8
4
9
2
5
6
in_order:
7
3
8
1
9
4
0
5
2
6
in_order loop:
7
3
8
1
9
4
0
5
2
6
post_order:
7
8
3
9
4
1
5
6
2
0
post_order_loop:
7
8
3
9
4
1
5
6
2
0
post_order_loop1:
https://repo.continuum.io/archive/.winzip/
https://github.com/Rochester-NRT/RocAlphaGo
https://github.com/wrongu/
https://github.com/hiropppe/
https://gitter.im/Rochester-NRT/RocAlphaGo
http://www.nltk.org/nltk_data/
