數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)(二)

1.4 樹(Tree)

1.4.1 術(shù)語

節(jié)點炭分、邊桃焕、根、路徑欠窒、子節(jié)點、父節(jié)點退子、兄弟岖妄、子樹、葉節(jié)點寂祥、層數(shù)荐虐、高度

1.4.2 代碼表示

class BinaryTree():
    def __init__(self, rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
    
    def insertLeft(self, newnode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newnode)
        
        else:
            t = BinaryTree(newnode)
            t.leftChild = self.leftChild
            self.leftChild = t
            
    def insertRight(self, newnode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newnode)
        else:
            t = BinaryTree(newnode)
            t.leftChild = self.leftChild
            self.leftChild = t
            
    def getRightChild(self):
        return self.rightChild
    
    def getLeftChild(self):
        return self.leftChild
    
    def setRootVal(self, obj):
        self.key = obj
        
    def getRootVal(self):
        return self.key
    
    def preorder(self):
        
        print(self.key)
        if self.leftChild:
            self.leftChild.preorder()
        if self.rightChild:
            self.rightChild.preorder()
r = BinaryTree('a')
print(r.getRootVal())
print(r.getLeftChild())
a
None
r.insertLeft('b')
print(r.getLeftChild())
<__main__.BinaryTree object at 0x1111f8518>

1.4.3 分析樹

分析樹(parse tree),也叫具體語法樹(concrete syntax tree),不同于抽象語法樹丸凭。

使用表達式:(3+(4*5))福扬,構(gòu)建分析樹腕铸。

規(guī)則如下:

  • 如果當(dāng)前符號是 '(' ,添加一個新節(jié)點作為當(dāng)前節(jié)點的左子節(jié)點铛碑,并下降到左子節(jié)點(currentTree)狠裹。

  • 如果當(dāng)前符號在列表 ['+', '-', '/', '*'] 中,請將當(dāng)前節(jié)點的根植設(shè)置為當(dāng)前符號表示的運算符汽烦。添加一個新節(jié)點作為當(dāng)前節(jié)點的右子節(jié)點涛菠。

  • 如果當(dāng)前符號是數(shù)字,請將當(dāng)前節(jié)點的根值設(shè)置為該數(shù)字并返回到父節(jié)點撇吞。

  • 如果當(dāng)前符號是 ')'俗冻,則轉(zhuǎn)到當(dāng)前節(jié)點的父節(jié)點。

from pythonds.basic.stack import Stack
from pythonds.trees.binaryTree import BinaryTree
def preorder(tree):
    if tree:
        print(tree.getRootVal())
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())


def buildParseTree(fpexp):
    fplist = fpexp.split()
    pStack = Stack()
    eTree = BinaryTree('')
    pStack.push(eTree)
    currentTree = eTree
    
    for i in fplist:
        if i == '(':
            # 規(guī)則 1
            currentTree.insertLeft('')
            pStack.push(currentTree)
            currentTree = currentTree.getLeftChild()
        elif i not in ['+', '-', '/', '*']:
            # 規(guī)則 3
            currentTree.setRootVal(i)
            parent = pStack.pop()
            currentTree = parent
        elif i in ['+', '-', '/', '*']:
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree)
            currentTree = currentTree.getRightChild()
        elif i == ')':
            currentTree = pStack.pop()
        else:
            raise ValueError
    currentTree.preorder()
            
pt = buildParseTree('((10+5)*3)')
((10+5)*3)

1.4.4 樹的遍歷

前序遍歷:根節(jié)點 -> 左子樹 -> 右子樹
中序遍歷:左子樹 -> 根節(jié)點 -> 右子樹
后序遍歷:左子樹 -> 右子樹 -> 根節(jié)點

后序遍歷的常見用法牍颈,即計算分析樹迄薄。

1.4.5 基于二叉堆的優(yōu)先隊列

1.4.5.1 二叉堆結(jié)構(gòu)

class BinHeap:
    def __init__(self):
        self.heapList = []
        self.currentSize = 0
    def percUp(self, i): # i 為末尾
        while i//2 > 0: #  不是頭節(jié)點
            if self.heapList[i] < self.heapList[i//2]:
                  self.heapList[i], self.heapList[i//2] = self.heapList[i//2], self.headpList[i]
            i = i//2
    def insert(self, k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)
    def minChild(self, i):
        # 給出最小節(jié)點
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i*2] < self.heapList[i*2+1]:
                return i * 2
            else:
                return i * 2 + 1
    def percDown(self, i):
        while ( i * 2 ) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                self.heapList[i], self.heapList[mc] = self.heapList[mc] + self.heapList[i]
            i = mc
    def delMin(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval
    def bulidHeap(self, alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.percDown(i)
            i = i - 1

1.4.6 二叉查找樹

BST屬性:左子樹的 key 小于父節(jié)點,右子樹的 key 都大于父節(jié)點煮岁。

class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild

    def hasBothChildren(self):
        return self.rightChild and self.leftChild

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self


class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def put(self,key,val):
        # 插入新節(jié)點
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)
        self.size = self.size + 1

    def _put(self,key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                   self._put(key,val,currentNode.leftChild)
            else:
                   currentNode.leftChild = TreeNode(key,val,parent=currentNode)
        else:
            if currentNode.hasRightChild():
                   self._put(key,val,currentNode.rightChild)
            else:
                   currentNode.rightChild = TreeNode(key,val,parent=currentNode)

    def __setitem__(self,k,v):
        return self.put(k,v)

    def get(self,key):
        if self.root:
            res = self._get(key,self.root)
            if res:
                return res.payload
            else:
                return None

    def _get(self,key,currentNode):
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif key < currentNode.key:
            return self._get(key,currentNode.leftChild)
        else:
            return self._get(key,currentNode.rightChild)

    def __getitem__(self,key):
        return self.get(key)

    def __contains__(self,key):
        if self._get(key,self.root):
            return True
        else:
            return False

    def delete(self,key):
        if self.size > 1:
            nodeToRemove = self._get(key,self.root)
        if nodeToRemove:
            self.remove(nodeToRemove)
            self.size = self.size-1
        else:
             raise KeyError('Error, key not in tree')
        if self.size == 1 and self.root.key == key:
            self.root = None
            self.size = self.size - 1
        else:
            raise KeyError('Error, key not in tree')

    def __delitem__(self,key):
        return self.delete(key)

    def spliceOut(self):
        if self.isLeaf():
            if self.isLeftChild():
                 self.parent.leftChild = None
            else:
                 self.parent.rightChild = None
        elif self.hasAnyChildren():
            if self.hasLeftChild():
                if self.isLeftChild():
                    self.parent.leftChild = self.leftChild
                else:
                    self.parent.rightChild = self.leftChild
                    self.leftChild.parent = self.parent
            else:
                if self.isLeftChild():
                     self.parent.leftChild = self.rightChild
                else:
                    self.parent.rightChild = self.rightChild
                    self.rightChild.parent = self.parent

    def findSuccessor(self):
        succ = None
        if self.hasRightChild():
            succ = self.rightChild.findMin()
        else:
            if self.parent:
                if self.isLeftChild():
                     succ = self.parent
                else:
                    self.parent.rightChild = None
                    succ = self.parent.findSuccessor()
                    self.parent.rightChild = self
        return succ

    def findMin(self):
        current = self
        while current.hasLeftChild():
            current = current.leftChild
        return current

    def remove(self, currentNode):
        if currentNode.isLeaf(): #leaf
            if currentNode == currentNode.parent.leftChild:
                currentNode.parent.leftChild = None
            else:
                currentNode.parent.rightChild = None
        elif currentNode.hasBothChildren(): #interior
            succ = currentNode.findSuccessor()
            succ.spliceOut()
            currentNode.key = succ.key
            currentNode.payload = succ.payload

        else: # this node has one child
            if currentNode.hasLeftChild():
                if currentNode.isLeftChild():
                    currentNode.leftChild.parent = currentNode.parent
                    currentNode.parent.leftChild = currentNode.leftChild
                elif currentNode.isRightChild():
                    currentNode.leftChild.parent = currentNode.parent
                    currentNode.parent.rightChild = currentNode.leftChild
                else:
                    currentNode.replaceNodeData(currentNode.leftChild.key,
                                            currentNode.leftChild.payload,
                                            currentNode.leftChild.leftChild,
                                            currentNode.leftChild.rightChild)
            else:
                if currentNode.isLeftChild():
                    currentNode.rightChild.parent = currentNode.parent
                    currentNode.parent.leftChild = currentNode.rightChild
                elif currentNode.isRightChild():
                    currentNode.rightChild.parent = currentNode.parent
                    currentNode.parent.rightChild = currentNode.rightChild
                else:
                    currentNode.replaceNodeData(currentNode.rightChild.key,
                                                currentNode.rightChild.payload,
                                                currentNode.rightChild.leftChild,
                                                currentNode.rightChild.rightChild)

1.4.7 二叉查找樹分析

如果按照隨機順序添加鍵讥蔽,樹的高度將在 log2^n,n 為樹種的節(jié)點樹人乓。二叉查找樹的最差情況是 O(n)勤篮。

1.4.8 平衡二叉搜索樹 ( AVL樹 )

1.4.9 一些概念

平衡二叉搜索樹,又叫 AVL 樹色罚,能夠自動確保樹的平衡碰缔,從而保持性能穩(wěn)定在 O(logN)。
平衡因子戳护,定義為左子樹高度和右子樹的高度差金抡。如果平衡因子大于零,子樹是左重的腌且。如果平衡因子小于零梗肝,子樹是右重的。如果平衡因子等于零铺董,那么樹就是完美平衡的巫击。
如果平衡因子是`-1`、`0`或者`1`精续,那么樹稱之為平衡坝锰。

1.4.10 代碼實現(xiàn)

class AVLTree(BinarySearchTree):
    def _put(self, key, val, currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key, val, currentNode.LeftChild)
            else:
                currentNode.leftChild = TreeNode(key, val, parent=currentNode)
                self.updateBalance(currentNode.leftChild)
        else:
            if currentNode.hasRightChild():
                self._put(key, val, currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key, val, parent=currentNode)
                self.updateBalance(currentNode.rightChild) 
                
    def updateBalance(self, node):
        if node.balanceFactor > 1 or node.balanceFactor < -1:
            self.rebalance(node)
            return 
        if node.parent != None:
            if node.isLeftChild():
                node.parent.balanceFactor += 1
            elif node.isRightChild():
                node.parent.balanceFactor -= 1
        if node.parent.balanceFactor != 0:
            self.updateBalance(node.parent)
            
        
    def rotateLeft(self, rotRoot):
        pass
    
    def rotateRight(self, rotRoot):
        pass
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市重付,隨后出現(xiàn)的幾起案子顷级,更是在濱河造成了極大的恐慌,老刑警劉巖确垫,帶你破解...
    沈念sama閱讀 223,126評論 6 520
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件弓颈,死亡現(xiàn)場離奇詭異帽芽,居然都是意外死亡,警方通過查閱死者的電腦和手機翔冀,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,421評論 3 400
  • 文/潘曉璐 我一進店門导街,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人橘蜜,你說我怎么就攤上這事菊匿。” “怎么了计福?”我有些...
    開封第一講書人閱讀 169,941評論 0 366
  • 文/不壞的土叔 我叫張陵跌捆,是天一觀的道長。 經(jīng)常有香客問我象颖,道長佩厚,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,294評論 1 300
  • 正文 為了忘掉前任说订,我火速辦了婚禮抄瓦,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘陶冷。我一直安慰自己钙姊,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,295評論 6 398
  • 文/花漫 我一把揭開白布埂伦。 她就那樣靜靜地躺著煞额,像睡著了一般。 火紅的嫁衣襯著肌膚如雪沾谜。 梳的紋絲不亂的頭發(fā)上膊毁,一...
    開封第一講書人閱讀 52,874評論 1 314
  • 那天,我揣著相機與錄音基跑,去河邊找鬼婚温。 笑死,一個胖子當(dāng)著我的面吹牛媳否,可吹牛的內(nèi)容都是我干的栅螟。 我是一名探鬼主播,決...
    沈念sama閱讀 41,285評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼篱竭,長吁一口氣:“原來是場噩夢啊……” “哼力图!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起室抽,我...
    開封第一講書人閱讀 40,249評論 0 277
  • 序言:老撾萬榮一對情侶失蹤搪哪,失蹤者是張志新(化名)和其女友劉穎靡努,沒想到半個月后坪圾,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體晓折,經(jīng)...
    沈念sama閱讀 46,760評論 1 321
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,840評論 3 343
  • 正文 我和宋清朗相戀三年兽泄,在試婚紗的時候發(fā)現(xiàn)自己被綠了漓概。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,973評論 1 354
  • 序言:一個原本活蹦亂跳的男人離奇死亡病梢,死狀恐怖胃珍,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情蜓陌,我是刑警寧澤觅彰,帶...
    沈念sama閱讀 36,631評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站钮热,受9級特大地震影響填抬,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜隧期,卻給世界環(huán)境...
    茶點故事閱讀 42,315評論 3 336
  • 文/蒙蒙 一飒责、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧仆潮,春花似錦宏蛉、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,797評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至蚌讼,卻和暖如春辟灰,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背篡石。 一陣腳步聲響...
    開封第一講書人閱讀 33,926評論 1 275
  • 我被黑心中介騙來泰國打工芥喇, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人凰萨。 一個月前我還...
    沈念sama閱讀 49,431評論 3 379
  • 正文 我出身青樓继控,卻偏偏與公主長得像,于是被迫代替她去往敵國和親胖眷。 傳聞我的和親對象是個殘疾皇子武通,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,982評論 2 361

推薦閱讀更多精彩內(nèi)容