Python數(shù)據(jù)結(jié)構(gòu)樹與算法分析

更新時(shí)間：2022年07月18日 14:34:05 作者：Ding?Jiaxiong

這篇文章主要介紹了Python數(shù)據(jù)結(jié)構(gòu)樹與算法分析，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下

1.示例

樹的一些屬性：

層次性：樹是按層級(jí)構(gòu)建的，越籠統(tǒng)就越靠近頂部，越具體則越靠近底部。
一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)都與另一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)無關(guān)。
葉子節(jié)點(diǎn)都是獨(dú)一無二的。
嵌套

2.術(shù)語及定義

節(jié)點(diǎn)：樹的基礎(chǔ)部分。節(jié)點(diǎn)的名字 → 鍵，附加信息 → 有效載荷。
邊：兩個(gè)節(jié)點(diǎn)通過一條邊相連，表示它們之間存在關(guān)系。除了根節(jié)點(diǎn)，其他每個(gè)結(jié)點(diǎn)都僅有一條入邊，出邊則可能有多條。
根節(jié)點(diǎn)：樹中唯一沒有入邊的結(jié)點(diǎn)。
路徑：由邊連接的有序節(jié)點(diǎn)列表。
子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)通過出邊與子節(jié)點(diǎn)相連。
父節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)是其所有子節(jié)點(diǎn)的父節(jié)點(diǎn)。
兄弟節(jié)點(diǎn)：具有同一父節(jié)點(diǎn)的結(jié)點(diǎn) → 互稱兄弟節(jié)點(diǎn)。
子樹：一個(gè)父節(jié)點(diǎn)及其所有后代的節(jié)點(diǎn)和邊構(gòu)成一棵子樹。
葉子結(jié)點(diǎn)：葉子節(jié)點(diǎn)沒有子節(jié)點(diǎn)。
層數(shù)：節(jié)點(diǎn)n的層數(shù)是從根節(jié)點(diǎn)到n的唯一路徑長(zhǎng)度。根節(jié)點(diǎn)的層數(shù)為0。
高度：樹的高度是其中節(jié)點(diǎn)層數(shù)的最大值。

1.定義一：樹由節(jié)點(diǎn)及連接節(jié)點(diǎn)的邊構(gòu)成。

樹的屬性：

有一個(gè)根節(jié)點(diǎn)除根節(jié)點(diǎn)外，其他每個(gè)節(jié)點(diǎn)都與其唯一的父節(jié)點(diǎn)相連。
從根節(jié)點(diǎn)到其他每個(gè)節(jié)點(diǎn)有且僅有一條路徑。
如果每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn) → 二叉樹。

2.定義二：一棵樹要么為空，要么由一個(gè)根節(jié)點(diǎn)和零棵或多棵子樹構(gòu)成，子樹本身也是一棵樹。

每棵子樹的根節(jié)點(diǎn)通過一條邊連到父樹的根節(jié)點(diǎn)。

3.實(shí)現(xiàn)

3.1 列表之列表

在這里插入圖片描述

樹的根節(jié)點(diǎn)是myTree[0]，左子樹是myTree[1]，右子樹是myTree[2]。

# 列表函數(shù)
def BinaryTree(r):
    return [r,[],[]] # 根節(jié)點(diǎn)r，和兩個(gè)作為子節(jié)點(diǎn)的空列表
# 插入左子樹
def insertLeft(root,newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])
    else:
        root.insert(1,[newBranch,[],[]])
    return root

## 插入右子樹
def insertRight(root , newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2,[newBranch,[],t])
    else:
        root.insert(2,[newBranch,[],[]])
    return root
### 樹的訪問函數(shù)
def getRootVal(root):
    return root[0]
def setRootVal(root,newVal):
    root[0] = newVal
def getLeftChild(root):
    return root[1]
def getRightChild(root):
    return root[2]
r = BinaryTree(3)
insertLeft(r,4)
print(r)

3.2節(jié)點(diǎn)與引用

定義一個(gè)類，其中有根節(jié)點(diǎn)和左右子樹的屬性。

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    ## 插入左子節(jié)點(diǎn)
    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.left = self.leftChild
            self.leftChild = t
    ## 插入右子節(jié)點(diǎn)
    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.right = self.rightChild
            self.rightChild = t
    ## 訪問函數(shù)
    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

4.二叉樹的應(yīng)用

4.1解析樹

根據(jù)完全括號(hào)表達(dá)式構(gòu)建解析樹
如何計(jì)算解析樹中的表達(dá)式
如何將解析樹還原成最初的數(shù)學(xué)表達(dá)式

解析樹構(gòu)建器：

import operator

from pythonds.basic import Stack
from pythonds.trees import BinaryTree
def buildParseTree(fpexp):
    fplist = fpexp.split()
    pStack = Stack()
    eTree = BinaryTree("")
    pStack.push(eTree)
    currentTree = eTree

    for i in fplist:
        if i == "(":
            currentTree.insertLeft("")
            pStack.push(currentTree)
            currentTree = currentTree.getLeftChild()

        elif i not in "+-*/)":
            currentTree.setRootVal(eval(i))
            parent = pStack.pop()
            currentTree = parent
        elif i in "+-*/":
            currentTree.setRootVal(i)
            currentTree.insertRight("")
            currentTree = currentTree.getRightChild()
        elif i == ")":
            currentTree = pStack.pop()
        else:
            raise ValueError("Unkown Operator :" + i )
    return eTree

## 計(jì)算二叉解析樹的遞歸函數(shù)
def evaluate(parseTree):
    opers = {
        "+":operator.add,"-":operator.sub,
        "*":operator.mul,"/":operator.truediv
    }
    
    leftC = parseTree.getLeftChild()
    rightC = parseTree.getRightChild()
    
    if leftC and rightC:
        fn = opers[parseTree.getRootVal()]
        return fn(evaluate(leftC),evaluate(rightC))
    else:
        return parseTree.getRootVal()

4.2樹的遍歷

前序遍歷【根左右】
中序遍歷【左根右】
后序遍歷【左右根】

前序遍歷算法實(shí)現(xiàn)為外部函數(shù)：

def preorder(tree):
    if tree:
        print(tree.getRootVal())
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild)

前序遍歷算法實(shí)現(xiàn)為BinaryTree類的方法

def preorder(self):
    print(self.key)
    if self.leftChild:
        self.leftChild.preorder()
    if self.rightChild:
        self.rightChild.preorder()

后序遍歷函數(shù)

def postorder(tree):
    if tree != None:
        postorder(tree.getLeftChild())
        postorder(tree.getRightChild())
        print(tree.getRootVal())

中序遍歷函數(shù)

def inorder(tree):
    if tree != None:
        inorder(tree.getLeftChild())
        print(tree.getRootVal())
        inorder(tree.getRightChild())

5.利用二叉堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列

隊(duì)列一個(gè)重要的變體 → 優(yōu)先級(jí)隊(duì)列。和隊(duì)列一樣，優(yōu)先級(jí)隊(duì)列從頭部移除元素，不過元素的邏輯順序是由優(yōu)先級(jí)決定的，優(yōu)先級(jí)最高的元素在最前，最低的元素在最后。

實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的經(jīng)典方法 → 二叉堆。入隊(duì)和出隊(duì)操作均可達(dá)到O(logn)

最小堆【最小的元素一直在隊(duì)首】
最大堆【最大的元素一直在隊(duì)首】 6.6.2 二叉堆的實(shí)現(xiàn)

結(jié)構(gòu)屬性：

完全二叉樹：除了最底層，其他每一層的節(jié)點(diǎn)都是滿的。且在最底層，從左往右填充節(jié)點(diǎn)。
完全二叉樹可以用一個(gè)列表直接表示。

堆的有序性：對(duì)于堆中任意元素x及其父元素p，p都不大于x。

堆操作

代碼實(shí)現(xiàn)：

class EchaDui:
    # 新建二叉堆
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0
    
    def percUp(self,i):
        while i // 2 > 0:
            if self.heapList[i] < self.heapList[i // 2]:
                tmp = self.heapList[i // 2]
                self.heapList[i // 2] = self.heapList[i]
                self.heapList[i] = tmp
                
            i = i // 2
    # 新加元素
    def insert(self,k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)
        
    def percDown(self,i):
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i = mc
    def minChild(self,i):
        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 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
        
    ## 根據(jù)元素列表構(gòu)建堆
    def builgHeap(self,alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.percDown(i)
            i = i - 1

6.二叉搜索樹

6.1搜索樹的實(shí)現(xiàn)

二叉搜索樹依賴性質(zhì)：小于父節(jié)點(diǎn)的鍵都在左子樹中，大于父節(jié)點(diǎn)的鍵則都在右子樹。

代碼實(shí)現(xiàn)：

class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0
    def length(self):
        return self.size
    def __len__(self):
        return self.size
    def __iter__(self):
        return self.root.__iter__()
    # 插入新節(jié)點(diǎn)
    def put(self,key,val):
        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, key, value):
        self._put(key,value)

    ## 查找鍵對(duì)應(yīng)的值
    def get(self,key):
        if self.root:
            res = self._get(key,self.root)
            if res:
                return res.payload
            else:
                return None
        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)

    # 檢查樹中是否有某個(gè)鍵
    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")
        elif 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):
        self.delete(key)

    """
        1. 待刪除節(jié)點(diǎn)沒有子節(jié)點(diǎn)
        2. 待刪除節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)
        3. 待刪除節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
    """
    # 尋找后繼結(jié)點(diǎn)
    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 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 remove(self,currentNode):
        if currentNode.isLeaf():
            if currentNode == currentNode.parent.leftChild:
                currentNode.parent.leftChild = None
            else:
                currentNode.parent.rightChild = None
        elif currentNode.hasBothChildren():
            succ = currentNode.findSuccessor()
            succ.spliceOut()
            currentNode.key = succ.key
            currentNode.payload = succ.payload
        else:
            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                            
                                                )
    # 二叉搜索樹迭代器
    def __iter__(self):
        if self:
            if self.hasLeftChild():
                for elem in self.leftChild:
                    yield elem
            yield self.key
            if self.hasRightChild():
                for elem in self.rightChild:
                    yield elem

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 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

7.平衡二叉搜索樹（AVL樹）

實(shí)現(xiàn)AVL樹時(shí)，要記錄每個(gè)節(jié)點(diǎn)的平衡因子。

平衡因子 = 左右子樹的高度之差

→ 保證樹的平衡因子為-1，0,1，可以使得關(guān)鍵操作獲得更好的大O性能

#from 第6章樹.二叉搜索樹 import TreeNode
def _put(self, key, val, currentNode):
    if key < currentNode.key:
        if currentNode.hasLeftchi1d():
            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)
# 實(shí)現(xiàn)左旋
def rotateLeft (self, rotRoot) :
    newRoot = rotRoot .rightchild
    rotRoot .rightChild = newRoot.leftChild
    if newRoot . leftChild !=None :
        newRoot . leftChild. parent = rotRoot
    newRoot.parent =rotRoot.parent
    if rotRoot .isRoot( ):
        self.root = newRoot
    else:
        if rotRoot .isLeftChild():
            rotRoot.parent .leftChild = newRoot
        else:
            rotRoot.parent .rightChild = newRoot
    newRoot . leftChild = rotRoot
    rotRoot.parent = newRoot
    rotRoot. balanceFactor = rotRoot . balanceFactor + 1 - min(newRoot . balanceFactor,0)
    newRoot . balanceFactor = newRoot . balanceFactor + 1 +max(rotRoot . balanceFactor,o )

# 實(shí)現(xiàn)再平衡
def rebalance(self, node) :
    if node. balanceFactor < 0:
        if node .rightChild .balanceFactor > 0:
            self.rotateRight (node.rightChild)self.rotateLeft (node)
        else:
            self.rotateLeft (node)
    elif node. balanceFactor > 0 :
        if node . leftChild. balanceFactor < 0:
            self.rotateLeft (node. leftChild)
            self.rotateRight (node)
        else:
            self.rotateRight (node)
nceFactor + 1 - min(newRoot . balanceFactor,0)
    newRoot . balanceFactor = newRoot . balanceFactor + 1 +max(rotRoot . balanceFactor,o )
# 實(shí)現(xiàn)再平衡
def rebalance(self, node) :
    if node. balanceFactor < 0:
        if node .rightChild .balanceFactor > 0:
            self.rotateRight (node.rightChild)self.rotateLeft (node)
        else:
            self.rotateLeft (node)
    elif node. balanceFactor > 0 :
        if node . leftChild. balanceFactor < 0:
            self.rotateLeft (node. leftChild)
            self.rotateRight (node)
        else:
            self.rotateRight (node)

到此這篇關(guān)于Python數(shù)據(jù)結(jié)構(gòu)樹與算法分析的文章就介紹到這了,更多相關(guān)Python數(shù)據(jù)結(jié)構(gòu)樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: