Python|快速掌握单双链表和树
前言：
单双链表、树、二叉树等数据结构的代码实现都存在相似之处，本文将从单链表入手，轻松掌握单双链表、树、二叉树的代码实现。友情提示：请提前了解什么是链表和树。
具体内容
1.单链表
单链表由一个个节点连接而成每个节点包含两部分信息：值(val)、下一个节点(next)。
图一单链表示意图
在接触单链表时，书上说的是节点1指向节点2，也就是next指向下一个节点。在代码实现的时候“next指向下一个节点”就等同于“next”就是下一个节点。
一个节点由两部分组成：值(val)、下一个节点(next)。下一个节点(next)也由两部分组成：val和next。层层嵌套，就形成了一个单链表。
图二单链表结构图
理解这些后，实现单链表的代码就很简单。
class Node(): def __init__(self,val): self.elem=val self.next=None #定义单链表link,第一个节点的值是10link=Node(10)#第一个节点的下一个节点是节点20link.next=Node(20)#第二个节点的下一个节点是30link.next.next=Node(30)#打印第一个节点的值print(link.elem)#返回10#打印第二个节点的值print(link.next.elem) #返回20#打印第三个节点的值print(link.next.next.elem) #返回30 |
|---|
根据上方的代码，用节点类Node实现了一个单链表，但是很明显，这个单链表的操作看起来有点蠢，当需要添加新节点时，还需要知道链表中有多少个节点，节点一多就需要手敲很多个next。
所以需要另一个类，来实现在添加节点时直接添加，而不用去管之前有多少节点。这个类如果还能实现遍历节点之类的操作就更好了。
节点添加：尾插法
#节点类class Node(): def __init__(self,val): self.elem=val #next初始化为空 self.next=None#定义一个空链表类class SigleLink():def __init__(self,node=None): #单链表必须从头部访问，空链表需要记录头部，初始化为空 self.__head=node |
|---|
尾插法，顾名思义，在单链表的尾部添加元素，如果链表为空，令头部__head等于新加入节点即可。链表不为空，令最后一个节点的next等于新加入的节点，就完成了新节点的插入，由于单链表只能从头部开始操作，所以需要先从头部遍历到最后一个节点。
#从尾部插入元素def add_tail(self,val): #用户只需传入节点值，由函数自带处理成节点 node=Node(val) #分别处理链表为空和不为空的情况 if self.__head==None: #头部为空，链表为空 self.__head=node else: #需要对最后一个节点进行操作，需要先遍历到最后一个节点 cur=self.__head #从头节点开始遍历,cur记录当前操作的节点 while cur.next!=None: #当前节点的next不为空，就将cur移向下一个节点 cur=cur.next cur.next=node |
|---|
在尾插法的实现中已经包含了节点的遍历，还要再实现从头部插入节点，以及从任意位置插入节点的代码也就很简单了。
#链表节点遍历 def travel(self): cur=self.__head while cur!=None: print(cur.elem,end=' ') cur=cur.next print('')#换行 |
|---|
节点添加：头插法
在链表头部插入新节点(node)，令node.next等于原来的头节点，将node标识为新的头节点即可。
#头插法 def add_top(self,val): node=Node(val) node.next=self.__head self.__head=node |
|---|
节点添加：任意位置插入节点
在下标为pos处插入新节点node，通过遍历找出第pos-1个节点，令node.next等于第pos-1的节点的next，再令第pos-1的节点的next等于node即可.
#获取链表的长度 def length(self): #cur游标，表示当前操作的节点 cur=self.__head #统计有多少节点 count=0 while cur!=None: count+=1 #将cur替换为下一个节点 cur=cur.next return countdef insert(self,pos,val): #输入的位置<0，调用头插法 if pos<=0: self.add_top(val) #输入的位置>节点个数，调用头插法 elif pos>self.length()-1: self.add_tail(val) else: node=Node(val) cur=self.__head count=0 #表示当前节点的下标，从0开始 #遍历到第pos-1个节点时停止 while count<pos-1: count+=1 cur=cur.next node.next=cur.next cur.next=node |
|---|
2.双链表
单链表每个节点包含：值(val)、下一个节点(next)。双链表多一个信息：上一个节点(last)。只需要对节点类稍加更改即可。
#双链表节点类class Node(): def __init__(self,val): self.elem=val self.last=None self.next=None |
|---|
（1）遍历
从头部开始遍历，操作和单链表一样。从链表中的某个节点开始遍历，只需要分别向前(last)和向后(next)遍历一次即可。
（2）插入
单链表从尾部插入只需更改上一个节点的next，双链表多一步，还需要更改插入节点的last。其他插入方式，也只需要注意多出来的last即可。
3.二叉树
二叉树与双链表相比，上一个和下一个节点变为左节点和右节点
根据逻辑结构的变化，对遍历，插入等操作做相应变化即可。
#二叉树节点类class Node(): def __init__(self,val): self.elem=val self.left=None self.right=None |
|---|
4.树
树稍微麻烦一点，因为树中的某个节点有多少子节点是不确定的，所以需要将子节点(son)用列表储存。在遍历节点的时候，注意用个for循环去遍历当前节点的son即可。
#树节点类class Node(): def __init__(self,val): self.elem=val self.son=[] |
|---|
结语
单双链表、二叉树、树的代码实现都有其共同之处，在弄清楚单链表的实现后，在编写双链表、二叉树、树的代码时，多思考，举一反三，便能很快上手。
END
编 辑 | 王楠岚
责 编 | 马原涛
where2go 团队