Python程序員面試分類真題5

Python程序員面試分類真題5(總分：100.00，做題時間：90分鐘)面試題(總題數(shù)：7，分?jǐn)?shù)：100.00)1.

如何把一個有序整數(shù)數(shù)組放到二叉樹中

（分?jǐn)?shù)：14.00）__________________________________________________________________________________________

正確答案：(如果要把一個有序的整數(shù)數(shù)組放到二叉樹中，那么所構(gòu)造出來的二叉樹必定也是一棵有序的二叉樹。鑒于此，實現(xiàn)思路為：取數(shù)組的中間元素作為根結(jié)點，將數(shù)組分成左右兩部分，對數(shù)組的兩部分用遞歸的方法分別構(gòu)建左右子樹。如下圖所示。

如上圖所示，首先取數(shù)組的中間結(jié)點6作為二叉樹的根結(jié)點，把數(shù)組分成左右兩部分，然后對于數(shù)組的左右兩部分子數(shù)組分別運用同樣的方法進(jìn)行二叉樹的構(gòu)建，例如，對于左半部分子數(shù)組，取中間結(jié)點3作為樹的根結(jié)點，再把子數(shù)組分成左右兩部分。依此類推，就可以完成二叉樹的構(gòu)建，實現(xiàn)代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

#方法功能:把有序數(shù)組轉(zhuǎn)換為二叉樹

defarrayotree(arr,start,end):

root=None

ifend＞=start:

root=BiTNode()

mid=(start+end+1)/2

#樹的根結(jié)點為數(shù)組中間的元素

root.data=arr[mid]

#遞歸的用左半部分?jǐn)?shù)組構(gòu)造root的左子樹

root.lchild=arraytotree(arr,start,mid-1)

#遞歸的用右半部分?jǐn)?shù)組構(gòu)造root的右予樹

root.rchild=arraytotree(arr,mid+1,end)

else:

root=None

returnroot

#用中序遍歷的方式打印出二叉樹結(jié)點的內(nèi)容

defprintTreeMidOrder(root):

ifroot==None:

return

#歷root結(jié)點的左子樹

ifroot.lchild!=None:

printTreeMidOrder(root.lchild)

#遍歷root結(jié)點

printroot.data,

#遍歷root結(jié)點的右子樹

ifroot.rchild!=None:

printTreeMidOrder(root.rchild)

if__name__=="__main__":

arr=[1,2,3,4,5,6,7,8,9,10]

print"數(shù)組:",

i=0

whilei＜len(arr):

printarr[i],

i+=1

print'\n'

root=arraytotree(arr,0,len(arr)-1)

print"轉(zhuǎn)換成樹的中序遍歷為:",

printTreeMidOrder(root)

print'\n'

程序的運行結(jié)果為：

數(shù)組：12345678910

轉(zhuǎn)換成樹的中序遍歷為：12345678910

算法性能分析：

由于這種方法只遍歷了一次數(shù)組，因此，算法的時間復(fù)雜度為O(N)，其中，N表示的是數(shù)組長度。)解析：[考點]如何把一個有序整數(shù)數(shù)組放到二叉樹中2.

給定一棵二叉樹，要求逐層打印二叉樹結(jié)點的數(shù)據(jù)，例如有如下二叉樹：

對這棵二叉樹層序遍歷的結(jié)果為1，2，3，4，5，6，7。

（分?jǐn)?shù)：14.00）__________________________________________________________________________________________

正確答案：(為了實現(xiàn)對二叉樹的層序遍歷，就要求在遍歷一個結(jié)點的同時記錄下它的孩子結(jié)點的信息，然后按照這個記錄的順序來訪問結(jié)點的數(shù)據(jù)，在實現(xiàn)的時候可以采用隊列來存儲當(dāng)前遍歷到的結(jié)點的孩子結(jié)點，從而實現(xiàn)二叉樹的層序遍歷，遍歷過程如下圖所示。

在上圖中，圖(1)首先把根結(jié)點1放到隊列里面，然后開始遍歷。圖(2)隊列首元素(結(jié)點1)出隊列，同時它的孩子結(jié)點2和結(jié)點3進(jìn)隊列；圖(3)接著出隊列的結(jié)點為2，同時把它的孩子結(jié)點4和結(jié)點5放到隊列里，依此類推就可以實現(xiàn)對二叉樹的層序遍歷。

實現(xiàn)代碼如下：

fromcollectionsimportdeque

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

#方法功能:把有序數(shù)組轉(zhuǎn)換為二叉樹

defarraytotree(arr,start,end):

roo=None

ifend＞=start:

root=BiTNode();

mid=(start+end+1)/2;

#樹的根結(jié)點為數(shù)組中間的元素

root.data=arr[mid];

#遞歸的用左半部分?jǐn)?shù)組構(gòu)造root的左子樹

root.lchild=arraytotree(arr,start,mid-1);

#遞歸的用右半部分?jǐn)?shù)組構(gòu)造root的右子樹

root.rchild=arraytotree(arr,mid+1,end);

else:

root=None

returnroot

"""

方法功能:用層序遍歷的方式打印出二叉樹結(jié)點的內(nèi)容

輸入?yún)?shù):root:二叉樹根結(jié)點

"""

defprintTreeLayer(root):

ifroot==None:

return;

queue=deque()

#樹根結(jié)點進(jìn)隊列

queue.append(root)

whilelen(queue)＞0:

p=queue,popleft()

#訪問當(dāng)前結(jié)點

print(p.data),

#如果這個結(jié)點的左孩子不為空則入隊列

ifp.lchild!=None:

queue.append(p.lchild)

#如果這個結(jié)點的右孩子不為空則入隊列

ifp.rchild!=None:

queue.append(p.rchild);

if__name__=="__main__":

arr=[1,2,3,4,5,6,7,8,9,10]

root=arraytotree(arr,0,len(arr)-1);

print"樹的層序遍歷結(jié)果為:",

printTreeLaver(root);

程序的運行結(jié)果為：

樹的層序遍歷結(jié)果為：63925810147

算法性能分析：

在二叉樹的層序遍歷過程中，對樹中的各個結(jié)點只進(jìn)行了一次訪問，因此，時間復(fù)雜度為O(N)，此外，這種方法還使用了隊列來保存遍歷的中間結(jié)點，所使用隊列的大小取決于二叉樹中每一層中結(jié)點個數(shù)的最大值。具有N個結(jié)點的完全二叉樹的深度為h=log2N+1。而深度為h的這一層最多的結(jié)點個數(shù)為2h-1=n/2。也就是說隊列中可能的最多的結(jié)點個數(shù)為N/2。因此，這種算法的空間復(fù)雜度為O(N)。)解析：[考點]如何從頂部開始逐層打印二叉樹結(jié)點數(shù)據(jù)3.

給定一棵二叉樹，它的每個結(jié)點都是正整數(shù)或負(fù)整數(shù)，如何找到一棵子樹，使得它所有結(jié)點的和最大?

（分?jǐn)?shù)：14.00）__________________________________________________________________________________________

正確答案：(要求一棵二叉樹的最大子樹和，最容易想到的辦法就是針對每棵子樹，求出這棵子樹中所有結(jié)點的和，然后從中找出最大值。恰好二叉樹的后序遍歷就能做到這一點。在對二叉樹進(jìn)行后序遍歷的過程中，如果當(dāng)前遍歷的結(jié)點的值與其左右子樹和的值相加的結(jié)果大于最大值，則更新最大值。如下圖所示：

在上面這個圖中，首先遍歷結(jié)點-1，這個子樹的最大值為-1，同理，當(dāng)遍歷到結(jié)點9時，子樹的最大值為9，當(dāng)遍歷到結(jié)點3的時候，這個結(jié)點與其左右孩子結(jié)點值的和(3-1+9=11)大于最大值(9)。因此，此時最大的子樹為以3為根結(jié)點的子樹，依此類推，直到遍歷完整棵樹為止。實現(xiàn)代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

classTest:

def__init__(self):

self.maxSum=-2**31

"""

方法功能:求最大子樹

輸入?yún)?shù):root:根結(jié)點;

maxRoot最大子樹的根結(jié)點

返回值:以root為根結(jié)點子樹所有結(jié)點的和

"""

deffindMaxSubTree(self,root,maxRoot):

ifroot==None:

return0

#求root左子樹所有結(jié)點的和

1max=self.findMaxSubTree(root.lchild,maxRoot)

#求root右子樹所有結(jié)點的和

rmax=self.findMaxSubTree(root.rchild,maxRoot)

sums=1max+rmax+root.data

#以root為根的子樹的和大于前面求出的最大值

ifsums＞self.maxSum:

self.maxSum=sums

maxRoot.data=root.data

#返回以root為根結(jié)點的予樹的所有結(jié)點的和

returnsums

"""

方法功能:構(gòu)造二叉樹

返回值:返回新構(gòu)造的二叉樹的根結(jié)點

"""

defconstructTree(self):

root=BiTNode()

node1=BiTNode()

node2=BiTNode()

node3=BiTNode()

node4=BiTNode()

root.data=6

node1.data=3

node2.data=-7

node3.data=-1

node4.data=9

root.lchild=node1

root.rchild=node2

node1.lchild=node3

node1.rchild=node4

node2.lchild=node2.rchild=node3.lchild=node3.rchild=\

node4.lchild=node4.rchild=None

returnroot

if__name__=="__main__":

#構(gòu)造二叉樹

test=Test()

root=test.constructTree()

maxRoot=BiTNode()#最大子樹的根結(jié)點

test.findMaxSubTree(root,maxRoot)

print"最大子樹和為:"+str(test.maxSum)

print"對應(yīng)子捌的根結(jié)點為:"+str(maxRoot.data)

程序的運行結(jié)果為：

最大子樹和為：11

對應(yīng)子樹的根結(jié)點為：3

算法性能分析：

這種方法與二叉樹的后序遍歷有相同的時間復(fù)雜度，即為O(N)，其中，N為二叉樹的結(jié)點個數(shù)。)解析：[考點]如何求一棵二叉樹的最大子樹和4.

兩棵二叉樹相等是指這兩棵二叉樹有著相同的結(jié)構(gòu)，并且在相同位置上的結(jié)點有相同的值。如何判斷兩棵二叉樹是否相等?

（分?jǐn)?shù)：14.00）__________________________________________________________________________________________

正確答案：(如果兩棵二叉樹root1、root2相等，那么root1與root2結(jié)點的值相同，同時它們的左右孩子也有著相同的結(jié)構(gòu)，并且對應(yīng)位置上結(jié)點的值相等，即root1.data=root2.data，并且root1的左子樹與root2的左子樹相等，root1的右子樹與root2的右子樹相等。根據(jù)這個條件，可以非常容易地寫出判斷兩棵二叉樹是否相等的遞歸算法。實現(xiàn)代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rcbild=None

"""

方法功能:判斷兩棵二叉樹是否相等

參數(shù):root1與root2分別為兩棵二叉樹的根結(jié)點

返回值:true:如果兩棵樹相等則返回true,否則返回false

"""

defisEqual(root1,root2):

ifroot1==Noneandroot2==None:

returnTrue

ifroot1==Noneandroot2!=None:

returnFalse

ifroot1!=Noneandroot2==None:

returnFalse

ifroot1.data==root2.data:

returnisEqual(root1.lchild,root2.lchild)andisEqual(root1.rchild,root2.rchild)

else:

returnFalse

defconstructTree():

root=BiTNode()

node1=BiTNode()

node2=BiTNode()

node3=BiTNode()

node4=BiTNode()

root.data=6

node1.data=3

node2.data=-7

node3.data=-1

node4.data=9

root.lchild=node1

root.rchild=node2

nodel.lchild=node3

nodel.rchild=node4

node2.lchild=node2.rchild=node3.lchild=node3.rchild=\

node4.lchild=node4.rchild=None

returnroot

if__name__=="__main__":

root1=constructTree()

root2=constructTree()

equal=isEqual(root1,root2)

ifequal:

print"這兩棵樹相等"

else:

print"這兩棵樹不相等"

程序的運行結(jié)果為：

這兩棵樹相等

算法性能分析：

這種方法對兩棵樹只進(jìn)行了一次遍歷，因此，時間復(fù)雜度為O(N)。此外，這種方法沒有申請額外的存儲空間。)解析：[考點]如何判斷兩棵二叉樹是否相等5.

輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整結(jié)點的指向。例如：

（分?jǐn)?shù)：14.00）__________________________________________________________________________________________

正確答案：(由于轉(zhuǎn)換后的雙向鏈表中結(jié)點的順序與二叉樹的中序遍歷的順序相同，因此，可以對二叉樹的中序遍歷算法進(jìn)行修改，通過在中序遍歷的過程中修改結(jié)點的指向來轉(zhuǎn)換成一個排序的雙向鏈表。實現(xiàn)思路如下圖所示：假設(shè)當(dāng)前遍歷的結(jié)點為root，root的左子樹已經(jīng)被轉(zhuǎn)換為雙向鏈表(如下圖(1)所示)，使用兩個變量pHead與pEnd分別指向鏈表的頭結(jié)點與尾結(jié)點。那么在遍歷root結(jié)點的時候，只需要將root結(jié)點的lchild(左)指向pEnd，把pEnd的rchild(右)指向root；此時root結(jié)點就被加入到雙向鏈表里了，因此，root變成了雙向鏈表的尾結(jié)點。對于所有的結(jié)點都可以通過同樣的方法來修改結(jié)點的指向。因此，可以采用遞歸的方法來求解，在求解的時候需要特別注意遞歸的結(jié)束條件以及邊界情況(例如雙向鏈表為空的時候)。

實現(xiàn)代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

classTest:

def__init__(self):

self.pHead=None#雙向鏈表頭結(jié)點

self.pEnd=None#雙向鏈表尾結(jié)點

#方法功能:把有序數(shù)組轉(zhuǎn)換為二叉樹

defarraytotree(self,arr,start,end):

root=None

ifend＞=start:

root=BiTNode()

mid=(start+end+1)/2

#樹的根結(jié)點為數(shù)組中間的元素

root.data=arr[mid]

#遞歸的用左半部分?jǐn)?shù)組構(gòu)造root的左子樹

root.lchild=self.arraytotree(arr,start,mid-1)

#遞歸的用右半部分?jǐn)?shù)組構(gòu)造root的右子樹

root.rchild=self.arraytotree(arr,mid+1,end)

else:

root=None

returnroot

"""

方法功能:把二叉樹轉(zhuǎn)換為雙向列表

輸入?yún)?shù):root:二叉樹根結(jié)點

"""

definOrderBSTree(self,root):

ifroot==None:

return

#轉(zhuǎn)換root的左子樹

self.inOrderBSTree(root.lchild)

root,lchild=self.pEnd#使當(dāng)前結(jié)點的左孩子指向雙向鏈表中最后一個結(jié)點

ifNone==self.pEnd:#雙向列表為空,當(dāng)前遍歷的結(jié)點為雙向鏈表的頭結(jié)點

self.pHead=root

else:#使雙向鏈表中最后一個結(jié)點的右孩子指向當(dāng)前結(jié)點

self.pEnd.rchild=root

self.pEnd=root#將當(dāng)前結(jié)點設(shè)為雙向鏈表中最后一個結(jié)點

#轉(zhuǎn)換root的右予樹

self.inOrderBSTree(root.rchild)

if__name__=="__main__":

arr=[1,2,3,4,5,6,7]

test=Test()

root=test.arraytotree(arr,O,len(arr)-1)

test.inOrderBSTree(root)

print"轉(zhuǎn)換后雙向鏈表正向遍歷:",

#cur=BiTNode()

cur=test.pHead

whilecur!=None:

printcur.data,

cur=cur.rchild

print'\n'

print"轉(zhuǎn)換后雙向鏈表逆向遍歷:",

cur=test.pEnd

whilecur!=None:

printcur.data,

cur=cur.lchild

程序的運行結(jié)果為：

轉(zhuǎn)換后雙向鏈表正向遍歷：1234567

轉(zhuǎn)換后雙向鏈表逆向遍歷：7654321

算法性能分析：

這種方法與二叉樹的中序遍歷有著相同的時間復(fù)雜度O(N)。此外，這種方法只用了兩個額外的變量pHead與pEnd來記錄雙向鏈表的首尾結(jié)點，因此，空間復(fù)雜度為O(1)。)解析：[考點]如何把二叉樹轉(zhuǎn)換為雙向鏈表6.

輸入一個整數(shù)數(shù)組，判斷該數(shù)組是否是某二元查找樹的后序遍歷的結(jié)果。如果是，那么返回true，否則返回false。例如數(shù)組[1，3，2，5，7，6，4]就是下圖中二叉樹的后序遍歷序列。

（分?jǐn)?shù)：14.00）__________________________________________________________________________________________

正確答案：(二元查找樹的特點是：對于任意一個結(jié)點，它的左子樹上所有結(jié)點的值都小于這個結(jié)點的值，它的右子樹上所有結(jié)點的值都大于這個結(jié)點的值。根據(jù)它的這個特點以及二元查找樹后序遍歷的特點，可以看出，這個序列的最后一個元素一定是樹的根結(jié)點(上圖中的結(jié)點4)，然后在數(shù)組中找到第一個大于根結(jié)點4的值5，那么結(jié)點5之前的序列(1，3，2)對應(yīng)的結(jié)點一定位于結(jié)點4的左子樹上，結(jié)點5(包含這個結(jié)點)后面的序列一定位于結(jié)點4的右子樹上(也就是說結(jié)點5后面的所有值都應(yīng)該大于或等于4)。對于結(jié)點4的左子樹遍歷的序列{1，3，2}以及右子樹的遍歷序列{5，7，6}可以采用同樣的方法來分析，因此，可以通過遞歸方法來實現(xiàn)，實現(xiàn)代碼如下：

"""

方法功能:判斷一個數(shù)組是否是二元查找樹的后續(xù)遍歷序列

輸入?yún)?shù):arr:數(shù)組:

返回值:true:是,否則返回false

"""

defIsAfterOrder(arr,start,end):

ifarr==None:

returnFalse

#數(shù)組的最后一個結(jié)點必定是根結(jié)點

root=arr[end]

#找到第一個大于root的值,那么前面所有的結(jié)點都位于root的左子樹上

i=start

whilei＜end:

if(arr[i]＞root):

break

i+=1

#如果序列是后續(xù)遍歷的序列,那么從i開始的所有值都應(yīng)該大于根結(jié)點root的值

j=i

whilej＜end:

ifarr[j]＜root:

returnFalse

j+=1

left_IsAfterOrder=True

right_IsAfterOrder=True

#判斷小于root值的序列是否是某一二元查找樹的后續(xù)遍歷

ifi＞start:

left_IsAfierOrder=IsAfterOrder(arr,start,i-1)

#判斷大于root值的序列是否是某一二元查找樹的后續(xù)遍歷

ifj＜end:

right_IsAfterOrder=IsAfterOrder(arr,i,end)

returnleft_IsAfterOrderandright_IsAfterOrder

if__name__="__main__":

arr=[1,3,2,5,7,6,4]

result=IsAfterOrder(arr,0,len(arr)-1)

i=0

whilei＜len(arr):

printarr[i],

i+-=1

ifresult:

print"是某一二元查找樹的后續(xù)遍歷序列"

else:

print"不是某一二元查找樹的后續(xù)遍歷序列"

程序的運行結(jié)果為：

1325764是某一二元查找樹的后序遍歷序列

算法性能分析：

這種方法對數(shù)組只進(jìn)行了一次遍歷，因此，時間復(fù)雜度O(N)。)解析：[考點]如何判斷一個數(shù)組是否是二元查找樹后序遍歷的序列7.

對于一棵給定的排序二叉樹，求兩個結(jié)點的共同父結(jié)點，例如在下圖中，結(jié)點1和結(jié)點5的共同父結(jié)點為3。

（分?jǐn)?shù)：16.00）__________________________________________________________________________________________

正確答案：(方法一：路徑對比法

對于一棵二叉樹的兩個結(jié)點，如果知道了從根結(jié)點到這兩個結(jié)點的路徑，就可以很容易地找出它們最近的公共父結(jié)點。因此，可以首先分別找出從根結(jié)點到這兩個結(jié)點的路徑(例如上圖中從根結(jié)點到結(jié)點1的路徑為6-＞3-＞2-＞1，從根結(jié)點到結(jié)點5的路徑為6-＞3-＞5)；然后遍歷這兩條路徑，只要是相等的結(jié)點都是它們的父結(jié)點，找到最后一個相等的結(jié)點即為離它們最近的共同父結(jié)點，在這個例子中，結(jié)點3就是它們共同的父結(jié)點。示例代碼如下：

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

classstack:

#模擬棧

def__init__(self):

self.items=[]

#判斷棧是否為空

defisEmpty(self):

returnlen(self.items)==0

#返回棧的大小

defsize(self):

returnlen(self.items)

#返回棧頂元素

defpeek(self):

ifnotself.isEmpty():

returnself.items[len(self.items)-1]

else:

returnNone

#彈棧

defpop(self):

iflen(self.items)＞0:

returnself.items.pop()

else:

print"棧已經(jīng)為空"

returnNone

#壓棧

defpush(self,item):

self.items.append(item)

"""

方法功能:獲取二叉樹從根結(jié)點root到node結(jié)點的路徑

輸入?yún)?shù):root:根結(jié)點;node:二叉樹中的某個結(jié)點;s:用來存儲路徑的棧返回值:node在root的予樹上,或node==root時返回true,否則返回false

"""

defgetPathFromRoot(root,node,s):

ifroot==None:

returnFalse

ifroot==node:

s.push(root)

returnTrue

"""

如果node結(jié)點在root結(jié)點的左予樹或右子樹上,

那么root就是node的祖先結(jié)點,把它加到棧里

"""

ifgetPathFromRoot(root.lchild,node,s)orgetPathFromRoot(root.rchild,node,s):

s.push(root)

returnTrue

returnFalse

"""

方法功能:查找二叉樹中兩個結(jié)點最近的共同父結(jié)點

輸入?yún)?shù):root:根結(jié)點;node1與node2為二叉樹中兩個結(jié)點

返回值:node1與node2最近的共同父結(jié)點

"""

defFindParentNode(root,node1,node2):

stack1=stack()#保存從root到node1的路徑

stack2=stack()#保存從root到node2的路徑

#獲取從root到node1的路徑

getPathFromRoot(root,node1,stack1)

#獲取從root到node2的路徑

getPathFromRoot(root,node2,stack2)

commonParent=None

#獲取最靠近node1和node2的父結(jié)點

whilestackl.peek()==stack2.peek():

commonParent=stack1.peek()

stack1.pop()

stack2.pop()

returncommonParent

if__name__=="__main__":

arr=[1,2,3,4,5,6,7,8,9,10]

root=arraytotree(arr,0,len(arr)-1)

node1=root.lchild.lchild.lchild

node2=root.lchild.rchild

res=None

res=FindParentNode(root,node1,node2)

ifres!=None:

printstr(node1.data)+"與"+str(node2.data)+"的最近公共父結(jié)點為:"+str(res.data),

else:

print"沒有公共父結(jié)點"

程序的運行結(jié)果為：

1與5的最近公共父結(jié)點為：3

算法性能分析：

當(dāng)獲取二叉樹從根結(jié)點root到node結(jié)點的路徑時，最壞的情況就是把樹中所有結(jié)點都遍歷了一遍，這個操作的時間復(fù)雜度為O(N)，再分別找出從根結(jié)點到兩個結(jié)點的路徑后，找它們最近的公共父結(jié)點的時間復(fù)雜度也為O(N)，因此，這種方法的時間復(fù)雜度為O(N)。此外，這種方法用棧保存了從根結(jié)點到特定結(jié)點的路徑，在最壞的情況下，這個路徑包含了樹中所有的結(jié)點，因此，空間復(fù)雜度也為O(N)。

很顯然，這種方法還不夠理想。下面介紹另外一種能降低空間復(fù)雜度的方法。

方法二：結(jié)點編號法

根據(jù)性質(zhì)，可以把二叉樹看成是一棵完全二叉樹(不管實際的二叉樹是否為完全二叉樹，二叉樹中的結(jié)點都可以按照完全二叉樹中對結(jié)點編號的方式進(jìn)行編號)，下圖為對二叉樹中的結(jié)點按照完全二叉樹中結(jié)點的編號方式進(jìn)行編號后的結(jié)果，結(jié)點右邊的數(shù)字為其對應(yīng)的編號。

根據(jù)性質(zhì)可以知道，一個編號為n的結(jié)點，它的父親結(jié)點的編號為n/2。假如要求node1與node2的最近的共同父結(jié)點，首先把這棵樹看成是一棵完全二叉樹(不管結(jié)點是否存在)，分別求得這兩個結(jié)點的編號n1，n2。然后每次找出n1與n2中較大的值除以2，直到n1==n2為止，此時n1或n2的值對應(yīng)結(jié)點的編號就是它們最近的共同父結(jié)點的編號，接著可以根據(jù)這個編號信息找到對應(yīng)的結(jié)點，具體方法為：通過觀察二叉樹中結(jié)點的編號可以發(fā)現(xiàn)：首先把根結(jié)點root看成1，求root的左孩子編號的方法為把root對應(yīng)的編號看成二進(jìn)制，然后向左移一位，末尾補(bǔ)0，如果是root的右孩子，那么末尾補(bǔ)1，因此，通過結(jié)點位置的二進(jìn)制碼就可以確定這個結(jié)點。例如結(jié)點3的編號為2(二進(jìn)制10)，它的左孩子的求解方法為：10，向左移一位末尾補(bǔ)0，可以得到二進(jìn)制100(十進(jìn)制4)，位置為4的結(jié)點的值為2。從這個特性可以得出通過結(jié)點位置信息獲取結(jié)點的方法，例如要求位置4的結(jié)點，4的二進(jìn)制碼為100，由于1代表根結(jié)點，接下來的一個0代表是左子樹root.lcluld，最后一個0也表示左子樹root.lchild.lchild，通過這種方法非常容易根據(jù)結(jié)點的編號找到對應(yīng)的結(jié)點。實現(xiàn)代碼如下：

importmath

classBiTNode:

def__init__(self):

self.data=None

self.lchild=None

self.rchild=None

#方法功能:把有序數(shù)組轉(zhuǎn)換為二叉樹

defarraytotree(arr,start,end):

root=None

ifend＞=start:

root=BiTNode()

mid=(start+end+1)/2

#樹的根結(jié)點為數(shù)組中問的元素

root.data=arr[mid]

#遞歸的用左半部分?jǐn)?shù)組構(gòu)造root的左子樹

root.lchild=arraytotree(arr,start,mid-1)

#遞歸的用右半部分?jǐn)?shù)組構(gòu)造root的右予樹

root.rchild=arraytotree(arr,mid+1,end)

else:

root=None

returnroot

classIntRef:

def__init__(self):

self.num=None

"""

方法功能:找出結(jié)點在二叉樹中的編號

輸入?yún)?shù):root:根結(jié)點node:待查找結(jié)點;number:node結(jié)點在二叉樹中的編號

返回值:true:找到該結(jié)點的位置,否則返回false

"""

defgetNo(root,node,number):

ifroot==None:

returnFalse

ifroot==node:

returnTrue

tmp=number.num

number.num=2*tmp

#node結(jié)點在root的左子樹中,左子樹編號為當(dāng)前結(jié)點編號的2倍

ifgetNo(root.lchild,node,number):

returnTrue

#node結(jié)點在root的右子樹中,右子樹編號為當(dāng)前結(jié)點編號的2倍加1

else:

number.num=tmp*2+1

returngetNo(root.rchild,node,number)

"""

方法功能:根據(jù)結(jié)點的編號找出對應(yīng)的結(jié)點

輸入?yún)?shù):root:根結(jié)點;number為結(jié)點的編號

返回值:編號為number對應(yīng)的結(jié)點

"""

defgetNodeFromNum(root,number):

ifroot==Noneornumber＜0:

returnNone

ifnumber=1:

returnroot

#結(jié)點編號對應(yīng)二進(jìn)制的位數(shù)(最高位一定為1,因為根結(jié)點代表1)

lens=int((math.log(number)/math.log(2)))

#去掉根結(jié)點表示的1

number-=1＜＜lens

whilelens＞0:

#如果這一位二進(jìn)制的值為1,

#那么編號為number的結(jié)點必定在當(dāng)前結(jié)點的右子樹上

if(1＜＜(lens-1))&number==1:

root=root.rchild

else:

root=root.lchild

lens-=1

returnroot

"""