【Python数据结构系列】☀️《树与二叉树-基础知识》——知识点讲解+代码实现☀️
【Python数据结构系列】☀️《树与二叉树-基础知识》——知识点讲解+代码实现☀️
文章目录
数据结构之树和二叉树
第一部分 树和二叉树的基础知识
1、树和二叉树的定义
1.1 树的定义
树（Tree）是n（n≥0）个结点的有限集，它或为空树（n=0）；或为非空树，对于非空树T：
- （1）有且仅有一个称之为根的结点；
- （2）除根结点以外的其余结点可分为m（m>0）个互不相交的有限集T₁，T₂，…，Tm，其中每一个结合本身又是一棵树，并且成为根的子树（SubTree）。
图 1(A) 是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意图。对于数据 A 来说，和数据 B、C、D 有关系；对于数据 B 来说，和 E、F 有关系。这就是“一对多”的关系。将具有“一对多”关系的集合中的数据元素按照图 1（A）的形式进行存储，整个存储形状在逻辑结构上看，类似于实际生活中倒着的树（图 1（B）倒过来），所以称这种存储结构为“树型”存储结构。
1.2 树的基本术语
（1）结点：树中的一个独立单元。包含一个数据元素及若干指向其子树的分支，如图1（A）中的A、B、C、D等。 （2）结点的度：结点拥有的子树数成为结点的度。例如，A的度为3，C的度为1，F的度为0。 （3）树的度：树的度是树内各结点度的最大值。图1（A）所示的树的度为3。 （4）叶子：度为0的结点称为非终端结点或分支结点。除根节点之外，非终端结点也成为内部结点。 （5）非终端结点：度不为0的结点称为叶子或终端结点。结点K、L、F、G、M、I、J都是树的叶子。 （6）双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例如，B的双亲为A，B的孩子有E和F。 （7）兄弟：同一个双亲的孩子之间互称兄弟。例如，H、I和J互为兄弟。 （8）祖先：从根到该结点所经分支上的所有结点。例如，M的祖先为A、D和H。 （9）子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子孙为E、K、L和F。 （10）层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的层次等于双亲结点的层次加1。 （11）堂兄弟：双亲在同一层的结点互为堂兄弟。例如，结点G与E、F、H、I、J互为堂兄弟。 （12）树的深度：树中结点的最大层次称为树的深度或高度。图1（A）所示的树的深度为4。 （13）有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。 （14）森林：是m（m≥0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以用森林和树互相递归的定义来描述树。
1.3 二叉树的定义
二叉树（Binary Tree）是n（n≥0）个结点所构成的集合，它或为空树（n=0）；或为非空树，对于非空树： （1）有且仅有一个称之为根的结点； （2）除根结点以外的其余结点分为两个互不相交的子集T₁和T₂，分别称为T的左子树和右子树，且T₁和T₂本身又都是二叉树。
二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点： （1）二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）； （2）二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树的递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互不想交的二叉树组成。由于这两棵子树也是二叉树，则由二叉树的定义，它们也可以是空树。由此，二叉树可以有5种基本形态，如下图所示。
树的基本术语是都适用于二叉树的。
2、二叉树的性质和存储结构
2.1 二叉树的性质
二叉树具有以下几个性质：
二叉树还有两种特殊的形态，满二叉树和完全二叉树。
- 如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。
- 如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
2.2 二叉树的存储结构
二叉树的存储结构有两种，分别为顺序存储和链式存储。
2.2.1 顺序存储
二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。
普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些节点，将其"拼凑"成完全二叉树即可。如下图所示，左侧是普通二叉树，右侧是转化后的完全（满）二叉树。
解决了二叉树的转化问题，接下来我们来学习如何顺序存储完全（满）二叉树。完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。
例如，存储上图所示的完全二叉树，其存储状态如下图所示：
由此，我们就实现了完全二叉树的顺序存储。
2.2.2 链式存储
其实二叉树并不合适用数组存储，因为并不是每个二叉树都是完全二叉树，普通二叉树使用顺序表存储会存在空间浪费的现象。接下来介绍二叉树的链式存储结构。
上图为一颗普通的二叉树，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。因此，其对应的链式存储结构如下图所示：
由上图可知，采用链式存储二叉树时，其节点结构由 3 部分构成：
- 指向左孩子节点的指针（Lchild）；
- 节点存储的数据（data）；
- 指向右孩子节点的指针（Rchild）；
其实，二叉树的链式存储结构远不止上图 所示的这一种。例如，在某些实际场景中，可能会做 “查找某节点的父节点” 的操作，这时可以在节点结构中再添加一个指针域，用于各个节点指向其父亲节点，如下图 所示：
利用上图所示的三叉链表，我们可以很轻松地找到各节点的父节点。因此，在解决实际问题时，用合适的链表结构存储二叉树，可以起到事半功倍的效果。
2.3 遍历二叉树
在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者是对树中的全部结点逐一处理，这就提出了一个遍历二叉树的问题。遍历二叉树（traversing binary tree）是指按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。访问的含义很广，可以是对结点做各种处理，包括输出结点的信息，对结点进行运算和修改等。遍历二叉树是二叉树最基本的操作，也是二叉树其他各种操作的基础，遍历的实质是对二叉树进行线性化的过程，即遍历的结果是将非线性结构的树中结点排成一个线性序列。由于二叉树的每个结点都有可能有两棵子树，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。 二叉树是有３个基本单元组成：根节点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如Ｌ、Ｄ、Ｒ分别表示遍历左子树、访问根节点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。若限定先左后右，则只有前3中情况，分别称之为先（根）序遍历、中（根）序遍历和后（根）序遍历。 基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。 先序遍历二叉树的操作定义如下： 若二叉树为空，则空操作；否则 （１）访问根节点； （２）先序遍历左子树； （３）先序遍历右子树。 中序遍历二叉树操作定义如下： 若二叉树为空，则空操作；否则 （１）中序遍历左子树； （２）访问根节点； （３）中序遍历右子树。 后序遍历二叉树的操作定义如下： 若二叉树为空，则空操作；否则 （１）后序遍历左子树； （２）后序遍历右子树； （３）访问根节点。
例如，上图的二叉树表示的为表达式：a+b*（c-d）-e/f
- 若先序遍历此二叉树，可得到二叉树的先序序列为：-+a*b-cd/ef
- 类似地，中序遍历此二叉树，可得此二叉树的中序序列为：a+b*c-d-e/f
- 后序遍历此二叉树，可得此二叉树的后序序列为：abcd-*+ef/-
大作业一：二叉树的基本操作
构建二叉树（遍历列表按照先序顺序插入二叉树中的值），用Python编程完成,并完成以下操作：（包括但不限于，可以根据自己能力继续扩展）
- 递归前序遍历二叉树
- 非递归前序遍历二叉树
- 递归中序遍历二叉树
- 非递归中序遍历二叉树
- 递归后序二叉树
- 非递归遍历二叉树
- 返回二叉树的深度
- 返回二叉树的结点数目
- 复制二叉树
最后输出结果要求：
测试案例的输入列表为［‘A’,‘B’,‘C’,’#’,’#’,‘D’,‘E’,’#’,‘G’,’#’,’#’,‘F’,’#’,’#’,’#’］,输出的遍历结果见下图。
【注】：二叉树的生成，需要用以上输入列表的数值哦；对于非递归遍历，需要用到栈。
代码思路（仅供参考，思路不限）： 二叉树的生成： １、构建结点类，构建二叉树类 ２、输入一个列表，然后从列表中取数，按照先序顺序进行递归插入数值，即先创建根结点，再左子树，再右子树。 ３、首先输入一个字符，判断其是否为＃，不是＃的即创建根结点，该结点的数值域为该字符，继续递归生成左子树， 输入第二个字符，判断其是否为＃，不是＃的即生成结点，是＃的将返回上一层递归，如此判断递归生成二叉树。 二叉树的遍历：按照先序、中序、后序遍历的顺序输出字符即可，主要是非递归的遍历是需要借助栈的，拿中序遍历的非递归算法思想来举例：定义一个空栈，从根结点开始访问，若当前节点非空，则将该节点压栈并访问其左子树，循环执行，直至当前节点为空时，取栈顶元素访问并弹栈，然后访问其右子树，再重复如上操作，直至遍历节点的指针为空在且栈也为空。
代码（递归写法）：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2021/8/18 8:16
# @Author : vaxtiandao
# @File : Binary tree.py
class Tree():
def __init__(self, item):
self.item = item
self.l = None
self.r = None
def llink(self, other): # 左连接子节点
self.l = other
def rlink(self, other): # 右连接子节点
self.r = other
# def __repr__(self):
# return str(self.item)+' '+str(self.l)+' '+str(self.r)
def get_depth(self): # 获取深度（递归）
if self.l == None:
l_depth = 0
else:
l_depth = self.l.get_depth()
if self.r == None:
r_depth = 0
else:
r_depth = self.r.get_depth()
return max(l_depth, r_depth) + 1
def get_len(self): # 获取节点数（递归）
if self.l == None:
l_len = 0
else:
l_len = self.l.get_len()
if self.r == None:
r_len = 0
else:
r_len = self.r.get_len()
return l_len + r_len + 1
def show_first(self): # 先序遍历（递归）
print(self.item, end=' ')
if self.l != None:
self.l.show_first()
if self.r != None:
self.r.show_first()
def show_mid(self): # 中序遍历（递归）
if self.l != None:
self.l.show_mid()
print(self.item, end=' ')
if self.r != None:
self.r.show_mid()
def show_last(self): # 后序遍历（递归）
if self.l != None:
self.l.show_last()
if self.r != None:
self.r.show_last()
print(self.item, end=' ')
def copy(self): # 拷贝节点
c_result = Tree(self.item)
c_result.llink(self.l)
c_result.rlink(self.r)
return c_result
def copy_deep(self): # 深拷贝节点以下整个树
c_result = Tree(self.item)
if self.l != None:
c_result.llink(self.l.copy())
if self.r != None:
c_result.rlink(self.r.copy())
return c_result
def create(x): # 根据列表创建二叉树
try:
tmp = next(x)
if tmp == '#':
return
root = Tree(tmp)
root.llink(create(x))
root.rlink(create(x))
return root
except:
pass
tree_list = ['A', 'B', 'C', '#', '#', 'D', 'E', '#', 'G', '#', '#', 'F', '#', '#', '#']
it = iter(tree_list)
root = create(it)
# 先序遍历
print(root.show_first())
# 中序遍历
print(root.show_mid())
# 后序遍历
print(root.show_last())实现效果：
代码（非递归，借用栈）：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2021/8/18 8:43
# @Author : vaxtiandao
# @File : Binary tree2.py
# 定义结点类，包含两个成员：结点元素值和指向下一结点的指针
class SingleNode():
# 结点类初始化
def __init__(self, item):
self.item = item # item存放结点的数值
self.next = None # 下一指针指向
# 定义链栈
class LinkStack():
# 初始化
def __init__(self):
self.top = None
# 判断是否为空
def is_empty(self):
if self.top == None:
return True
else:
return False
# 返回栈顶元素
def get_element(self):
if self.is_empty():
return None
else:
return self.top.item
# 返回栈长度
def get_length(self):
tmp = self.top
if tmp == None:
return 0
i = 0
while tmp != None:
tmp = tmp.next
i += 1
return i
# 进栈
def add_stack(self, element):
node = SingleNode(element)
node.next = self.top # 指针变换
self.top = node
# 出栈
def remove_stack(self):
if self.is_empty():
raise IndexError("栈已空，无法出栈")
else:
node = self.top
self.top = self.top.next
return node.item
# 清空栈
def clear_stack(self):
self.top = None
class Tree():
def __init__(self,item):
self.item=item
self.l=None
self.r=None
def llink(self,other): #左连接子节点
self.l=other
def rlink(self,other): #右连接子节点
self.r=other
# def __repr__(self):
# return str(self.item)+' '+str(self.l)+' '+str(self.r)
def get_depth(self): #获取深度（递归）
if self.l==None:
l_depth=0
else:
l_depth=self.l.get_depth()
if self.r==None:
r_depth=0
else:
r_depth=self.r.get_depth()
return max(l_depth,r_depth)+1
def get_len(self): #获取节点数（递归）
if self.l==None:
l_len=0
else:
l_len=self.l.get_len()
if self.r==None:
r_len=0
else:
r_len=self.r.get_len()
return l_len+r_len+1
def show_first(self): #先序遍历（递归）
print(self.item,end=' ')
if self.l !=None:
self.l.show_first()
if self.r !=None:
self.r.show_first()
def show_mid(self): #中序遍历（递归）
if self.l !=None:
self.l.show_mid()
print(self.item,end=' ')
if self.r !=None:
self.r.show_mid()
def show_last(self): #后序遍历（递归）
if self.l !=None:
self.l.show_last()
if self.r !=None:
self.r.show_last()
print(self.item,end=' ')
def copy(self): #拷贝节点
c_result=Tree(self.item)
c_result.llink(self.l)
c_result.rlink(self.r)
return c_result
def copy_deep(self): #深拷贝节点以下整个树
c_result=Tree(self.item)
if self.l!=None:
c_result.llink(self.l.copy())
if self.r!=None:
c_result.rlink(self.r.copy())
return c_result
def create(x): #根据列表创建二叉树
try:
tmp=next(x)
if tmp=='#':
return
root=Tree(tmp)
root.llink(create(x))
root.rlink(create(x))
return root
except:
pass
def show_first(tree): # 非递归先序遍历（利用栈）
if tree == None: # 如果树为空，返回空
return None
stack = LinkStack() # 如果树不为空，利用栈遍历
tmp = tree # tmp指针指向根节点
stack.add_stack(tmp) # 根节点入栈
while not stack.is_empty(): # 当栈不为空时，不断出栈
tmp = stack.remove_stack()
print(tmp.item, end=' ') # 访问并打印当前节点内容
if tmp.r != None: # 将当前节点的子节点入栈（为了保证先访问左树，先入栈右节点）
stack.add_stack(tmp.r)
if tmp.l != None:
stack.add_stack(tmp.l)
def show_mid(tree): # 非递归中序遍历
if tree == None:
return None
stack = LinkStack()
tmp = tree # 定义指针
while tmp != None or (not stack.is_empty()): # 指针不为空或栈不为空
while tmp != None: # 将当前节点入栈，并查找左树的最左端
stack.add_stack(tmp)
tmp = tmp.l
if not stack.is_empty(): # 找到左树最左端后，出栈一个节点，此节点为最左端节点
tmp = stack.remove_stack()
print(tmp.item, end=' ') # 访问当前节点
tmp = tmp.r # 指针指向右节点
def show_last(tree): # 非递归后序遍历（利用2个栈，用逆先序DRL访问整个树后，利用第二个栈将结果保存并反转，即可得到后序LRD访问的结果）
if tree == None:
return None
stack = LinkStack()
out_stack = LinkStack()
tmp = tree
stack.add_stack(tmp)
while not stack.is_empty():
tmp = stack.remove_stack()
out_stack.add_stack(tmp) # 访问节点并入栈结果保存的栈
if tmp.l != None:
stack.add_stack(tmp.l) # 其他部分与先序类似，但左右子节点入栈顺序需反转
if tmp.r != None:
stack.add_stack(tmp.r)
while not out_stack.is_empty(): # 将结果出栈，达到反转顺序效果
print(out_stack.remove_stack().item, end=' ')
tree_list=['A','B','C','#','#','D','E','#','G','#','#','F','#','#','#']
it=iter(tree_list)
root=create(it)
# 先序遍历
print(root.show_first())
# 中序遍历
print(root.show_mid())
# 后序遍历
print(root.show_last())
croot=root.copy()
droot=root.copy_deep()
print(root,root.l,root.r)
print(croot,croot.l,croot.r)
print(droot,droot.l,droot.r)实现效果：
2.4 线索二叉树
2.4.1 线索二叉树的概念
问题：为什么要研究线索二叉树？ 当用二叉链表作为二叉树的存储结构时，可以很方便地找到某个结点的左右孩子；但一般情况下去，无法直接找到该结点在某种遍历序列中的前驱和后继结点。
提出问题： 如何寻找特定遍历序列中二叉树结点的前驱和后继？
解决的办法： １、通过遍历寻找——费时间 ２、再增设前驱、后继指针域——增加了存储负担。 ３、利用二叉链表中的空指针域。
回顾：二叉链表中空指针域的数量： 具有ｎ个结点的二叉链表中，一共有2n个指针域；因为n个结点中有n-1个孩子，即2n个指针域中，有n-1个用来指示结点的左右孩子，其余n+1个指针域为空。
利用二叉链表中的空指针域： 如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某结点的左孩子为空，则将空的右孩子指针域改为指向其后继——这种改变指向的指针称为“线索”，加上线索的二叉树称为线索二叉树（Threaded BinaryTree）。
试做如下规定： 若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，尚需改变结点结构，增加两个标志域，其结点形式如下图所示。
2.4.2 构造线索二叉树
由于线索二叉树构造的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程，可用递归算法。对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树，包括先序线索二叉树、中序线索二叉树和后序线索二叉树。
以上这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树（Threaded BinaryTree）。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。 （１）**先序线索二叉树 **
（２）中序线索二叉树
（３）后序线索二叉树
再如下图（ａ）所示为中序线索二叉树，与其对应的中序线索链表如图（ｂ）所示。其中实线为指针（指向左、右子树），虚线为线索（指向前驱和后继）。为了方便起见，仿照线性表的存储结构，在二叉树的线索链表上也添加了一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；同时，令二叉树中序序列中第一个结点的lchild域指针和最后一个结点rchild域的指针均指向头结点。这好比为二叉树建立了一个双向线索链表，既可从第一个结点起顺后继进行遍历，也可从最后一个结点起顺前驱遍历。
2.4.3遍历线索二叉树
由于有了结点的前驱和后继信息，因此线索二叉树的遍历和在指定次序下查找结点的前驱和后继算法都变得简单，且不再需要借助栈。若需经常查找结点在所遍历线性序列中的前驱和后继，则采用线索链表作为存储结构。
大作业二：线索化二叉树及遍历线索二叉树
构建二叉树（通过手动输入结点来构建二叉树），并完成以下操作：
- 中序线索化二叉树并遍历
- 前序线索化二叉树并遍历
- 后序线索化二叉树并遍历
最后输出结果要求：
为了可以保证最后线索化结果的正确性，可在类中加入一个未线索化的二叉树的遍历来验证。
代码思路（仅供参考，思路不限）： 我们手动输入结点来构建二叉树，主要是为了更好的测试线索化是否成功。 二叉树的生成：创建结点类，生成ｎ个根结点，然后利用结点的关系来创建二叉树（如ｔ的左孩子为ｆ，ｔ的右孩子是ｇ，ｇ的左孩子是ｈ）。 线索二叉树的类：线索化的过程就是在遍历的过程中修改空指针的过程，如中序线索化的过程，即先线索化左子树， （１）处理当前结点的前驱结点，若当前结点的左子结点为空，则让当前结点的左指针指向前驱结点，并修改当前结点的左指针类型为１ （２）处理当前结点的后继结点，若前驱结点存在，且当前结点的右子节点为空，则让前驱结点的右指针指向当前结点，修改前驱结点的有指针类型为１ 每处理一个结点后，就令当前结点为下一个结点的前驱结点。 递归线索化右子树。
遍历线索二叉树：（以中序遍历为例）循环找到第一个左指针类型为１的结点，打印该结点，如果当前结点的右指针指向的就是后继结点，那就一直输出，如果当前结点的右指针类型为１，那就获取到该结点的后继结点，令其后继结点继续遍历。
代码：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2021/8/18 9:03
# @Author : vaxtiandao
# @File : Clue binary tree.py
# 定义结点类，包含两个成员：结点元素值和指向下一结点的指针
class SingleNode():
# 结点类初始化
def __init__(self, item):
self.item = item # item存放结点的数值
self.next = None # 下一指针指向
# 定义链栈
class LinkStack():
# 初始化
def __init__(self):
self.top = None
# 判断是否为空
def is_empty(self):
if self.top == None:
return True
else:
return False
# 返回栈顶元素
def get_element(self):
if self.is_empty():
return None
else:
return self.top.item
# 返回栈长度
def get_length(self):
tmp = self.top
if tmp == None:
return 0
i = 0
while tmp != None:
tmp = tmp.next
i += 1
return i
# 进栈
def add_stack(self, element):
node = SingleNode(element)
node.next = self.top # 指针变换
self.top = node
# 出栈
def remove_stack(self):
if self.is_empty():
raise IndexError("栈已空，无法出栈")
else:
node = self.top
self.top = self.top.next
return node.item
# 清空栈
def clear_stack(self):
self.top = None
class Ttree(): # 线索二叉树类
def __init__(self, item):
self.item = item
self.l = None
self.r = None
self.ltag = 0
self.rtag = 0
def llink(self, other):
self.l = other
self.ltag = 0
def rlink(self, other):
self.r = other
self.rtag = 0
def __repr__(self):
if self.l == None:
l_item = 'NA'
else:
l_item = str(self.l.item)
if self.r == None:
r_item = 'NA'
else:
r_item = str(self.r.item)
return str(self.item) + ' id:' + str(id(self)) + ' ltag:' + str(self.ltag) + ' l:' + l_item + \
' rtag:' + str(self.rtag) + ' r:' + r_item
def get_depth(self):
if self.ltag == 1 or self.l == None:
l_depth = 0
else:
l_depth = self.l.get_depth()
if self.rtag == 1 or self.r == None:
r_depth = 0
else:
r_depth = self.r.get_depth()
return max(l_depth, r_depth) + 1
def get_len(self):
if self.ltag == 1 or self.l == None:
l_len = 0
else:
l_len = self.l.get_len()
if self.rtag == 1 or self.r == None:
r_len = 0
else:
r_len = self.r.get_len()
return l_len + r_len + 1
def show_first(self):
print(self.item, end=' ')
if self.l != None and self.ltag != 1:
self.l.show_first()
if self.r != None and self.rtag != 1:
self.r.show_first()
def show_mid(self):
if self.l != None and self.ltag != 1:
self.l.show_mid()
print(self.item, end=' ')
if self.r != None and self.rtag != 1:
self.r.show_mid()
def show_last(self):
if self.l != None and self.ltag != 1:
self.l.show_last()
if self.r != None and self.rtag != 1:
self.r.show_last()
print(self.item, end=' ')
def create(x):
try:
tmp = next(x)
if tmp == '#':
return
root = Ttree(tmp)
root.llink(create(x))
root.rlink(create(x))
return root
except:
pass
def thread_first(tree): # 先序线索化
pre = None # 前一个节点
tmp = tree # 当前节点
def thread(a): # 定义递归先序访问函数
if a.l != None and a.ltag != 1: # 如果左节点存在，访问左树根节点
nonlocal pre
nonlocal tmp
pre = tmp
tmp = a.l
if tmp.l == None or tmp.ltag == 1: # 如果当前节点左节点不存在，则指向前一个节点，并将tag标为1
tmp.l = pre
tmp.ltag = 1
if pre.r == None or pre.rtag == 1: # 如果前节点右节点不存在，则指向当前节点，并将tag标为1
pre.r = tmp
pre.rtag = 1
thread(tmp) # 递归线索化子树
if a.r != None and a.rtag != 1: # 右节点类似
pre = tmp
tmp = a.r
if tmp.l == None or tmp.ltag == 1:
tmp.l = pre
tmp.ltag = 1
if pre.r == None or pre.rtag == 1:
pre.r = tmp
pre.rtag = 1
thread(tmp)
thread(tree)
def thread_mid(tree): # 中序线索化
pre = None
tmp = None
def thread(a):
nonlocal pre
nonlocal tmp
if a.l != None and a.ltag != 1:
thread(a.l)
pre = tmp
tmp = a
if tmp != None:
if tmp.l == None or tmp.ltag == 1:
tmp.l = pre
tmp.ltag = 1
if pre != None:
if pre.r == None or pre.rtag == 1:
pre.r = tmp
pre.rtag = 1
if tmp.r != None and tmp.rtag != 1:
thread(tmp.r)
thread(tree)
def thread_last(tree): # 后序线索化
pre = None
tmp = None
def thread(a):
nonlocal pre
nonlocal tmp
if a.l != None and a.ltag != 1:
thread(a.l)
if a.r != None and a.rtag != 1:
thread(a.r)
pre = tmp
tmp = a
if tmp != None:
if tmp.l == None or tmp.ltag == 1:
tmp.l = pre
tmp.ltag = 1
if pre != None:
if pre.r == None or pre.rtag == 1:
pre.r = tmp
pre.rtag = 1
thread(tree)
tree_list = ['A', 'B', 'C', '#', '#', 'D', 'E', '#', 'G', '#', '#', 'F', '#', '#', '#']
def travel_first(tree, action): # 先序遍历
tmp = tree
while tmp != None:
while tmp.l != None and tmp.ltag != 1:
action(tmp)
tmp = tmp.l
action(tmp)
tmp = tmp.r
def travel_mid(tree, action): # 中序遍历
def lfirst(node):
tmp = node
while tmp.l != None and tmp.ltag != 1:
tmp = tmp.l
return tmp
def next(node):
if node.rtag == 0 and node.r != None:
return lfirst(node.r)
else:
return node.r
tmp = lfirst(tree)
while tmp != None:
action(tmp)
tmp = next(tmp)
def travel_last(tree, action): # 后序遍历
tmp = tree
stack = LinkStack()
while tmp != None:
while tmp.r != None and tmp.rtag != 1:
stack.add_stack(tmp)
tmp = tmp.r
stack.add_stack(tmp)
tmp = tmp.l
while not stack.is_empty():
action(stack.remove_stack())
root = create(iter(tree_list))
thread_first(root)
print(root.show_first())
print(travel_first(root, print))
root = create(iter(tree_list))
thread_mid(root)
print(root.show_mid())
print(travel_mid(root, print))
root = create(iter(tree_list))
thread_last(root)
print(root.show_last())
print(travel_last(root, print))实现效果：
3、树和森林
3.1 树的存储结构
3.1.1 双亲表示法
这种表示法中，以一组连续的存储单元存储树的结点，每个结点除了数据域data外，还设一个parent域用以指示其双亲结点的位置，其结点形式如下左图所示。右图所示为一棵树及其双亲表示的存储结构。
这种存储结构利用了每个结点（除根以外）只有唯一的双亲的性质。在这种存储结构下，求结点的双亲十分方便，也很容易求树的根，但求结点的孩子时需要遍历整个结构。
3.1.2 孩子表示法
孩子表示法存储普通树采用的是 “顺序表+链表” 的组合结构，其存储过程是：从树的根节点开始，使用顺序表依次存储树中各个节点，需要注意的是，与双亲表示法不同，孩子表示法会给各个节点配备一个链表，用于存储各节点的孩子节点位于顺序表中的位置。如果节点没有孩子结点（叶子结点），则该结点的链表为空链表。
3.1.3 孩子兄弟法
又称为二叉树表示法，或二叉链表表示法，即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibing域，其结点形式如下图所示。
树结构中，位于同一层的节点之间互为兄弟节点。例如，孩子表示法中的普通树，节点 A、B 和 C 互为兄弟节点，而节点 D、E 和 F 也互为兄弟节点。将其用孩子兄弟表示法进行存储的结果如下图所示。
3.2 森林转换成二叉树
从树的二叉链表表示的定义可知，任何一棵与树对应的二叉树，其根结点的右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。这一一对应的关系说明森林或树与二叉树可以相互转换。
树转换为二叉树的步骤是： （１）将树的根节点直接作为二叉树的根节点 （２）将树的根节点的第一个子节点作为根节点的左儿子，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右儿子 （３）将树中的剩余节点按照上一步的方式，依序添加到二叉树中，直到树中所有的节点都在二叉树中
森林转换为二叉树的步骤是： （1）先把每棵树转换为二叉树； （2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。
大作业三：将树和森林转换成二叉树
操作１：普通树转二叉树
对于普通树转二叉树，要记住6个字口诀：左儿子，右兄弟； 实现的大致步骤是这样的： （1）将树的根节点直接作为二叉树的根节点 （2）将树的根节点的第一个子节点作为根节点的左儿子，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右儿子 （3）将树中的剩余节点按照上一步的方式，依序添加到二叉树中，直到树中所有的节点都在二叉树中 提示：这里需要四个类，队列类，普通树节点类，二叉树节点类，普通树转二叉树的类；
操作１测试案例：（左边为普通树，右边为二叉树） （案例１）
（运行结果）
（案例２）
（运行结果）
（案例３）
（运行结果）
操作２：森林转换为二叉树
上面那个任务已经实现了普通树转化为二叉树，而森林是由多棵普通树构成的，因此自然也可以转化为二叉树，其转化方法是： （1）首先将森林中所有的普通树各自转化为二叉树； （2）将森林中第一棵树的树根作为整个森林的树根，其他树的根节点看作是第一棵树根节点的兄弟节点，采用孩子兄弟表示法将所有树进行连接；（这里跟上普通树转二叉树的转换函数有异曲同工之妙，这里就不多解释了，小伙伴们自行思考哈）
操作２测试案例：（上面为森林，下面为要最终实现的二叉树） （案例）
（运行结果）
【注】：小伙伴们必须使用以上测试案例哈，为了方便作业统一，难度稍微有点较高，相信你一定可以的，奥里给！
代码思路（仅供参考，思路不限）：
（1）首先先根据树转二叉树提供的案例的左图，创建一棵普通树，普通树的孩子节点用列表存储（再普通树节点初始化函数实现，比如self.chidren = [node1, node2, node3]）； （2）然后定义一个二叉树节点类和普通树转二叉树的类，创建一个空二叉树对象，将普通树的根结点当作二叉树的根结点； （3）接下来就是最关键的转换函数，这里用到队列，首先定义两个队列，一个存储普通树的节点，一个存储二叉树的节点，然后把各自已确定的根节点存入进去，剩下就是循环遍历了，遍历思路如下； （4）取出普通树节点队列中的首元素，遍历其孩子节点，然后将孩子节点放入队列中，再依次遍历孩子结点，直到没有结点遍历为止；每次都是先从队列中取结点，看是否有孩子结点，如果有，那就加进普通树节点队列中，如果没有就不执行下面for循环，直到所有队列中的结点都取出完时，while循环停止！这里说一下，如果有孩子节点的话，需要根据节点的索引位置，判断其是第一个节点还是后面的节点，然后根据这个依次生成二叉树节点放入二叉树对象中；（这里难度不小，小伙伴们一定要理解原理，多看些相关资料）
代码：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2021/8/18 9:08
# @Author : vaxtiandao
# @File : Tree2BTree.py
class Otree(): # 一般树对象
def __init__(self, item, child=None):
self.item = item # 根节点值
if child == None: # 子节点
self.child = []
else:
self.child = child
def add_child(self, *other): # 添加子节点
for i in other:
self.child.append(i)
def __repr__(self):
return str(self.item) + ':' + str(self.child)
class Tree():
def __init__(self, item):
self.item = item
self.l = None
self.r = None
def llink(self, other): # 左连接子节点
self.l = other
def rlink(self, other): # 右连接子节点
self.r = other
# def __repr__(self):
# return str(self.item)+' '+str(self.l)+' '+str(self.r)
def get_depth(self): # 获取深度（递归）
if self.l == None:
l_depth = 0
else:
l_depth = self.l.get_depth()
if self.r == None:
r_depth = 0
else:
r_depth = self.r.get_depth()
return max(l_depth, r_depth) + 1
def get_len(self): # 获取节点数（递归）
if self.l == None:
l_len = 0
else:
l_len = self.l.get_len()
if self.r == None:
r_len = 0
else:
r_len = self.r.get_len()
return l_len + r_len + 1
def show_first(self): # 先序遍历（递归）
print(self.item, end=' ')
if self.l != None:
self.l.show_first()
if self.r != None:
self.r.show_first()
def show_mid(self): # 中序遍历（递归）
if self.l != None:
self.l.show_mid()
print(self.item, end=' ')
if self.r != None:
self.r.show_mid()
def show_last(self): # 后序遍历（递归）
if self.l != None:
self.l.show_last()
if self.r != None:
self.r.show_last()
print(self.item, end=' ')
def copy(self): # 拷贝节点
c_result = Tree(self.item)
c_result.llink(self.l)
c_result.rlink(self.r)
return c_result
def copy_deep(self): # 深拷贝节点以下整个树
c_result = Tree(self.item)
if self.l != None:
c_result.llink(self.l.copy())
if self.r != None:
c_result.rlink(self.r.copy())
return c_result
def create(x): # 根据列表创建二叉树
try:
tmp = next(x)
if tmp == '#':
return
root = Tree(tmp)
root.llink(create(x))
root.rlink(create(x))
return root
except:
pass
def O2B(otree): # 普通树转二叉树
if otree.child == []: # 如果没有子节点，直接返回一个二叉树对象
return Tree(otree.item)
else: # 有子节点，递归创建二叉树
root = Tree(otree.item) # 根据当前节点数据创建二叉树根节点
for i in range(len(otree.child)): # 对于其子节点
if i == 0: # 第一个子节点创建为左子树
child_cur = O2B(otree.child[i]) # 递归创建二叉树
root.llink(child_cur)
else: # 其他子节点依次创建为前一个子节点的右树
child_pre = child_cur # pre指针向后移动
child_cur = O2B(otree.child[i]) # 根据下一个子节点递归创建二叉树
child_pre.rlink(child_cur) # 新创建的二叉树作为前一个节点的右树
return root
# 创建普通树
B = Otree('B')
C = Otree('C')
D = Otree('D')
A = Otree('A')
A.add_child(B, C, D)
print(A)
tree = O2B(A)
print(tree.show_first())
# 第二个例子
for i in list('ABCDEFGHIJKL'):
exec('%s=Otree("%s")' % (i, i))
B.add_child('E', 'F')
D.add_child('G')
A.add_child('B', 'C', 'D')
print(A)实现效果：
