多叉樹演算法
1. 求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
2. 求一個python的三叉樹演算法
這是網路上的一個版本，我自己做了一點修改，這是一個n叉樹，希望對你有所幫助
#!/usr/bin/python
#-*-coding:utf-8-*-
'''
Createdon2014-3-26
@author:qcq
'''
#==============================================================================
#tree.py:
#==============================================================================
#--
#$Revision:1.7$
#$Date:2000/03/2922:36:12$
#modifiedbyqcqin2014/3/27
#modifiedbyqcqin2014/4/23增加了遍歷樹的非遞歸版本的廣度優先和深度優先
#--
#================================================================
#Contents
#----------------------------------------------------------------
#classTree:Genericn-arytreenodeobject
#classNodeId:Representsthepathtoanodeinann-arytree
#----------------------------------------------------------------
#importstring
classTree:
"""Genericn-arytreenodeobject
Childrenareadditive;noprovisionfordeletingthem.
:0forthefirst
childadded,1forthesecond,andsoon.
modifiedbyqcqin2014/3/27.
Exports:
Tree(parent,value=None)Constructor
.parentIfthisistherootnode,None,otherwise
theparent'sTreeobject.
.childListListofchildren,zeroormoreTreeobjects.
.valueValuepassedtoconstructor;canbeanytype.
.birthOrderIfthisistherootnode,0,otherwisethe
indexofthischildintheparent's.childList
.nChildren()Returnsthenumberofself'schildren.
.nthChild(n)Returnsthenthchild;raisesIndexErrorif
nisnotavalidchildnumber.
.fullPath():.
.nodeId():ReturnspathtoselfasaNodeId.
"""
#---Tree.__init__---
def__init__(self,parent,value=None):
"""ConstructorforaTreeobject.
[if(parentisNoneoraTreeobject)->
if(parentisNone)->
,nochildren,
andvalue(value)
else->
ofparent(parent)andnochildren,andvalue(value)
]
"""
#--1--
self.parent=parent
self.value=value
self.childList=[]
#--2--
#-[if(parentisNone)->
#self.birthOrder:=0
#else->
#parent:=
#self.birthOrder:=sizeofparent's.childList
#-]
ifparentisNone:
self.birthOrder=0
else:
self.birthOrder=len(parent.childList)
parent.childList.append(self)
#---Tree.nChildren---
defnChildren(self):
"""[
]
"""
returnlen(self.childList)
#---Tree.nthChild---
defnthChild(self,n):
"""[if(nisaninteger)->
if(0<=n<(numberofself'schildren)->
returnself's(n)thchild,countingfrom0
else->
raiseIndexError
]
"""
returnself.childList[n]
#---Tree.fullPath---
deffullPath(self):
""".
[returnasequence[c0,c1,...,ci]suchthatselfis
root.nthChild(c0).nthChild(c1).....nthChild(ci),or
anemptylistifselfistheroot]
"""
#--1--
result=[]
parent=self.parent
kid=self
#--2--
#[result+:=childnumbersfromparenttoroot,in
#reverseorder]
whileparent:
result.insert(0,kid.birthOrder)
parent,kid=parent.parent,parent
#--3--
returnresult
#---Tree.nodeId---
defnodeId(self):
""".
"""
#--1--
#[fullPath:=sequence[c0,c1,...,ci]suchthatselfis
#root.nthChild(c0).nthChild(c1).....nthChild(ci),or
#anemptylistifselfistheroot]
fullPath=self.fullPath()
#--2--
returnNodeId(fullPath)
defequals(self,node):
'''
'''
returnself.value==node.value
#===========================================================================
#deletethenodefromthetree
#===========================================================================
defdelete(self):
ifself.parentisNone:
return
else:
#temp=self.birthOrder
'''
ifdeletethemiddletreeobject,
.
'''
self.parent.childList.remove(self.parent.childList[self.birthOrder])
fori,jinzip(range(self.birthOrder+1,self.parent.nChildren()),self.parent.childList[self.birthOrder+1:]):
j.birthOrder=j.birthOrder-1
defupdate(self,value):
'''
'''
self.value=value
def__str__(self):
return"The%dchildwithvalue%d"%(self.birthOrder,self.value)#-----classNodeId-----
classNodeId:
""".
Exports:
NodeId(path):
[->
-id]
.path:[aspassedtoconstructor]
.__str__():[returnselfasastring]
.find(root):
[ifrootisaTreeobject->
treerootedat(root)->
returnthe.valueofthatnode
else->
returnNone]
.isOnPath(node):
[ifnodeisaTreeobject->
->
return1
else->
return0]
"""
#---NodeId.__init__---
def__init__(self,path):
"""ConstructorfortheNodeIdobject
"""
self.path=path
#---NodeId.__str__---
def__str__(self):
"""Returnselfindisplayableform
"""
#--1--
#[L:=alistoftheelementsofself.pathconvertedtostrings]
L=map(str,self.path)
#--2--
#["/"]
returnstring.join(L,"/")
#---NodeId.find---
deffind(self,node):
"""
"""
returnself.__reFind(node,0)
#---NodeId.__reFind---
def__reFind(self,node,i):
"""Recursivenodefindingroutine.Startsatself.path[i:].
[if(nodeisaTreeobject)
and(0<=i<=len(self.path))->
ifi==len(self.path)->
returnnode'svalue
elseifself.path[i:]describesapathfromnode
tosometreeobjectT->
returnT
else->
returnNone]
"""
#--1--
ifi>=len(self.path):
returnnode.value#We'rethere!
else:
childNo=self.path[i]
#--2--
#[->
#child:=thatchildnode
#else->
#returnNone]
try:
child=node.nthChild(childNo)
exceptIndexError:
returnNone
#--3--
#[if(i+1)==len(self.path)->
#returnchild
#elseifself.path[i+1:]describesapathfromnodeto
#sometreeobjectT->
#returnT
#else->
#returnNone]
returnself.__reFind(child,i+1)
#---NodeId.isOnPath---
defisOnPath(self,node):
"""Isself'spathtoorthroughthegivennode?
"""
#--1--
#[nodePath:=pathlistfornode]
nodePath=node.fullPath()
#--2--
#[ifnodePathisaprefixof,oridenticaltoself.path->
#return1
#else->
#return0]
iflen(nodePath)>len(self.path):
return0#Nodeisdeeperthanself.path
foriinrange(len(nodePath)):
ifnodePath[i]!=self.path[i]:
return0#Nodeisadifferentroutethanself.path
return1
3. 關於演算法中的二叉樹，，，
滿二叉樹是沒有度為1的結點。
完全二叉樹定義:
若設二叉樹的高度為h，除第 h 層外，其它各層 (1~h-1) 的結點數都達到最大個數，第 h 層從右向左連續缺若干結點，這就是完全二叉樹。
完全二叉樹葉子結點的演算法:
如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1~n的結點一一對應，這棵二叉樹稱為完全二叉樹。
可以根據公式進行推導，假設n0是度為0的結點總數(即葉子結點數)，n1是度為1的結點總數，n2是度為2的結點總數，由二叉樹的性質可知:n0=n2+1，則n= n0+n1+n2(其中n為完全二叉樹的結點總數)，由上述公式把n2消去得:n= 2n0+n1-1，由於完全二叉樹中度為1的結點數只有兩種可能0或1，由此得到n0=(n+1)/2或n0=n/2，合並成一個公式:n0=(n+1)/2 ，就可根據完全二叉樹的結點總數計算出葉子結點數。
因此葉子結點數是(839+1)/2=420
4. 關於二叉樹的演算法.C++
#include<vector>
#include<iostream>
usingnamespacestd;
structTreeNode
{
intval;
TreeNode*left;
TreeNode*right;
TreeNode(intx):val(x),left(NULL),right(NULL){} //constructionfunction
};
voidfun(TreeNode*root,vector<TreeNode*>&vt)
{
if(root==nullptr)
return;
vt.push_back(root);
fun(root->left,vt);
fun(root->right,vt);
for(autoele:vt)
cout<<ele->val<<"";
cout<<endl;
vt.pop_back();
}
intmain()
{
TreeNode*root=newTreeNode(0);
root->left=newTreeNode(1);
root->right=newTreeNode(2);
root->left->right=newTreeNode(3);
root->left->right->left=newTreeNode(4);
root->right->left=newTreeNode(5);
root->right->right=newTreeNode(6);
vector<TreeNode*>vt;
fun(root,vt);
}
5. 二叉樹演算法是什麼
二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。
二叉樹的第i層至多有2^（i 1）個結點；深度為k的二叉樹至多有2^k 1個結點；對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0 = n2 + 1。二叉樹演算法常被用於實現二叉查找樹和二叉堆。
二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。
(5)多叉樹演算法擴展閱讀：
二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：
1、空二叉樹——(a)
2、只有一個根結點的二叉樹——(b);
3、右子樹為空的二叉樹——(c);
4、左子樹為空的二叉樹——(d);
5、完全二叉樹——(e)
注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。
6. 關於二叉樹遍歷演算法的問題，一個二叉樹求結點個數的問題，
意思就是這樣啊，體現的就是分治策略，本來二叉樹就可以簡化為左子樹+根+右子樹
推而廣之，很多二叉樹的基本演算法都是通過遍歷來完成的，只是遍歷的方法可能不一定是後序的
另外，按照定義，求二叉樹的高度不是左右子樹高度的和，而是左右子樹高度的最大值，最後返回這個最大值加1，空二叉樹就是0了
7. 二叉樹的深度演算法怎麼算啊
二叉樹的深度演算法：
一、遞歸實現基本思想：
為了求得樹的深度，可以先求左右子樹的深度，取二者較大者加1即是樹的深度，遞歸返回的條件是若節點為空，返回0
演算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非遞歸實現基本思想：
受後續遍歷二叉樹思想的啟發，想到可以利用後續遍歷的方法來求二叉樹的深度，在每一次輸出的地方替換成算棧S的大小，遍歷結束後最大的棧S長度即是棧的深度。
演算法的執行步驟如下：
（1）當樹非空時，將指針p指向根節點，p為當前節點指針。
（2）將p壓入棧S中，0壓入棧tag中，並令p執行其左孩子。
（3）重復步驟（2），直到p為空。
（4）如果tag棧中的棧頂元素為1，跳至步驟（6）。從右子樹返回
（5）如果tag棧中的棧頂元素為0，跳至步驟（7）。從左子樹返回
（6）比較treedeep與棧的深度，取較大的賦給treedeep，對棧S和棧tag出棧操作，p指向NULL，並跳至步驟（8）。
（7）將p指向棧S棧頂元素的右孩子，彈出棧tag，並把1壓入棧tag。（另外一種方法，直接修改棧tag棧頂的值為1也可以）
（8）循環（2）~（7），直到棧為空並且p為空
（9）返回treedeep，結束遍歷
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}
8. 二叉樹演算法有哪些應用場景
二叉樹常被用於實現二叉查找樹和二叉堆。
在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」和「右子樹」。
根據不同的用途可分為：
1、完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。
2、滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。
3、平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL演算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。
(8)多叉樹演算法擴展閱讀
深度為h的二叉樹最多有個結點(h>=1)，最少有h個結點。對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1。
有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系為若I為結點編號則 如果I>1，則其父結點的編號為I/2。如果2*I<=N，則其左孩子（即左子樹的根結點）的編號為2*I。若2*I>N，則無左孩子。如果2*I+1<=N，則其右孩子的結點編號為2*I+1。
9. 二叉樹的演算法到底是怎麼算啊！c語言一般都考些什麼演算法
我擦。二叉樹的演算法有很多，你說的是哪個？建議你去看嚴蔚敏的數據結構那本書。c語言一般考什麼演算法？你得先說明是什麼考試可行？如果你是在上c語言課，期末考試的演算法幾乎涉及不到，考的都是些常用基礎語法，演算法也都是能從課本上找到原型的。如果你是計算機二級，愛莫能助，沒考過。學計算機的，不需要考，只能祝你一切順利咯
10. 請寫出計算二叉樹的深度的演算法
typedef struct tree//二叉樹的定義
{ char data; struct tree *lchild,*rchild; }TREE,*Tree;
void create(Tree t)//創建一棵二叉樹
{ char ch; scanf("%c",&ch); if(ch=='#') t=NULL;
else { t->data=ch; create(t->lchild); create(t->rchild); }
}
int deep(Tree t)//深度演算法
{ if(!t) return 0; else { ld=deep(t->lchild); rd=deep(t->rchild);
if(ld>rd) return rd+1; else return ld+1;
}
void main()//主函數
{ Tree t; create(t); printf("%d\n",deep(t)); }