二叉树的查询Python

㈠ python 二叉树是怎么实现的

#coding:utf-8
#author:Elvis

classTreeNode(object):
def__init__(self):
self.data='#'
self.l_child=None
self.r_child=None

classTree(TreeNode):
#createatree
defcreate_tree(self,tree):
data=raw_input('->')
ifdata=='#':
tree=None
else:
tree.data=data
tree.l_child=TreeNode()
self.create_tree(tree.l_child)
tree.r_child=TreeNode()
self.create_tree(tree.r_child)

#visitatreenode
defvisit(self,tree):
#输入#号代表空树
iftree.dataisnot'#':
printstr(tree.data)+'	',
#先序遍历
defpre_order(self,tree):
iftreeisnotNone:
self.visit(tree)
self.pre_order(tree.l_child)
self.pre_order(tree.r_child)

#中序遍历
defin_order(self,tree):
iftreeisnotNone:
self.in_order(tree.l_child)
self.visit(tree)
self.in_order(tree.r_child)

#后序遍历
defpost_order(self,tree):
iftreeisnotNone:
self.post_order(tree.l_child)
self.post_order(tree.r_child)
self.visit(tree)

t=TreeNode()
tree=Tree()
tree.create_tree(t)
tree.pre_order(t)
print'
'
tree.in_order(t)
print'
'
tree.post_order(t)

㈡ python怎么做二叉查找树

可以的，和C++中类的设计差不多，以下是二叉树的遍历
class BTree:
def __init__(self,value):
self.left=None
self.data=value
self.right=None

def insertLeft(self,value):
self.left=BTree(value)
return self.left
#return BTree(value)

def insertRight(self,value):
self.right=BTree(value)
return self.right

def show(self):
print self.data

def preOrder(node):
node.show()
if node.left:
preOrder(node.left)
if node.right:
preOrder(node.right)

def inOrder(node):
if node:
if node.left:
inOrder(node.left)
node.show()
if node.right:
inOrder(node.right)

if __name__=='__main__':
Root=BTree('root')
A=Root.insertLeft('A')
C=A.insertLeft('C')
D=A.insertRight('D')
F=D.insertLeft('F')
G=D.insertRight('G')
B=Root.insertRight('B')
E=B.insertRight('E')

preOrder(Root)
print 'This is binary tree in-traversal'
inOrder(Root)

㈢ python二叉树输出结果为什么是这样

1. 二叉树

二叉树(binary tree)中的每个节点都不能有多于两个的儿子。

图 ((7+3)*(5-2))的表达式树表示

2.1 根据中缀表达式构造表达式树：

遍历表达式：

1.建立一个空树

2.遇到'('，为当前的Node添加一个left child，并将left child当做当前Node。

3.遇到数字，赋值给当前的Node，并返回parent作为当前Node。

4.遇到('+-*/')，赋值给当前Node，并添加一个Node作为right child，将right child当做当前的Node。

5.遇到')',返回当前Node的parent。

defbuildexpressionTree(exp):tree=BinaryTree('')stack=[]stack.append(tree)currentTree=treeforiinexp:ifi=='(':currentTree.insertLeft('')stack.append(currentTree)currentTree=currentTree.leftChildelifinotin'+-*/()':currentTree.key=int(i)parent=stack.pop()currentTree=parentelifiin'+-*/':currentTree.key=icurrentTree.insertRight('')stack.append(currentTree)currentTree=currentTree.rightChildelifi==')':currentTree=stack.pop()else:raiseValueErrorreturntree

上述算法对中缀表达式的写法要求比较繁琐，小括号应用太多，例如要写成(a+(b*c))的形式。

用后缀表达式构建表达式树会方便一点:如果符号是操作数，建立一个单节点并将一个指向它的指针推入栈中。如果符号是一个操作符，从栈中弹出指向两棵树T1和T2的指针并形成一棵新的树，树的根为此操作符，左右儿子分别指向T2和T1.

123456789101112131415defbuild_tree_with_post(exp):stack=[]oper='+-*/'foriinexp:ifinotinoper:tree=BinaryTree(int(i))stack.append(tree)else:righttree=stack.pop()lefttree=stack.pop()tree=BinaryTree(i)tree.leftChild=lefttreetree.rightChild=righttreestack.append(tree)returnstack.pop()

3.树的遍历

3.1 先序遍历(preorder travelsal)

先打印出根，然后递归的打印出左子树、右子树，对应先缀表达式

12345678defpreorder(tree,nodelist=None):ifnodelistisNone:nodelist=[]iftree:nodelist.append(tree.key)preorder(tree.leftChild,nodelist)preorder(tree.rightChild,nodelist)returnnodelist

3.2 中序遍历(inorder travelsal)

先递归的打印左子树，然后打印根，最后递归的打印右子树，对应中缀表达式

12345definorder(tree):iftree:inorder(tree.leftChild)printtree.keyinorder(tree.rightChild)

3.3 后序遍历(postorder travelsal)

递归的打印出左子树、右子树，然后打印根，对应后缀表达式

1234567defpostorder(tree):iftree:forkeyinpostorder(tree.leftChild):yieldkeyforkeyinpostorder(tree.rightChild):yieldkeyyieldtree.key

3.4 表达式树的求值

1234567891011defpostordereval(tree):operators={'+':operator.add,'-':operator.sub,'*':operator.mul,'/':operator.truediv}leftvalue=Nonerightvalue=Noneiftree:leftvalue=postordereval(tree.leftChild)rightvalue=postordereval(tree.rightChild)ifleftvalueandrightvalue:returnoperators[tree.key](leftvalue,rightvalue)else:returntree.key

㈣ python 二叉树实现思想

第一 ：return 的缩进不对 ，

ifself.root==None:
self.root=node
return#如果这里不缩进，下面的语句无意义，直接返回，不会执行。

while queue这个循环的作用的是从root根结点开始，向下查找第一个左(右)子结点为空的结点，将node插入这个位置,queue的作用是将查找到的非空子结点保存在queue中，然后依次向下查找这些子结点的左右子结点

㈤ python 如何将一段字符串用二叉树的后序遍历打印出来

# -*- coding:utf-8 -*-def fromFMtoL( mid ): global las #全局后序遍历 global fir #先序遍历 root = fir[0] #取出当前树根 fir = fir[1:] #取出树根后 先序遍历把根拿出来 下面一个元素做树根 root_po = mid.find( root ) #在中序遍历当中树根的位置 left = mid[0:root_po] #左子树 right = mid[root_po+1:len(mid)] #右子树 ''' 后序遍历： 左 右 根 先左子树 再右子树 最后跟 ''' #有左子树的时候 if len(left) > 0: fromFMtoL( left ) #有右子树的时候 if len(right) > 0: fromFMtoL( right ) #树根写进结果 las += rootif __name__ == "__main__" : # fir = input("请输入先序遍历：") #前序遍历的结果 # mid = input("请输入中序遍历：") #中序遍历的结果 fir = "DBACEGF" mid = "ABCDEFG" # fir = "ABC" # mid = "BAC" las = "" fromFMtoL( mid ) print(las)

㈥ python 查找二叉树是否有子树

python中的二叉树模块内容：
BinaryTree：非平衡二叉树
AVLTree：平衡的AVL树
RBTree：平衡的红黑树
以上是用python写的，相面的模块是用c写的，并且可以做为Cython的包。
FastBinaryTree
FastAVLTree
FastRBTree
特别需要说明的是：树往往要比python内置的dict类慢一些，但是它中的所有数据都是按照某个关键词进行排序的，故在某些情况下是必须使用的。
安装和使用
安装方法
安装环境：
ubuntu12.04, python 2.7.6

㈦ 求Python二叉树的几个算法 求几个二叉树的method！ 1) 给一个值，然后在树中找出该值

你好：

二叉树算法，网上是比较多的；

可能按照你的需求不是很多：

下面是我用的一个，不过你可以借鉴一下的：

#-*-coding:cp936-*-
importos
classNode(object):
"""docstringforNode"""
def__init__(self,v=None,left=None,right=None,parent=None):
self.value=v
self.left=left
self.right=right
self.parent=parent
classBTree(object):
"""docstringforBtTee"""
def__init__(self):
self.root=None
self.size=0
definsert(self,node):
n=self.root
ifn==None:
self.root=node
return
whileTrue:
ifnode.value<=n.value:
ifn.left==None:
node.parent=n
n.left=node
break
else:
n=n.left
ifnode.value>n.value:
ifn.right==None:
n.parent=n
n.right=node
break
else:
n=n.right
deffind(self,v):
n=self.root#http://yige.org
whileTrue:
ifn==None:
returnNone
ifv==n.value:
returnn
ifv<n.value:
n=n.left
continue
ifv>n.value:
n=n.right
deffind_successor(node):
'''查找后继结点'''
assertnode!=Noneandnode.right!=None
n=node.right
whilen.left!=None:
n=n.left
returnn
defdelete(self,v):
n=self.find(v)
print"delete:",n.value
del_parent=n.parent
ifdel_parent==None:
self.root=None;
return
ifn!=None:
ifn.left!=Noneandn.right!=None:
succ_node=find_successor(n)
parent=succ_node.parent
ifsucc_node==parent.left:
#ifsucc_nodeisleftsubtree
parent.left=None
ifsucc_node==parent.right:
#ifsucc_nodeisrightsubtree
parent.right=None
ifdel_parent.left==n:
del_parent.left=succ_node
ifdel_parent.right==n:
del_parent.right=succ_node
succ_node.parent=n.parent
succ_node.left=n.left
succ_node.right=n.right
deln
elifn.left!=Noneorn.right!=None:
ifn.left!=None:
node=n.left
else:
node=n.right
node.parent=n.parent
ifdel_parent.left==n:
del_parent.left=node
ifdel_parent.right==n:
del_parent.right=node
deln
else:
ifdel_parent.left==n:
del_parent.left=None
ifdel_parent.right==n:
del_parent.right=None
deftranverse(self):
defpnode(node):
ifnode==None:
return
ifnode.left!=None:
pnode(node.left)
printnode.value
ifnode.right!=None:
pnode(node.right)
pnode(self.root)
defgetopts():
importoptparse,locale
parser=optparse.OptionParser()
parser.add_option("-i","--input",dest="input",help=u"helpname",metavar="INPUT")
(options,args)=parser.parse_args()
#printoptions.input
return(options.input)
if__name__=='__main__':
al=[23,45,67,12,78,90,11,33,55,66,89,88,5,6,7,8,9,0,1,2,678]
bt=BTree()
forxinal:
bt.insert(Node(x))
bt.delete(12)
bt.tranverse()
n=bt.find(12)
ifn!=None:
print"findvalud:",n.value

㈧ python 二叉树实现四则运算

#!/usr/bin/python#* encoding=utf-8s = "20-5*(0+1)*5^(6-2^2)" c = 0top = [0,s[c],0]op = [["0","1","2","3","4","5","6","7","8","9"],["+","-"],["*","/"],["^"]] def getLev(ch): for c1 in range(0, len(op)): for c2 in range(0, len(op[c1])): if (op[c1][c2]==ch): return c1 elif (len(ch)>1): match = 0 for c3 in range(0, len(ch)): if (getLev(ch[c3])>=0): match+=1 if (match==len(ch)):return c1 return -1

㈨ python二叉树算法

定义一颗二叉树，请看官自行想象其形状

class BinNode( ):
def __init__( self, val ):
self.lchild = None
self.rchild = None
self.value = val

binNode1 = BinNode( 1 )
binNode2 = BinNode( 2 )
binNode3 = BinNode( 3 )
binNode4 = BinNode( 4 )
binNode5 = BinNode( 5 )
binNode6 = BinNode( 6 )

binNode1.lchild = binNode2
binNode1.rchild = binNode3
binNode2.lchild = binNode4
binNode2.rchild = binNode5
binNode3.lchild = binNode6