一. 二叉樹構(gòu)建以及遍歷

1.構(gòu)建結(jié)點

二叉樹的結(jié)點Node有數(shù)據(jù)域滴肿，左孩子和右孩子三部分属百。

class Node(object):
    def __init__(self,item):
        self.elem = item
        self.lchild = None
        self.rchild = None    

2.利用上面的結(jié)點構(gòu)建一個樹類

class Tree(object):
    def __init__(self):
        self.root = None

樹添加結(jié)點的方法

def add(self,item):
    """
        param: item 是傳進(jìn)來來的數(shù)據(jù),我們要實例化一個結(jié)點取接收他,但是他的位置要放在樹梢,不能亂插入
               queue 我們創(chuàng)建一個隊列來接收和彈出結(jié)點,這樣我們找到結(jié)點需要接收的位置
    """
    node = Node(item)
    if self.root is None：
        """如果根結(jié)點是None,是一顆空數(shù),我們就把node賦值給root,那么下面的while循環(huán)是不會受影響的,因為是隊列[None]的bool值是True"""
        self.root = node
        return
    #把要遍歷的結(jié)點加入queue隊列中
    queue = [self.root]
    while queue:
        #隊列的彈出要加0酥夭，與棧相仿
        cur_node = queue.pop(0)
        if cur_node.lchild is None:
            #這里有空位，插入結(jié)點
            cur_node.lchild = node
        else:
            #cur_node的做孩子放進(jìn)隊列中，下次循環(huán)左子結(jié)點
            queue.append(cur_node.lchild)
        #同理對于右邊的操作
        if cur_node.rchild is None:
            cur_node.rchild = node
        else:
            queue.append(cur_node.rchild)

廣度遍歷 —— 層序遍歷

遞歸版

def levelOrder(self,root):
    def helper(node,level):
        if not node:
            return 
        else:
            sol[level-1].append(node.val)
            if len(sol) == level: #遍歷到新層時爹耗，只有最左邊的結(jié)點使得等式成立
                sol.append([])
            helper(node.lchild,level+1)
            helper(node.rchild,level+1)
    sol = [[]]
    helper(root,1)
    return sol[:-1]

循環(huán)版

def breadth_travel(self):
        """廣度遍歷與結(jié)點的添加非常相似,廣度遍歷不用插入結(jié)點了,在循環(huán)里面的條件和添加的相仿"""
        if self.root is None:
            return 
        queue = [self.root]
 
        while queue:
            cur_node = queue.pop(0)
            # 我們打印看看結(jié)點的遍歷順序?qū)Σ粚?            print(cur_node.elem)
            if cur_node.lchild is not None:
                # 扔進(jìn)隊列循環(huán)
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

深度遍歷：前序奔滑，中序艾岂，后序

遞歸版

#先序遍歷 根左右
def preOrder(self,node):
    if self.root is None:
        return 
    print(node.elem)
    self.preOrder(node.lchild)
    self.preOrder(node.rchild)

#中序遍歷  左根右
def middleOrder(self,node):
    if self.root is None:
        return 
    self.preOrder(node.lchild)
    print(node.elem)
    self.preOrder(node.rchild)

#后序遍歷  左右根
def lastOrder(self,node):
    if self.root is None:
        return 
    self.preOrder(node.lchild)
    self.preOrder(node.rchild)
    print(node.elem)

循環(huán)版 —— 使用棧遍歷二叉樹

    def front(self):
        """堆棧前序遍歷"""
        if not self.root:
            return
        tmp_stack = []
        node = self.root
        while tmp_stack or node:
            while node:
                print(node.data)
                tmp_stack.append(node)
                node = node.left_child
            node = tmp_stack.pop()
            node = node.right_child

    def middle(self):
        """堆棧中序遍歷"""
        if not self.root:
            return
        tmp_stack = []
        node = self.root
        while tmp_stack or node:
            while node:
                tmp_stack.append(node)
                node = node.left_child
            node = tmp_stack.pop()
            print(node.data)
            node = node.right_child

    def last(self):
        """堆棧后序遍歷，較難"""
        if not self.root:
            return
        tmp_node = self.root
        tmp_stack = []
        while tmp_node or tmp_stack:
            while tmp_node:
                tmp_stack.append(tmp_node)
                tmp_node = tmp_node.left_child or tmp_node.right_child
            tmp_node = tmp_stack.pop()
            print(tmp_node.data)
            if tmp_stack and tmp_stack[-1].left_child is tmp_node:
                tmp_node = tmp_stack[-1].right_child
            else:
                tmp_node = None

    def lastSimpleV(self,root):
        stack = []
        sol = [] #保存打印輸出結(jié)果的列表
        curr = root
        while stack or curr:
            if curr:
                sol.append(curr.data)
                stack.append(curr.left_child)
                curr = curr.right_child
            else:
                curr = stack.pop()
        return sol[::-1]  #反向打印結(jié)果

二 鏈表的創(chuàng)建及相關(guān)操作

1.定義一個單鏈表結(jié)點類

class Node(object):
    def __init__(self,data):
        self.data = data
        self.next = None

2.方法

#判斷是否為空
def isEmpty(self):
    return (self.length ==0)

#增加一個結(jié)點,增加之后 要把鏈表長度加一
def append(self,dataOrNode):
    item = None
    if isinstance(dataOrNode,Node):
        #如果是結(jié)點的話
        item = dataOrNode
    else:
        item = Node(dataNode)
     if not self.head:  
        #如果頭結(jié)點為空的話直接插入
        self.head = item
        self.length += 1
    else:
        node = self.head
        while node.next:
            node = node.next
        node.next = item
        self.length += 1

#刪除一個結(jié)點,刪除結(jié)點之后要把鏈表長度減
def delete(self,index):
    if self.isEmpty():
        print("this chain table is empty")
        return 
    if index<0 or index>=self.length:
        print("error:out of index")
        return
#刪除第一個結(jié)點
if index==0:
        self.head = self.head.next
        self.length -= 1
        return
#prev為保存前驅(qū)結(jié)點
#node為保存當(dāng)前結(jié)點
#當(dāng)j與index相等時就朋其，相當(dāng)于找到要刪除的節(jié)點
j = 0
node = self.head
prev = self.head
while node.next and j<index:
    prev = node
    node = node.next
    j+=1
if j==index:
    prev.next = node.next
    self.length -= 1

#更新結(jié)點值
def update(self,index,data):
    if self.isEmpty() or index <0 or index>=self.length:
        return 
    j = 0
    node = self.head
    while node.next and j<index:
        node = node.next
        j += 1
    if j == index:
        node.data = data

三 圖的創(chuàng)建以及深度廣度遍歷