tree 树
名词解释
node 节点
树的基本组成部分。节点内可以存储重要的信息。
edge 边
边是树的另一种基本结构。边将两个节点连接在一起，表示两个节点间存在某种关系。树中的每个节点（除了根节点）都有且只有一条输入边。但可以有无数条输出边。
root 根节点
在树中，根节点有且只有一个。并且根节点没有输入边。
path 路径
路径由有顺序的节点序列表示。这些序列间由边连接起来。
children 子节点
输入边来自同一个节点的节点的集合。那同一个节点是这些子节点的父节点。
parent 父节点
对于由一个节点A的输出边连接的所有节点B的集合, 节点A是任何一个B的父节点。
sibling 兄弟
具有同一个父节点的子节点之间叫兄弟。
subtree 子树
一个父节点以及其所有子代的节点和边的集合。
leaf node 叶节点
没有子节点的节点。
level 层
对于节点n来说，n的层为从根节点到节点n的路径上边的个数。
height 高
从根节点到任何子节点的最大层数。
tree 树
#### Definition One
Definition One: A tree consists of a set of nodes and a set of edges that connect pairs of nodes. A tree has the following properties:
One node of the tree is designated as the root node.
Every node
A unique path traverses from the root to each node.
If each node in the tree has a maximum of two children, we say that the tree is a binary tree.
#### Definition Two (recursive definition of a tree)
Definition Two: A tree is either empty or consists of a root and zero or more subtrees, each of which is also a tree. The root of each subtree is connected to the root of the parent tree by an edge.
节点与引用 nodes and references
class BinaryTree(object):
def __init__(self, rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
def insertLeft(self, newNode):
if self.leftChild is None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode) # once there is existing a left child, put the left
# child down a level
t.leftChild = self.leftChild
self.leftChild = t
def insertRight(self, newNode):
if self.rightChild is None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode) # same like the insert left method
t.rightChild = self.rightChild
self.rightChild = t
def getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild
def setRootVal(self, obj):
self.key = obj
def getRootVal(self):
return self.key
r = BinaryTree('a')
print(r.getRootVal())
print(r.getLeftChild())
r.insertLeft('b')
print(r.getLeftChild())
print(r.getLeftChild().getRootVal())
r.insertRight('c')
print(r.getRightChild())
print(r.getRightChild().getRootVal())
r.getRightChild().setRootVal('hello')
print(r.getRightChild().getRootVal())
a
None
<__main__.BinaryTree object at 0x0000000003FADD68>
b
<__main__.BinaryTree object at 0x0000000003FADC50>
c
hello
def buildTree():
root = BinaryTree('a')
root.insertLeft('b')
root.insertRight('c')
root.getLeftChild().insertRight('d')
root.getRightChild().insertLeft('e')
root.getRightChild().insertRight('f')
return root
Parse Tree
1.If the current token is a ‘(‘, add a new node as the left child of the current node, and descend to the left child.
2.If the current token is in the list [“+”,”-“,”/”,”*”], set the root value of the current node to the operator represented by the current token. Add a new node as the right child of the current node and descend to the right child.
3.If the current token is a number, set the root value of the current node to the number and return to the parent.
4.If the current token is a ‘)’, go to the parent of the current node.
def buildParseTree(expr):
expr = expr.split(' ')
curTree = BinaryTree('')
stack = [curTree]
for epr in expr:
if epr == '(':
curTree.insertLeft('')
stack.append(curTree)
curTree = curTree.getLeftChild()
elif epr not in ['+','-','*','/',')']:
curTree.setRootVal(int(epr))
curTree = stack.pop()
elif epr in ['+','-','*','/']:
curTree.setRootVal(epr)
curTree.insertRight('')
stack.append(curTree)
curTree = curTree.getRightChild()
elif epr == ')':
curTree = stack.pop()
else:
raise ValuError
return curTree
import operator
def evaluate(tree):
left = tree.getLeftChild()
right = tree.getRightChild()
optr = {'+':operator.add, '-':operator.sub,'*':operator.mul,'/':operator.div}
if left and right:
return optr[tree.getRootVal()](evaluate(left), evaluate(right))
else:
return tree.getRootVal()
pt = buildParseTree("( ( 10 + 5 ) * 3 )")
print(evaluate(pt))
45
Tree Traversals 树的遍历
树的遍历方式有三种：先序遍历，中序遍历， 后序遍历
preorder 先序遍历
In a preorder traversal, we visit the root node first, then recursively do a preorder traversal of the left subtree, followed by a recursive preorder traversal of the right subtree.
inorder 中序遍历
In an inorder traversal, we recursively do an inorder traversal on the left subtree, visit the root node, and finally do a recursive inorder traversal of the right subtree.
postorder 后序遍历
In a postorder traversal, we recursively do a postorder traversal of the left subtree and the right subtree followed by a visit to the root node.
def preOrder(tree):
if tree:
print(tree.getRootVal)
preOrder(tree.getLeftChild())
preOrder(tree.getRightChild())
"""
the above one is better.
def preOrder(self):
print(self.key)
if self.leftChild:
self.leftChile.preOrder()
if self.rightChild:
self.rihtChild.preOrder()
"""
def postOrder(tree):
if tree:
postOrder(tree.getLeftChild())
postOrder(tree.getRightChild())
print(tree.getRootVal())
def postOrderEval(parsetree):
operators = {'+':operator.add, '-':operator.sub,'*':operator.mul,'/':operator.div}
if parsetree:
left = postOrderEval(parsetree.getLeftChild())
right = postOrderEval(parsetree.getRightChild())
if left and right:
return operators[parsetree.getRootVal()](left, right)
else:
return parsetree.getRootVal()
print(postOrderEval(pt))
45
def inOrder(tree):
if tree:
inOrder(tree.getLeftChild())
print(tree.getRootVal())
inOrder(tree.getRightChild())
def printExpr(parsetree):
if parsetree:
left = parsetree.getLeftChild()
right = parsetree.getRightChild()
if left and right:
return '('+ printExpr(left) + str(parsetree.getRootVal()) + printExpr(right) + ')'
else:
return str(parsetree.getRootVal())
def printexp(tree):
sVal = ""
if tree:
sVal = '(' + printexp(tree.getLeftChild())
sVal = sVal + str(tree.getRootVal())
sVal = sVal + printexp(tree.getRightChild())+')'
return sVal
print(printexp(pt))
print(printExpr(pt))
(((10)+(5))*(3))
((10+5)*3)
京公网安备 11010502036488号