python使用二叉树

Ⅰ python二叉树问题

def __init__(self ,value=3): # value = default_value
self.value = value

这样就行了撒。
PS：以后贴代码记得把缩进对齐。。。

Ⅱ 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怎么实现二叉树排序

常用的排序算法（主要指面试中）包含两大类，一类是基础比较模型的，也就是排序的过程，是建立在两个数进行对比得出大小的基础上，这样的排序算法又可以分为两类：一类是基于数组的，一类是基于树的；基础数组的比较排序算法主要有：冒泡法，插入法，选择法，归并法，快速排序法；基础树的比较排序算法主要有：堆排序和二叉树排序；基于非比较模型的排序，主要有桶排序和位图排序（个人认为这两个属于同一思路的两个极端）。

Ⅳ python 二叉树实现思想

第一 ：return 的缩进不对 ，

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

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

Ⅳ 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 二叉树实现四则运算

#!/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字典怎么表现二叉树

用python构造一个n层的完全二叉树的代码如下： typedef struct {int weight;int parent, lchild, rchild; } HTNode ,*HuffmanTree; // 动态分配数组存储huffman树 算法设计void createHuffmantree(){ ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode.

Ⅷ python怎么在二叉树中

#coding:utf-8#author:Elvis class TreeNode(object): def __init__(self): self.data = '#' self.l_child = None self.r_child = None class Tree(TreeNode): #create a tree def create_tree(self, tree): data = raw_input('->') if data == '#': 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) #visit a tree node def visit(self, tree): #输入#号代表空树 if tree.data is not '#': print str(tree.data) + '\t', #先序遍历 def pre_order(self, tree): if tree is not None: self.visit(tree) self.pre_order(tree.l_child) self.pre_order(tree.r_child) #中序遍历 def in_order(self, tree): if tree is not None: self.in_order(tree.l_child) self.visit(tree) self.in_order(tree.r_child) #后序遍历 def post_order(self, tree): if tree is not None: 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 '\n'tree.in_order(t)print '\n'tree.post_order(t)

Ⅸ 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