树与二叉树
1.线性结构和非线性结构
线性结构的所有元素都是线性排列的,结构中必然存在唯一的“起点”和“终点”元素。且除首尾元素外,都有且只有一个“前驱”和“后驱”节点。
非线性结构则完全相反,结构中可能存在多个“起点”和“终点”元素。所有节点都可能存在0个或多个“前驱”和“后继”节点。
2.树形结构
树可以描述为由n(n>=0)个节点构成的一个有限集合,以及在该集合上定义的一种节点关系。
树形结构是一种特殊的非线性结构,其特点是:只有一个没有“前驱”,只有“后继”的根节点。有多个只有“前驱”没有“后继”的叶子节点,其余节点均只有一个“前驱”和多个“后继”。
3.描述树形结构的词
1)度(Degree):
一个节点拥有的子树(后继节点)的个数称之为该节点的度,一棵树中最大的度称之为树的度。
2)节点(Node):
没有前驱的节点称为根节点或开始节点;没有后驱的节点称为叶子节点或终端节点。
树中度不为0的节点称为分支节点,除根节点之外的分支节点称为内部节点。
节点间的前驱和后驱关系也称之为父子关系。
3)层数(Level):
节点的层数从根节点开始计算,根节点的层数为1。树中节点最大层数称为树的高度或深度(Depth)
4.二叉树
二叉树是树形结构的一种特殊情况,其最大度为2。
1)完全二叉树和满二叉树
满二叉树:所有节点度为2或0;所有叶子节点在同一层
完全二叉树:最多只有最下两层度小于0;最下一层的叶子节点都在最左边。
2)二叉树的性质
二叉树第k层上最多有2k-1个节点(K>=1);
深度为k的二叉树最多有2k-1个节点(k>=1);
度为2的节点个数(n0)和度为0的节点个数(n2)满足n0=n2+1的关系;
3)二叉树的遍历:前序遍历(根左右),中序遍历(左根右),后序遍历(左右根)
#二叉树的实现方式
<---这是用来举例的二叉树
#1.数组实现
#用数组实现二叉树,从根节点开始,从上而下,从左到右存储
#非完全二叉树需先补全为为完全二叉树后存储
#而又基于数组定义(元素数据类型相同),空节点用''空字符填充
tree_s = ['A','B','C','','D','','E']
#2.链表实现
#用链表实现二叉树,头指针指向根节点
#节点格式:[左子树指针,值域,右子树指针]
tree_item_head = 0
tree_item = [[1,'A',2],[-1,'B',3],[-1,'C',4],[-1,'D',-1],[-1,'E',-1]]
#3.列表实现
#用列表实现二叉树格式[节点名称,左子树,右子树]
tree_list = ['A',['B',None,['D',None,None]],['C',None,['E',None,None]]]
#4.类实现
class node:
def __init__(self,value,left=None,right=None):
self.value = value
self.left = left
self.right = right
class tree:
def __init__(self):
self.root = None
def bulid(self,data):#假装这里有个建立二叉树的方法
def preTraverse(self,p): #前序遍历
if p is None:
return
print(p.value,end=',')
self.preTraverse(p.left)
self.preTraverse(p.right)
def midTraverse(self,p): #中序遍历
if p is None:
return
self.midTraverse(p.left)
print(p.value,end=',')
self.midTraverse(p.right)
def afterTraverse(self,p): #后序遍历
if p is None:
return
self.afterTraverse(p.left)
self.afterTraverse(p.right)
print(p.value,end=',')
import random
t = tree()
list1 = [];n=0
while n<10:
r = random.randint(0,99)
if r not in list1:
list1.append(r)
t.build(r) #提纲上没有,我自己瞎写了一个
n+=1
print(r,end=',')
t.preTraverse(t.root)
t.midTraverse(t.root)
t.afterTraverse(t.root)
#基于数组存储二叉树的遍历
tree_s = ['A','B','C','','D','','E']
#前提:父节点f和子节点c的索引关系:c=2*f+1
#1.前序遍历
def preTraverse(tree_s,p):
f=p;c=f*2+1
print(tree_s[f],end=',') #输出父节点
if c preTraverse(tree_s,c)
if c+1 preTraverse(tree_s,c+1)
preTraverse(tree_s,0)
def midTraverse(tree_s,p):
f=p;c=f*2+1
if c midTraverse(tree_s,c)
print(tree_s[f],end=',') #输出父节点
if c+1 midTraverse(tree_s,c+1)
midTraverse(tree_s,0)
def afterTraverse(tree_s,p): #后序遍历
f=p;c=f*2+1
if c afterTraverse(tree_s,c)
if c+1 afterTraverse(tree_s,c+1)
print(tree_s[f],end=',') #输出父节点
afterTraverse(tree_s,0)