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