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