用python语言写二叉树

A. python打印二叉树所有路径的主函数怎样写

基本算法就是二叉树的遍历，首先想到的是深度优先遍历。
难缺毁橘点在于，如何实现每个子路径的记录和append
binaryTreePaths函数只伏团给了root变量，余衡无法存储每个子路径，考虑写辅助函数res，添加存储路径的变量
res(root,temp)
同时还需要一个全局变量result存储最后的输出结果，result.append(temp)

B. python 查找二叉树是否有子树

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

C. python二叉树问题

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

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

D. Python 二叉树的创建和遍历、重建

几个有限元素的集合，该集合为空或者由一个根（Root）的元素及两不相交的（左子树和右子树）的二叉树组成，是有序树，当集合为空时，称为空二叉树，在二叉树中，一个元素也称为一个结点。

前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

中序遍历：若树为空，则空操作返回，否则从根结点开始（不是先访问根结点），中序遍历根结点的左子树，然后访问根节点，最后中序遍历右子树。

后序遍历：若树为空，则空操作返回，否则从左到右先访问叶子结点后结点的方式遍历左右子树，最后访问根节点。

层序遍历：若树为空，则空操作返回，否则从树的每一层，即从根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

假设已知后序遍历和中序遍历结果，从后序遍历的结果可以等到最后一个访问的结点是根节点，对于最简单的二叉树，此时在中序遍历中找到根节点之后，可以分辨出左右子树，这样就可以重建出这个最简单的二叉树了。而对于更为复杂的二叉树，重建得到根结点和暂时混乱的左右结点，通过递归将左右结点依次重建为子二叉树，即可完成整个二叉树的重建。（在得到根结点之后，需要在中序遍历序列中寻找根结点的位置，并将中序序列拆分为左右部分，所以要求序列中不能有相同的数字，这是序列重建为二叉树的前提。）

Root =None

strs="abc##d##e##"   #前序遍历扩展的二叉树序列

vals =list(strs)

Roots=Create_Tree(Root,vals)#Roots就是我们要的二叉树的根节点。

print(Roots)

inorderSearch = inOrderTraverse2(Roots)

print(inorderSearch)

E. 如何用python构造一个n层的完全二叉树

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

F. python二叉树求深度的一个问题，有代码，求解释

这是递归算法
我们可以先假设函数功能已经实现，left从左子树拿到一个深度值，right从右子树拿到一个深度值，最后，本层的深度为left和right的最大值加1，也就是最大深度值再算上自己这一层。
也可以从停止条件开始思考，什么时候不再递归呢？当root为空时，并返回深度值为0。调用这一层的函数得到返回值就是0，我们假设这是左子树left得到的值，同时假设右子树也为空，所以right也为0。那么返回给上一层的值就是left和right最大值加1，就是1，表示这个节点深度为1。同理，可以得到整棵树深度。

G. 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

H. 一道算法题，用python初始化一颗二叉树并求解其最短路径的值

二叉树算法，可能按照你的需求不是很多：
下面是我用的一个，不过你可以借鉴一下的：
# -*- coding: cp936 -*-
import os
class Node(object):
"""docstring for Node"""
def __init__(self, v = None, left = None, right=None, parent=None):
self.value = v
self.left = left
self.right = right
self.parent = parent
class BTree(object):
"""docstring for BtTee """
def __init__(self):
self.root = None
self.size = 0
def insert(self, node):
n = self.root
if n == None:
self.root = node
return
while True:
if node.value <= n.value:
if n.left == None:
node.parent = n
n.left = node
break
else:
n = n.left
if node.value > n.value:
if n.right == None:
n.parent = n
n.right = node
break
else:
n = n.right
def find(self, v):
n = self.root # http://yige.org
while True:
if n == None:
return None
if v == n.value:
return n
if v < n.value:
n = n.left
continue
if v > n.value:
n = n.right
def find_successor(node):
'''查找后继结点'''
assert node != None and node.right != None
n = node.right
while n.left != None:
n = n.left
return n
def delete(self, v):
n = self.find(v)
print "delete:",n.value
del_parent = n.parent
if del_parent == None:
self.root = None;
return
if n != None:
if n.left != None and n.right != None:
succ_node = find_successor(n)
parent = succ_node.parent
if succ_node == parent.left:
#if succ_node is left sub tree
parent.left = None
if succ_node == parent.right:
#if succ_node is right sub tree
parent.right = None
if del_parent.left == n:
del_parent.left = succ_node
if del_parent.right == n:
del_parent.right = succ_node
succ_node.parent = n.parent
succ_node.left = n.left
succ_node.right = n.right
del n
elif n.left != None or n.right != None:
if n.left != None:
node = n.left
else:
node = n.right
node.parent = n.parent
if del_parent.left == n:
del_parent.left = node
if del_parent.right == n:
del_parent.right = node
del n
else:
if del_parent.left == n:
del_parent.left = None
if del_parent.right == n:
del_parent.right = None
def tranverse(self):
def pnode(node):
if node == None:
return
if node.left != None:
pnode(node.left)
print node.value
if node.right != None:
pnode(node.right)
pnode(self.root)
def getopts():
import optparse, locale
parser = optparse.OptionParser()
parser.add_option("-i", "--input", dest="input", help=u"help name", metavar="INPUT")
(options, args) = parser.parse_args()
#print options.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()
for x in al :
bt.insert(Node(x))
bt.delete(12)
bt.tranverse()
n = bt.find(12)
if n != None:
print "find valud:",n.value

I. 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