Python程序设计教程第8章课件

第8章Python数据结构课程描述数据结构是计算机存储和组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。数据结构往往与高效的检索算法和索引技术有关。本节介绍Python中的一些常用数据结构的用法，包括栈、队列、树、链表、bitmap和图。第8章Python数据结构课程描述本章知识点数据结构基础队列bitmap栈链表图本章知识点数据结构基础8.1Python数据结构概述8.1.1什么是数据结构8.1.2数据结构和算法的关系8.1Python数据结构概述8.1.1什么是数据结8.1.1什么是数据结构一个程序里面必然会有数据存在，同样的一个或几个数据要组织起来，可以有不同的组织方式，也就是不同的存储方式。不同的组织方式就是不同的结构，我们把这些数据组织在一起的结构称之为数据的结构，也叫做数据结构。比如，有一个字符串是"abc"，我们将其重新组织一下，比如通过list()函数将"abc"变成["a","b","c"]，那么这个时候数据就发生了重组，重组之后数据的结构就变了。["a","b","c"]这种形式的数据的结构被称为列表。也就是说列表是一种数据结构，除此之外，还有元组、字典、栈、树等数据结构。Python的数据结构有很多类型。其中有Python系统自己定义好的，不需要我们自己去定义。这种数据结构被称为Python的内置数据结构，比如列表、元组、字典等。而有些数据组织方式，Python系统里面没有直接定义，需要我们自己去定义实现，这些数据组织方式称为Python扩展数据结构，比如栈和队列。8.1.1什么是数据结构一个程序里面必然会有数据存在，同8.1.1弹出消息框使用showinfo()函数可以弹出提示消息框，方法如下showinfo(title=标题,message=内容)8.1.1弹出消息框使用showinfo()函数可以弹出提8.1.2数据结构和算法的关系数据结构和算法有着密切的联系。因为数据结构是数据的组织方式，也就是数据的存储方式。算法是指运算方法，通俗地讲，算法就是思维。数据结构是静态的，我们编写的程序是动态的。程序要对数据进行运算，运算的方法很多，不同的运算方法就是不同的算法。当然算法不是凭空出来的，它必须建立在数据的基础上，所以数据结构是算法的基础，但同一个数据结构运用不同算法的效率是不同的。8.1.2数据结构和算法的关系数据结构和算法有着密切的联8.2栈8.2.1栈的工作原理8.2.2利用Python列表实现栈的数据结构8.2栈8.2.1栈的工作原理8.2.1栈的工作原理栈是一种经典的数据结构，但它并不是Python的内置数据结构，而是属于扩展数据结构。栈相当于一端开口、一端封闭的容器。栈支持出栈和进栈2种操作。数据移动到栈里面的过程叫做进栈，也叫做压栈、入栈；数据进入到栈里面后，就到了栈顶，同时占了栈的一个位置。当再进入一个数据时，新的数据就占据了栈顶的位置，原来的数据就被新的数据压入到栈顶的下一个位置里。栈只能对其栈顶的数据进行操作，所以这个时候原来的数据就不能被操作。8.2.1栈的工作原理栈是一种经典的数据结构，但它并不是初始化时的栈初始化时的栈将数据A执行进栈操作将数据A执行进栈操作再将数据B执行进栈操作再将数据B执行进栈操作8.2.2利用Python列表实现栈的数据结构1.构造函数首先，在构造函数中定义一个列表items用于实现栈的容器，代码如下：#coding:utf8classStack:"""模拟栈"""def__init__(self):self.items=[]8.2.2利用Python列表实现栈的数据结构1.构造2.isEmpty()函数defisEmpty(self):returnlen(self.items)==02.isEmpty()函数defisEmpty(self3.push()函数defpush(self,item):self.items.append(item)3.push()函数defpush(self,item4.pop()函数defpop(self):returnself.items.pop()4.pop()函数defpop(self):5.peek()函数defpop(self):returnself.items.pop()5.peek()函数defpop(self):6.size()函数defsize(self):returnlen(self.items)6.size()函数defsize(self):【例8-1】s=Stack()#创建栈对象print(s.isEmpty())#打印栈是否为空s.push('DataA')#进栈DataAs.push('DataB')#进栈DataAprint(s.peek())#打印栈顶元素s.push('DataC')#进栈DataCprint(s.size())#打印栈的大小print(s.isEmpty())#打印栈是否为空s.push('DataD')#进栈DataDprint(s.pop())#出栈print(s.pop())#出栈print(s.size())#打印栈的大小)【例8-1】s=Stack()#创建栈对象8.3队列队列是一种经典的数据结构，它也不是Python的内置数据结构，而是属于扩展数据结构。队列相当于两边都开口的容器。但是一边只能进行删除操作，而不能进行插入操作；另一边只能进行插入操作，而不能进行删除操作。进行插入操作的这一端叫做队尾，进行删除操作的这一端叫做队首。所以，队列中的数据是从队尾进队首出的。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素成为出队。8.3队列队列是一种经典的数据结构，它也不是Python初始化时的队列初始化时的队列将数据A执行入队操作将数据A执行入队操作将数据B执行入队操作将数据B执行入队操作再将数据C执行进栈操作再将数据C执行进栈操作再将数据C执行进栈操作再将数据C执行进栈操作将数据A执行出队操作将数据A执行出队操作8.3.2利用Python列表实现队列的数据结构本节介绍一个Python自定义类Queue，它的功能是利用Python列表实现队列的数据结构。8.3.2利用Python列表实现队列的数据结构本节介绍1.构造函数#coding:utf8classQueue(object):def__init__(self):self.queue=[]1.构造函数#coding:utf82.isempty()函数isempty()函数用于判断队列是否为空。如果队列为空，则isempty()函数返回True，否则返回False。isempty()函数的代码如下：

defisempty(self):returnself.queue==[]2.isempty()函数isempty()函数用于判断队3.enqueue()函数defenqueue(self,item):self.queue.append(item)3.enqueue()函数defenqueue(sel4.dequeue()函数defdequeue(self):ifself.queue!=[]:returnself.queue.pop(0)else:returnNone4.dequeue()函数defdequeue(sel5.head()函数head()函数用于返回队首元素，但并不删除该元素。代码如下：

defhead(self):ifself.queue!=[]:returnself.queue[0]else:returnNone5.head()函数head()函数用于返回队首元素，6.tail()函数tail()函数用于返回队尾元素，但并不删除该元素。代码如下：

deftail(self):ifself.queue!=[]:returnself.queue[-1]else:returnNone6.tail()函数tail()函数用于返回队尾元素，7.length()函数length()函数用于返回队列的大小。代码如下：

deflength(self):returnlen(self.queue)7.length()函数length()函数用于返回队列的【例8-2】q=Queue()#创建队列对象print(q.isempty())#打印队列是否为空q.enqueue('DataA')#入队DataAq.enqueue('DataB')#入队DataAprint(q.head())#打印对首元素print(q.tail())#打印队尾元素q.enqueue('DataC')#入队DataCprint(q.length())#打印队列的大小print(q.isempty())#打印队列是否为空q.enqueue('DataD')#入队DataDprint(q.dequeue())#出队print(q.dequeue())#出队print(q.length())#打印队列的大小)【例8-2】q=Queue()#创建队列对象运行结果如下：TrueDataADataB3FalseDataADataB2运行结果如下：True8.4树8.4.1树的工作原理8.4.2遍历二叉树8.4.3在Python程序中实现树的数据结构8.4树8.4.1树的工作原理8.4.1树的工作原理树的定义首先有且只有一个根节点，另外他有Ｎ个不相交的子集，每个子集都是一个子树。8.4.1树的工作原理树的定义首先有且只有一个根节点，另空树空树只有一个根结点的二叉树只有一个根结点的二叉树有左子树的二叉树有左子树的二叉树只有右子树的二叉树只有右子树的二叉树2完全二叉树2完全二叉树8.4.2遍历二叉树“遍历”是二叉树各种操作的基础。二叉树是一种非线性结构，遍历二叉树不像遍历线性链表那样容易，无法通过简单的循环实现。遍历二叉树就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉树包含3个部分，即根结点、左子树和右子树。根据这3个部分的访问次序对二叉树的遍历进行分类，可以将遍历二叉树的方法分为3种类型，分别称为“先序遍历”、“中序遍历”和“后序遍历”。先序遍历指先访问根节点，然后再访问左子树，最后访问右子树；中序遍历指访问左子树，然后再访问根节点，最后访问右子树；中序遍历指先访问根节点，然后访问左子树，最后访问右子树；后序遍历指访问左子树，然后再访问右子树，最后访问根节点。8.4.2遍历二叉树“遍历”是二叉树各种操作的基础。二8.4.3在Python程序中实现树的数据结构本节介绍一个Python自定义类BinaryTree，它的功能是在Python程序中实现树的数据结构。8.4.3在Python程序中实现树的数据结构本节介绍一1.定义树节点类Node首先，定义一个树节点类Node，代码如下：classNode(object):def__init__(self,data=-1,lchild=None,rchild=None):self.data=dataself.lchild=lchildself.rchild=rchild1.定义树节点类Node首先，定义一个树节点类Node，代2.BinaryTree类的构造函数classBinaryTree(object):def__init__(self):self.root=Node()2.BinaryTree类的构造函数classBin3.BinaryTree类的add()函数defadd(self,data):#data为新节点的数据

node=Node(data)#创建新节点

ifself.isEmpty():#如果二叉树为空，则将新节点作为二叉树的根节点

self.root=nodeelse:tree_node=self.rootqueue=[]#以列表存储二叉树

queue.append(self.root)whilequeue:#遍历二叉树

tree_node=queue.pop(0)

3.BinaryTree类的add()函数defadiftree_node.lchild==None:#如果当前节点的左孩子为空，则将新节点作为当前节点的左孩子

tree_node.lchild=nodereturneliftree_node.rchild==None:#如果当前节点的右孩子为空，则将新节点作为当前节点的右孩子

tree_node.rchild=nodereturnelse:queue.append(tree_node.lchild)queue.append(tree_node.rchild)iftree_node.lchild==None:4.BinaryTree类的pre_order()函数defpre_order(self,start):#start是开始遍历的节点

node=startifnode==None:#如果当前节点为空，则返回

returnprintnode.data,#打印当前节点的数据

#如果当前节点的左右子树都为空，则返回

ifnode.lchild==Noneandnode.rchild==None:returnself.pre_order(node.lchild)#从当前节点的左子树开始先序遍历

self.pre_order(node.rchild)#从当前节点的右子树开始先序遍历4.BinaryTree类的pre_order()函数5.BinaryTree类的in_order()函数defin_order(self,start):#start是开始遍历的节点

node=startifnode==None:returnself.in_order(node.lchild)#从当前节点的左子树开始中序遍历

printnode.data,#打印当前节点的数据

self.in_order(node.rchild)#从当前节点的右子树开始中序遍历5.BinaryTree类的in_order()函数d6.post_order()函数defpost_order(self,start):#start是开始遍历的节点

node=startifnode==None:returnself.post_order(node.lchild)#从当前节点的左子树开始后序遍历

self.post_order(node.rchild)#从当前节点的右子树开始后序遍历

printnode.data,#打印当前节点的数据6.post_order()函数defpost_ord7.isEmpty()函数fromtkinterimport*root=Tk()cv=Canvas(root,bg='red',width=200,height=100)cv.pack()root.mainloop()7.isEmpty()函数fromtkinterim8.length()函数deflength(self):returnlen(self.queue)8.length()函数deflength(self)【例8-3】if__name__=='__main__':arr=[]foriinrange(10):arr.append(i)printarrtree=BinaryTree()foriinarr:tree.add(i)

【例8-3】if__name__=='__main__print'preorder:'tree.pre_order(tree.root)print'\nin_order:'tree.in_order(tree.root)print'\npost_order:'tree.post_order(tree.root)print'preorder:'运行结果如下：[0,1,2,3,4,5,6,7,8,9]preorder:0137849256in_order:7381940526post_order:7839415620运行结果如下：[0,1,2,3,4,5,6,7【例8-3】使用的二叉树【例8-3】使用的二叉树8.5链表8.5.1链表的工作原理8.5.2利用Python实现单向链表的数据结构8.5链表8.5.1链表的工作原理8.5.1链表的工作原理链表是一种非连续、非顺序的存储方式。链表由一系列结点组成，每个结点包括两个部分，一部分是数据域，另一部分是指向下一个结点的指针域。链表可以分为单向链表、单向循环链表、双向链表、双向循环链表。单向链表是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。通过指针连接起来，但是只能单向遍历的内存块。，如图8-16所示。8.5.1链表的工作原理链表是一种非连续、非顺序的存储方单向循环链表单向循环链表的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环单向循环链表单向循环链表的特点是表中最后一个结点的指针域指向双向链表双向链表的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。双向链表双向链表的每个数据结点中都有两个指针，分别指向直接后双向循环链表fromtkinterimport*root=Tk()cv=Canvas(root,bg='white',width=200,height=100)cv.create_rectangle(10,10,100,80,outline='blue',fill='red',width=2,stipple='gray12',)cv.pack()root.mainloop()双向循环链表fromtkinterimport*8.5.2利用Python实现单向链表的数据结构首先，定义一个链表节点类Node，代码如下：classNode():__slots__=['_item','_next']#限定Node实例的属性

def__init__(self,item):self._item=itemself._next=None#Node的指针部分默认指向NonedefgetItem(self):returnself._itemdefgetNext(self):returnself._nextdefsetItem(self,newitem):self._item=newitemdefsetNext(self,newnext):self._next=newnext8.5.2利用Python实现单向链表的数据结构首先，定2.类SinglelinkedList的初始函数classSingleLinkedList():def__init__(self):self._head=None#初始化链表为空表

self._size=02.类SinglelinkedList的初始函数class3.类SinglelinkedList的isEmpty()函数defisEmpty(self):returnself._head==None3.类SinglelinkedList的isEmpty()4.类SinglelinkedList的add()函数defadd(self,item):temp=Node(item)temp.setNext(self._head)self._head=temp4.类SinglelinkedList的add()函数5.类SinglelinkedList的append()函数defappend(self,item):temp=Node(item)ifself.isEmpty():self._head=temp#若为空表，将添加的元素设为第一个元素

else:current=self._headwhilecurrent.getNext()!=None:current=current.getNext()#遍历链表

current.setNext(temp)#此时current为链表最后的元素5.类SinglelinkedList的append()6.类SinglelinkedList的index()函数defindex(self,item):current=self._headcount=0found=Nonewhilecurrent!=Noneandnotfound:count+=1ifcurrent.getItem()==item:found=Trueelse:current=current.getNext()iffound:returncountelse:raiseValueError,'%sisnotinlinkedlist'%item6.类SinglelinkedList的index()函7.类SinglelinkedList的remove()函数defremove(self,item):current=self._headpre=Nonewhilecurrent!=None:ifcurrent.getItem()==item:ifnotpre:self._head=current.getNext()else:pre.setNext(current.getNext())breakelse:pre=currentcurrent=current.getNext()7.类SinglelinkedList的remove()函8.类SinglelinkedList的insert()函数definsert(self,pos,item):ifpos<=1:self.add(item)elifpos>self.size():self.append(item)else:temp=Node(item)count=1pre=Nonecurrent=self._headwhilecount<pos:count+=1pre=currentcurrent=current.getNext()pre.setNext(temp)temp.setNext(current)8.类SinglelinkedList的insert()【例8-4】使用类SinglelinkedList的例子if__name__=='__main__':a=SingleLinkedList()#定义单向链表对象aforiinrange(1,10):#向单向链表对象a中添加10个元素a.append(i)printa.size()#打印单向链表的大小()#打印单向链表的大小printa.index(5)#打印位置5的元素a.remove(4)#移除位置4的元素()#遍历链表a.insert(4,100)#在位置4插入元素100()#遍历链表【例8-4】使用类SinglelinkedList的例子第8章Python数据结构课程描述数据结构是计算机存储和组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。数据结构往往与高效的检索算法和索引技术有关。本节介绍Python中的一些常用数据结构的用法，包括栈、队列、树、链表、bitmap和图。第8章Python数据结构课程描述本章知识点数据结构基础队列bitmap栈链表图本章知识点数据结构基础8.1Python数据结构概述8.1.1什么是数据结构8.1.2数据结构和算法的关系8.1Python数据结构概述8.1.1什么是数据结8.1.1什么是数据结构一个程序里面必然会有数据存在，同样的一个或几个数据要组织起来，可以有不同的组织方式，也就是不同的存储方式。不同的组织方式就是不同的结构，我们把这些数据组织在一起的结构称之为数据的结构，也叫做数据结构。比如，有一个字符串是"abc"，我们将其重新组织一下，比如通过list()函数将"abc"变成["a","b","c"]，那么这个时候数据就发生了重组，重组之后数据的结构就变了。["a","b","c"]这种形式的数据的结构被称为列表。也就是说列表是一种数据结构，除此之外，还有元组、字典、栈、树等数据结构。Python的数据结构有很多类型。其中有Python系统自己定义好的，不需要我们自己去定义。这种数据结构被称为Python的内置数据结构，比如列表、元组、字典等。而有些数据组织方式，Python系统里面没有直接定义，需要我们自己去定义实现，这些数据组织方式称为Python扩展数据结构，比如栈和队列。8.1.1什么是数据结构一个程序里面必然会有数据存在，同8.1.1弹出消息框使用showinfo()函数可以弹出提示消息框，方法如下showinfo(title=标题,message=内容)8.1.1弹出消息框使用showinfo()函数可以弹出提8.1.2数据结构和算法的关系数据结构和算法有着密切的联系。因为数据结构是数据的组织方式，也就是数据的存储方式。算法是指运算方法，通俗地讲，算法就是思维。数据结构是静态的，我们编写的程序是动态的。程序要对数据进行运算，运算的方法很多，不同的运算方法就是不同的算法。当然算法不是凭空出来的，它必须建立在数据的基础上，所以数据结构是算法的基础，但同一个数据结构运用不同算法的效率是不同的。8.1.2数据结构和算法的关系数据结构和算法有着密切的联8.2栈8.2.1栈的工作原理8.2.2利用Python列表实现栈的数据结构8.2栈8.2.1栈的工作原理8.2.1栈的工作原理栈是一种经典的数据结构，但它并不是Python的内置数据结构，而是属于扩展数据结构。栈相当于一端开口、一端封闭的容器。栈支持出栈和进栈2种操作。数据移动到栈里面的过程叫做进栈，也叫做压栈、入栈；数据进入到栈里面后，就到了栈顶，同时占了栈的一个位置。当再进入一个数据时，新的数据就占据了栈顶的位置，原来的数据就被新的数据压入到栈顶的下一个位置里。栈只能对其栈顶的数据进行操作，所以这个时候原来的数据就不能被操作。8.2.1栈的工作原理栈是一种经典的数据结构，但它并不是初始化时的栈初始化时的栈将数据A执行进栈操作将数据A执行进栈操作再将数据B执行进栈操作再将数据B执行进栈操作8.2.2利用Python列表实现栈的数据结构1.构造函数首先，在构造函数中定义一个列表items用于实现栈的容器，代码如下：#coding:utf8classStack:"""模拟栈"""def__init__(self):self.items=[]8.2.2利用Python列表实现栈的数据结构1.构造2.isEmpty()函数defisEmpty(self):returnlen(self.items)==02.isEmpty()函数defisEmpty(self3.push()函数defpush(self,item):self.items.append(item)3.push()函数defpush(self,item4.pop()函数defpop(self):returnself.items.pop()4.pop()函数defpop(self):5.peek()函数defpop(self):returnself.items.pop()5.peek()函数defpop(self):6.size()函数defsize(self):returnlen(self.items)6.size()函数defsize(self):【例8-1】s=Stack()#创建栈对象print(s.isEmpty())#打印栈是否为空s.push('DataA')#进栈DataAs.push('DataB')#进栈DataAprint(s.peek())#打印栈顶元素s.push('DataC')#进栈DataCprint(s.size())#打印栈的大小print(s.isEmpty())#打印栈是否为空s.push('DataD')#进栈DataDprint(s.pop())#出栈print(s.pop())#出栈print(s.size())#打印栈的大小)【例8-1】s=Stack()#创建栈对象8.3队列队列是一种经典的数据结构，它也不是Python的内置数据结构，而是属于扩展数据结构。队列相当于两边都开口的容器。但是一边只能进行删除操作，而不能进行插入操作；另一边只能进行插入操作，而不能进行删除操作。进行插入操作的这一端叫做队尾，进行删除操作的这一端叫做队首。所以，队列中的数据是从队尾进队首出的。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素成为出队。8.3队列队列是一种经典的数据结构，它也不是Python初始化时的队列初始化时的队列将数据A执行入队操作将数据A执行入队操作将数据B执行入队操作将数据B执行入队操作再将数据C执行进栈操作再将数据C执行进栈操作再将数据C执行进栈操作再将数据C执行进栈操作将数据A执行出队操作将数据A执行出队操作8.3.2利用Python列表实现队列的数据结构本节介绍一个Python自定义类Queue，它的功能是利用Python列表实现队列的数据结构。8.3.2利用Python列表实现队列的数据结构本节介绍1.构造函数#coding:utf8classQueue(object):def__init__(self):self.queue=[]1.构造函数#coding:utf82.isempty()函数isempty()函数用于判断队列是否为空。如果队列为空，则isempty()函数返回True，否则返回False。isempty()函数的代码如下：

defisempty(self):returnself.queue==[]2.isempty()函数isempty()函数用于判断队3.enqueue()函数defenqueue(self,item):self.queue.append(item)3.enqueue()函数defenqueue(sel4.dequeue()函数defdequeue(self):ifself.queue!=[]:returnself.queue.pop(0)else:returnNone4.dequeue()函数defdequeue(sel5.head()函数head()函数用于返回队首元素，但并不删除该元素。代码如下：

defhead(self):ifself.queue!=[]:returnself.queue[0]else:returnNone5.head()函数head()函数用于返回队首元素，6.tail()函数tail()函数用于返回队尾元素，但并不删除该元素。代码如下：

deftail(self):ifself.queue!=[]:returnself.queue[-1]else:returnNone6.tail()函数tail()函数用于返回队尾元素，7.length()函数length()函数用于返回队列的大小。代码如下：

deflength(self):returnlen(self.queue)7.length()函数length()函数用于返回队列的【例8-2】q=Queue()#创建队列对象print(q.isempty())#打印队列是否为空q.enqueue('DataA')#入队DataAq.enqueue('DataB')#入队DataAprint(q.head())#打印对首元素print(q.tail())#打印队尾元素q.enqueue('DataC')#入队DataCprint(q.length())#打印队列的大小print(q.isempty())#打印队列是否为空q.enqueue('DataD')#入队DataDprint(q.dequeue())#出队print(q.dequeue())#出队print(q.length())#打印队列的大小)【例8-2】q=Queue()#创建队列对象运行结果如下：TrueDataADataB3FalseDataADataB2运行结果如下：True8.4树8.4.1树的工作原理8.4.2遍历二叉树8.4.3在Python程序中实现树的数据结构8.4树8.4.1树的工作原理8.4.1树的工作原理树的定义首先有且只有一个根节点，另外他有Ｎ个不相交的子集，每个子集都是一个子树。8.4.1树的工作原理树的定义首先有且只有一个根节点，另空树空树只有一个根结点的二叉树只有一个根结点的二叉树有左子树的二叉树有左子树的二叉树只有右子树的二叉树只有右子树的二叉树2完全二叉树2完全二叉树8.4.2遍历二叉树“遍历”是二叉树各种操作的基础。二叉树是一种非线性结构，遍历二叉树不像遍历线性链表那样容易，无法通过简单的循环实现。遍历二叉树就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉树包含3个部分，即根结点、左子树和右子树。根据这3个部分的访问次序对二叉树的遍历进行分类，可以将遍历二叉树的方法分为3种类型，分别称为“先序遍历”、“中序遍历”和“后序遍历”。先序遍历指先访问根节点，然后再访问左子树，最后访问右子树；中序遍历指访问左子树，然后再访问根节点，最后访问右子树；中序遍历指先访问根节点，然后访问左子树，最后访问右子树；后序遍历指访问左子树，然后再访问右子树，最后访问根节点。8.4.2遍历二叉树“遍历”是二叉树各种操作的基础。二8.4.3在Python程序中实现树的数据结构本节介绍一个Python自定义类BinaryTree，它的功能是在Python程序中实现树的数据结构。8.4.3在Python程序中实现树的数据结构本节介绍一1.定义树节点类Node首先，定义一个树节点类Node，代码如下：classNode(object):def__init__(self,data=-1,lchild=None,rchild=None):self.data=dataself.lchild=lchildself.rchild=rchild1.定义树节点类Node首先，定义一个树节点类Node，代2.BinaryTree类的构造函数classBinaryTree(object):def__init__(self):self.root=Node()2.BinaryTree类的构造函数classBin3.BinaryTree类的add()函数defadd(self,data):#data为新节点的数据

node=Node(data)#创建新节点

ifself.isEmpty():#如果二叉树为空，则将新节点作为二叉树的根节点

self.root=nodeelse:tree_node=self.rootqueue=[]#以列表存储二叉树

queue.append(self.root)whilequeue:#遍历二叉树

tree_node=queue.pop(0)

3.BinaryTree类的add()函数defadiftree_node.lchild==None:#如果当前节点的左孩子为空，则将新节点作为当前节点的左孩子

tree_node.lchild=nodereturneliftree_node.rchild==None:#如果当前节点的右孩子为空，则将新节点作为当前节点的右孩子

tree_node.rchild=nodereturnelse:queue.append(tree_node.lchild)queue.append(tree_node.rchild)iftree_node.lchild==None:4.BinaryTree类的pre_order()函数defpre_order(self,start):#start是开始遍历的节点

node=startifnode==None:#如果当前节点为空，则返回

returnprintnode.data,#打印当前节点的数据

#如果当前节点的左右子树都为空，则返回

ifnode.lchild==Noneandnode.rchild==None:returnself.pre_order(node.lchild)#从当前节点的左子树开始先序遍历

self.pre_order(node.rchild)#从当前节点的右子树开始先序遍历4.BinaryTree类的pre_order()函数5.BinaryTree类的in_order()函数defin_order(self,start):#start是开始遍历的节点

node=startifnode==None:returnself.in_order(node.lchild)#从当前节点的左子树开始中序遍历

printnode.data,#打印当前节点的数据

self.in_order(node.rchild)#从当前节点的右子树开始中序遍历5.BinaryTree类的in_order()函数d6.post_order()函数defpost_order(self,start):#start是开始遍历的节点

node=startifnode==None:returnself.post_order(node.lchild)#从当前节点的左子树开始后序遍历

self.post_order(node.rchild)#从当前节点的右子树开始后序遍历

printnode.data,#打印当前节点的数据6.post_order()函数defpost_ord7.isEmpty()函数fromtkinterimport*root=Tk()cv=Canvas(root,bg='red',width=200,height=100)cv.pack()root.mainloop()7.isEmpty()函数fromtkinterim8.length()函数deflength(self):returnlen(self.queue)8.length()函数deflength(self)【例8-3】if__name__=='__main__':arr=[]foriinrange(10):arr.append(i)printarrtree=BinaryTree()foriinarr:tree.add(i)

【例8-3】if__name__=='__main__print'preorder:'tree.pre_order(tree.root)print'\nin_order:'tree.in_order(tree.root)print'\npost_order:'tree.post_order(tree.root)print'preorder:'运行结果如下：[0,1,2,3,4,5,6,7,8,9]preorder:0137849256in_order:7381940526post_order:7839415620运行结果如下：[0,1,2,3,4,5,6,7【例8-3】使用的二叉树【例8-3】使用的二叉树8.5链表8.5.1链表的工作原理8.5.2利用Python实现单向链表的数据结构8.5链表8.5.1链表的工作原理8.5.1链表的工作原理链表是一种非连续、非顺序的存储方式。链表由一系列结点组成，每个结点包括两个部分，一部分是数据域，另一部分是指向下一个结点的指针域。链表可以分为单向链表、单向循环链表、双向链表、双向循环链表。单向链表是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。通过指针连接起来，但是只能单向遍历的内存块。，如图8-16所示。8.5.1链表的工作原理链表是一种非连续、非顺序的存储方单向循环链表单向循环链表的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环单向循环链表单向循环链表的特点是表中最后一个结点的指针域指向双向链表双向链表的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。双向链表双向链表的每个数据结点中都有两个指针，分别指向直接后双向循环链表fromtkinterimport*root=Tk()cv=Canvas(root,bg='white',width=200,height=100)cv.create_rectangle(10,10,100,80,outline='blue',fill='red',width=2,stipple='gray12',)cv.pack()root.mainloop()双向循环链表fromtkinterimport*8.5.2利用Python实现单向链表的数据结构首先，定义一个链表节点类Node，代码如下：classNode():__slots__=['_item','_next']#限定Node实例的属性

def__init__(self,item):self._item=itemself._next=None#Node的指针部分默认指向NonedefgetItem(self):returnself._itemdefgetNext(self):returnself._nextdefsetItem(self,newitem):self._item=newitemdefsetNext(self,newnext):self._next=newnext8.5.2利用Python实现单向链表的数据结构首先，定2.类Singlelin