二叉樹的構建python

① 一道演算法題，用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

② python編寫歐式二叉樹的問題

所以我就遇到了一下幾個問題：
1、該怎麼把二叉樹各個節點連起來？
2、怎麼定義內部數據成員？
3、如何實例化左右孩子？

在網上也沒找到比較簡單比較通用的Python二叉樹類實現，所以我花了點時間自己寫一個。
[python] view plain 在CODE上查看代碼片派生到我的代碼片
class Tree:
def __init__(self, val = '#', left = None, right = None):
self.val = val
self.left = left
self.right = right

#前序構建二叉樹
def FrontBuildTree(self):
temp = input('Please Input: ')
node = Tree(temp)
if(temp != '#'):
node.left = self.FrontBuildTree()
node.right = self.FrontBuildTree()
return node#因為沒有引用也沒有指針，所以就把新的節點給返回回去

#前序遍歷二叉樹
def VisitNode(self):
print(self.val)
if(self.val != '#'):
self.left.VisitNode()
self.right.VisitNode()

if __name__ == '__main__':
root = Tree()
root = root.FrontBuildTree()
root.VisitNode()

③ 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構造一個n層的完全二叉樹

用python構造一個n層的完全二叉樹的代碼如下：
typedefstruct{
intweight;
intparent,lchild,rchild;
}HTNode,*HuffmanTree;//動態分配數組存儲huffman樹
演算法設計
voidcreateHuffmantree(){
ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);//動態分配數組存儲huffman樹,0號單元未用
//m:huffman樹中的結點數（m=2*n-1）
for(i=1;i<=m;++i)
ht[i].parent=ht[i]->lch=ht[i]->rch=0;
for(i=1;i<=n;++i)
ht[i].weight=w[i];//初始化，w[i]：n個葉子的權值
for(i=n+1;i<=m,++i)｛//建哈夫曼樹
select(i-1),s1,s2);//在ht[k](1<=k<=i-1)中選擇兩個雙親域為零而權值取最小的結點:s1和s2
ht[s1].parent=ht[s2].parent=i;
ht[i].lch=s1;
ht[i].rch=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
};
}

⑤ 數據結構-二叉樹的創建

#include <stdio.h>
#define ElemType char
//節點聲明，數據域、左孩子指針、右孩子指針
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序建立二叉樹
BiTree CreateBiTree(){
char ch;
BiTree T;
scanf('%c',&ch);
if(ch=='#')T=NULL;
else{
T = (BiTree)malloc(sizeof(BiTNode));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根節點
}
//先序遍歷二叉樹
void PreOrderTraverse(BiTree T){
if(T){
printf('%c',T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//中序遍歷
void InOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
printf('%c',T->data);
PreOrderTraverse(T->rchild);
}
}
//後序遍歷
void PostOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
printf('%c',T->data);
}
}
void main(){
BiTree T;
T = CreateBiTree();//建立
PreOrderTraverse(T);//輸出
getch();
}

⑥ python非遞歸建立二叉樹

class Node(object):
def __init__(self, value):
self.left = None
self.right = None
self.value = value

class MyBST(object):
def __init__(self):
self.empty = True

def add(self, value):
if self.empty:
self.root = Node(value)
self.empty = False
cur = self.root
while (True):
if not cur:
cur = Node(value)
break
if value > cur.value:
if cur.value != None:
cur = cur.right
else:
newNode = Node(value)
cur.right = newNode
break
elif value < cur.value:
if cur.value != None:
cur = cur.left
else:
newNode = Node(value)
cur.left = newNode
break
else:
cur.value = value
break
在while(True)循環里添加一個if條件判斷

⑦ Python演算法之哈夫曼編碼

問題: 哈夫曼編碼,英文名稱 Huffman Coding，有時也翻譯為霍夫曼編碼，在1952年提出的，是最好的編碼方式。哈夫曼編碼在電子通訊方面有著重要的應用，同時也廣泛應用於數據壓縮坦槐，其壓縮率通常在20% 90%之間 赫夫曼碼是可變字長編碼(VLC)的一種。哈夫曼樹是最優二叉樹， 帶權路徑長度最小的二叉樹。

原理:

假設有幾個數字40,10,20,16,14。

首先將這五個數字按照從小到大的順序排列：10, 14，16，20, 40。

構建哈夫曼樹：

1.首先選取10,14

2.重新排序：16,20,24,40

3.重新排序24,36,40,60

4.按照二叉羨信沖樹左0右1，構建哈兄殲夫曼樹

所以最終得到數字10的編碼為100，數字14的編碼為101，數字16的編碼為110，數字20的編碼為111，數字40的編碼為0。

代碼：

運行結果: