一、python实现链表，并实现链表的增删改查

1、python中没有现成的这种数据类型，所以我们需要实现一个Node类来定义这种数据结构
2、定义SinCycLinkedlist作为链表的构造类，可以实现链表的增删改查；

#!/usr/bin/env python
# -*- coding: utf-8 -*-

class Node:
    def __init__(self, initdata):
        self.__data = initdata
        self.__next = None

    def getData(self):
        return self.__data

    def getNext(self):
        return self.__next

    def setData(self, newdata):
        self.__data = newdata

    def setNext(self, newnext):
        self.__next = newnext

class SinCycLinkedlist:
    def __init__(self):
        self.head = Node(None)
        self.head.setNext(self.head)

    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head.getNext())
        self.head.setNext(temp)

    def remove(self, item):
        prev = self.head
        while prev.getNext() != self.head:
            cur = prev.getNext()
            if cur.getData() == item:
                prev.setNext(cur.getNext())
            prev = prev.getNext()

    def search(self, item):
        cur = self.head.getNext()
        while cur != self.head:
            if cur.getData() == item:
                return True
            cur = cur.getNext()

        return False

    def empty(self):
        return self.head.getNext() == self.head

    def size(self):
        count = 0
        cur = self.head.getNext()
        while cur != self.head:
            count += 1
            cur = cur.getNext()

        return count

if __name__ == '__main__':
    s = SinCycLinkedlist()
    print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))

    s.add(19)
    s.add(86)
    print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))

    print('86 is%s in s' % ('' if s.search(86) else ' not',))
    print('4 is%s in s' % ('' if s.search(4) else ' not',))
    print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))

    s.remove(19)
    print('s.empty() == %s, s.size() == %s' % (s.empty(), s.size()))

二、python实现二叉查找树

二叉查找树的相关性质：
1、若左子树不空，则左子树上所有结点的值均小于等于它的根结点的值；
2、若右子树不空，则右子树上所有结点的值均大于等于它的根结点的值；

class Node:
    def __init__(self, data):
        self.data = data
        self.lchild = None #左子树
        self.rchild = None #右子树

3、二叉树的查找

首先将给定值与根结点的关键字比较，若相等则查找成功
若小于根结点关键字值，递归查左子树
若大于根结点值，递归查右子树
若子树为空，查找失败

4、二叉树的插入

1）、一定是树中存在的节点
2）、一定是一个新添加的叶子节点
3）、一定是查找这个要插入节点时，查找路径上访问的最后一个结点的，左子结点或者右子结点

5、二叉树的删除

1）、待删除的是叶子结点，直接删除
2）、待删除结点有一个子节点，用删除链表结点的方法删除；
3）、待删除结点有两个子节点，将右侧子树最小数据点作为这个结点，然后把右侧子树的最小数据点删除；

6、实现代码

# encoding: utf-8
class Node:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

class BST:
    def __init__(self, node_list):
        self.root = Node(node_list[0])
        for data in node_list[1:]:
            self.insert(data)

    # 搜索
    def search(self, node, parent, data):
        if node is None:
            return False, node, parent
        if node.data == data:
            return True, node, parent
        if node.data > data:
            return self.search(node.lchild, node, data)
        else:
            return self.search(node.rchild, node, data)

    # 插入
    def insert(self, data):
        flag, n, p = self.search(self.root, self.root, data)
        if not flag:
            new_node = Node(data)
            if data > p.data:
                p.rchild = new_node
            else:
                p.lchild = new_node

    # 删除
    def delete(self, root, data):
        flag, n, p = self.search(root, root, data)
        if flag is False:
            print ("无该关键字，删除失败")
        else:
            if n.lchild is None:
                if n == p.lchild:
                    p.lchild = n.rchild
                else:
                    p.rchild = n.rchild
                del p
            elif n.rchild is None:
                if n == p.lchild:
                    p.lchild = n.lchild
                else:
                    p.rchild = n.lchild
                del p
            else:  # 左右子树均不为空
                pre = n.rchild
                if pre.lchild is None:
                    n.data = pre.data
                    n.rchild = pre.rchild
                    del pre
                else:
                    next = pre.lchild
                    while next.lchild is not None:
                        pre = next
                        next = next.lchild
                    n.data = next.data
                    pre.lchild = next.rchild
                    del p


    # 先序遍历
    def preOrderTraverse(self, node):
        if node is not None:
            print(node.data)
            self.preOrderTraverse(node.lchild)
            self.preOrderTraverse(node.rchild)

    # 中序遍历
    def inOrderTraverse(self, node):
        if node is not None:
            self.inOrderTraverse(node.lchild)
            print(node.data)
            self.inOrderTraverse(node.rchild)

    # 后序遍历
    def postOrderTraverse(self, node):
        if node is not None:
            self.postOrderTraverse(node.lchild)
            self.postOrderTraverse(node.rchild)
            print (node.data)

a = [49, 38, 65, 97, 60, 76, 13, 27, 5, 1]
bst = BST(a)  # 创建二叉查找树
bst.inOrderTraverse(bst.root)  # 中序遍历

bst.delete(bst.root, 49)
bst.inOrderTraverse(bst.root)

三、python图论

1、图的表示方法：
     1）、邻接矩阵：设矩阵为A，那Aij就表示第i个节点和第j个节点是否相连，为1表示相连，0表示不相连；
     2）、邻接表：第一列表示有哪些元素(第一列即是一个不重复元素列表)，每一行表示有哪些节点与其相连；
2、图的两种表示方法解析：
     1）、邻接矩阵 ：适用于密集图

     2）、邻接表：节省空间，适用于稀疏图

     3）、当图用邻接表表示之后（python中的邻接表其实就是一个字典）

     4）、可以用find_path方法，递归的找到任意一条从图中一个节点到另一个节点的路径；

     5）、find_path_all可以找到所有的一个节点到另一个节点的路径；

3、上一个截图

4、实例

#图的邻接链表表示法
graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C','G','H'],
         'E': ['F'],
         'F': ['C']}

#从图中找出任意一条从起始顶点到终止顶点的路径
def find_path(graph, start, end, path=[]):
    if start == end:
        print("path", path)
        return True
    if not graph.get(start):
        path.pop()
        return False
    for v in graph[start]:
        if v not in path:
            path.append(v)
            #递归查找，下次的start是v，终点end不变
            if find_path(graph,v,end,path):
                return True
    return False

path = []
if find_path(graph, 'A', 'C', path=path):
    print(path)
else:
    print(1)


#从图中找出从起始顶点到终止顶点的所有路径
import copy
# copy是python的标准模块，有浅拷贝的深拷贝
# 浅拷贝：也就是说仅拷贝父对象，不会拷贝对象的内部的子对象。即浅复制只复制对象本身，没有复制该对象所引用的对象
# 深拷贝：深拷贝完全拷贝了父对象及其子对象。即创建一个新的组合对象，同时递归地拷贝所有子对象，新的组合对象与原对象没有任何关联

def find_path_all(curr, end, path):
    '''
    :param curr: 当前顶点
    :param end: 要到达的顶点
    :param path: 当前顶点的一条父路径
    :return:
    '''
    if curr == end:
        path_tmp = copy.deepcopy(path)
        path_all.append(path_tmp)
        return
    if not graph.get(curr):
        return
    for v in graph[curr]:
        #一个顶点在当前递归路径中只能出现一次，否则会陷入死循环。
        if v in path:
            print("v %s in path %s" %(v, path))
            continue
        #构造下次递归的父路径
        path.append(v)
        find_path_all(v,end,path)
        path.pop()

path_all = []
find_path_all('A', 'G',path=['A'])
print(path_all)


#遍历图中所有顶点，按照遍历顺序将顶点添加到列表中
vertex = []
def dfs(v):
    if v not in graph:
        return
    for vv in graph[v]:
        if vv not in vertex:
            vertex.append(vv)
            dfs(vv)

for v in graph:
    if v not in vertex:
        vertex.append(v)
        dfs(v)
print(vertex)