一棕诵、鏈表

在 Python 中裁良，列表是動態(tài)數(shù)組。這意味著列表和鏈表的內(nèi)存使用都非常相似校套。

二价脾、棧

1.棧(stack)，有些地方稱為堆棧笛匙，是一種容器侨把，可存入數(shù)據(jù)元素犀变、訪問元素、刪除元素

2.特點：只能允許在容器的一端(稱為棧頂端指標—— top) 進行加入數(shù)據(jù)(push)和輸出數(shù)據(jù)(pop) 的運算秋柄。沒有了位置概念获枝，保證任何時候可以訪問、刪除的元素都是此前最后存入的那個元素骇笔，確定了一種默認的訪問順序映琳。
3.由于棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進行操作，因而按照先進后出（后進先出）的原理運作蜘拉。

• 2.1 棧結(jié)構(gòu)的實現(xiàn)
  （1）Stack()創(chuàng)建一個新的空棧
  （2）push(item)添加一個新的元素item到棧頂
  （3）pop()彈出棧頂元素
  （4）peek()返回棧頂元素
  （5）is_empty()判斷棧是否為空
  （6）size()返回棧的元素個數(shù)

• 2.2.代碼實現(xiàn)：

class Stack(object):
    #定義初始化方法
    def __init__(self):
        #初始化一個空列表
        self._list=[]
    #壓棧
    def push(self,item):
        self._list.append(item)
 
    #彈出元素
    def pop(self):
        return self._list.pop()
 
    #返回棧頂元素
    def peek(self):
        return self._list[len(self._list)-1]
 
    #判斷棧頂是否為空
    def is_empty(self):
        return self._list==[]
 
    #計算棧的大小
    def size(self):
        return len(self._list)
if __name__=="__main__":
    stack=Stack()
    print("棧是否為空：",stack.is_empty())
    #壓棧
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    print("棧是否為空：",stack.is_empty())
    print("棧的長度：",stack.size())
    #彈出
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

棧是否為空： True
棧是否為空： False
棧的長度： 4
4
3
2
1

三萨西、隊列是什么？

1.隊列(queue)是只允許在一端進行插入操作旭旭，而在另一端進行刪除操作的線性表

2.隊列是遵循先進先出的原理簡稱谎脯，允許插入的一端為隊尾，允許刪除的一端為隊頭持寄。隊列不允許在中間部位進行操作

• 3.1隊列的實現(xiàn)
  1.實現(xiàn)步驟：

（1）Queue()創(chuàng)建一個空的隊列

（2）enqueue(item)向隊列中添加元素item

（3）dequeue()從隊列頭部刪除一個元素

（4）is_empty判斷一個隊列是否為空

（5）size()返回隊列大小

• 3.2.代碼實現(xiàn)

class Queue(object):
    #定義初始化方法
    def __init__(self):
        self._list=[]
    #進隊
    def enqueue(self,item):
        #self._list.append(item)
        self._list.insert(0,item)
    #出隊
    def dequeue(self):
        #return self._list.pop()
        return self._list.pop()
    #判斷是否為空
    def is_empty(self):
        return self._list==[]
    #計算隊列大小
    def size(self):
        return len(self._list)
 
if __name__=="__main__":
    queue=Queue()
    print("隊列是否為空：",queue.is_empty())
    #進隊
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    print("隊列是否為空：", queue.is_empty())
    #出隊
    print(queue.dequeue())
    print(queue.dequeue())
    print(queue.dequeue())

隊列是否為空： True
隊列是否為空： False
1
2
3

四源梭、樹

image.png

• 結(jié)點：使用樹結(jié)構(gòu)存儲的每一個數(shù)據(jù)元素都被稱為“結(jié)點”。例如稍味，圖 1（A）中废麻，數(shù)據(jù)元素 A 就是一個結(jié)點；

• 父結(jié)點（雙親結(jié)點）模庐、子結(jié)點和兄弟結(jié)點：對于圖 1（A）中的結(jié)點 A烛愧、B、C掂碱、D 來說怜姿，A 是 B、C疼燥、D 結(jié)點的父結(jié)點（也稱為“雙親結(jié)點”）沧卢，而 B、C醉者、D 都是 A 結(jié)點的子結(jié)點（也稱“孩子結(jié)點”）但狭。對于 B、C撬即、D 來說立磁，它們都有相同的父結(jié)點，所以它們互為兄弟結(jié)點搞莺。

• 結(jié)點A就是整棵樹的根結(jié)點息罗。

• 一棵樹的度是樹內(nèi)各結(jié)點的度的最大值。圖 1（A）表示的樹中才沧，各個結(jié)點的度的最大值為 3迈喉，所以，整棵樹的度的值是 3温圆。一棵樹的度是樹內(nèi)各結(jié)點的度的最大值挨摸。圖 1（A）表示的樹中，各個結(jié)點的度的最大值為 3岁歉，所以得运，整棵樹的度的值是 3。

4.1樹的種類

• 無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關(guān)系锅移，稱為無序樹
• 有序樹：樹中任意節(jié)點的子節(jié)點之間有順序關(guān)系熔掺，稱為有序樹
  • 二叉樹：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹
  • 完全二叉樹：對于一顆二叉樹，假設(shè)其深度為d（d>1）非剃。除了第d層外置逻，其他各層的節(jié)點數(shù)目均已達到最大值，且第d層所有節(jié)點從左向右連續(xù)地緊密排列备绽，這樣的二叉樹稱為完 全二叉樹券坞，其中滿二叉樹的定義是所有葉子節(jié)點都在最底層的完全二叉樹
  • 平衡二叉樹（AVL樹）：當且僅當任何節(jié)點的兩顆子樹的高度差不大于1的二叉樹
  • B樹：一種對讀寫操作進行優(yōu)化的自平衡的二叉查找樹，能夠保持數(shù)據(jù)有序肺素，擁有多余兩個子樹

image.png

簡單地理解恨锚，滿足以下兩個條件的樹就是二叉樹：
本身是有序樹；
樹中包含的各個節(jié)點的度不能超過 2倍靡，即只能是 0猴伶、1 或者 2；

4.2 樹的實現(xiàn)

# 定義二叉樹節(jié)點
class Node(object):
    """二叉樹結(jié)點的定義"""

    def __init__(self, item):
        self.elem = item
        self.lChild = None
        self.rChild = None


class Tree(object):
    """二叉樹"""

    def __init__(self):
        self.root = None  # 根結(jié)點

    def add(self, item):
        """添加結(jié)點"""
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]  # 隊列
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lChild is None:
                cur_node.lChild = node
                return
            else:
                queue.append(cur_node.lChild)
            if cur_node.rChild is None:
                cur_node.rChild = node
                return
            else:
                queue.append(cur_node.rChild)

    def breadth_travel(self):
        """利用隊列實現(xiàn)樹的層次遍歷（廣度遍歷）"""
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem, end=" ")
            if cur_node.lChild is not None:
                queue.append(cur_node.lChild)
            if cur_node.rChild is not None:
                queue.append(cur_node.rChild)

    def preorder(self, node):
        """前序遍歷（深度遍歷）(中 -> 左 -> 右)"""
        if node is None:
            return
        print(node.elem, end=" ")
        self.preorder(node.lChild)
        self.preorder(node.rChild)

    def inorder(self, node):
        """中序遍歷（深度遍歷）(左 -> 中 -> 右)"""
        if node is None:
            return
        self.inorder(node.lChild)
        print(node.elem, end=" ")  # 此處可認為 node.elem 就是我們要處理的結(jié)點
        self.inorder(node.rChild)

    def postorder(self, node):
        """后序遍歷（深度遍歷）(左 -> 右 -> 中)"""
        if node is None:
            return
        self.postorder(node.lChild)
        self.postorder(node.rChild)
        print(node.elem, end=" ")

if __name__ == "__main__":
    tree = Tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    print("廣度優(yōu)先遍歷")
    tree.breadth_travel()
    print("先序遍歷")
    tree.preorder(tree.root)
    print("中序遍歷")
    tree.inorder(tree.root)
    print("后序遍歷")
    tree.postorder(tree.root)

image.png