找到
1
篇与
树
相关的结果
-
树与二叉树 1.线性结构和非线性结构线性结构的所有元素都是线性排列的，结构中必然存在唯一的“起点”和“终点”元素。且除首尾元素外，都有且只有一个“前驱”和“后驱”节点。非线性结构则完全相反，结构中可能存在多个“起点”和“终点”元素。所有节点都可能存在0个或多个“前驱”和“后继”节点。2.树形结构树可以描述为由n（n>=0）个节点构成的一个有限集合，以及在该集合上定义的一种节点关系。树形结构是一种特殊的非线性结构，其特点是：只有一个没有“前驱”，只有“后继”的根节点。有多个只有“前驱”没有“后继”的叶子节点，其余节点均只有一个“前驱”和多个“后继”。3.描述树形结构的词1)度（Degree）：一个节点拥有的子树（后继节点）的个数称之为该节点的度,一棵树中最大的度称之为树的度。2)节点（Node）：没有前驱的节点称为根节点或开始节点；没有后驱的节点称为叶子节点或终端节点。树中度不为0的节点称为分支节点，除根节点之外的分支节点称为内部节点。节点间的前驱和后驱关系也称之为父子关系。3)层数（Level）:节点的层数从根节点开始计算，根节点的层数为1。树中节点最大层数称为树的高度或深度（Depth）。1.二叉树二叉树是树形结构的一种特殊情况，其最大度为2。1)完全二叉树和满二叉树满二叉树：所有节点度为2或0；所有叶子节点在同一层完全二叉树：最多只有最下两层度小于0；最下一层的叶子节点都在最左边。2)二叉树的性质二叉树第k层上最多有2k-1个节点（K>=1）；深度为k的二叉树最多有2k-1个节点（k>=1）；度为2的节点个数（n0）和度为0的节点个数（n2）满足n0=n2+1的关系；3)二叉树的遍历：前序遍历（根左右），中序遍历（左根右），后序遍历（左右根）2.二叉树的实现方式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 = right5)树类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)6.基于数组存储二叉树的遍历tree_s = ['A','B','C','','D','','E'] #前提：父节点f和子节点c的索引关系：c=2*f+1 def preTraverse(tree_s,p): #前序遍历 f=p;c=f*2+1 print(tree_s[f],end=',') #输出父节点 if c<len(tree_s) and tree_s[c] != '': preTraverse(tree_s,c) if c+1<len(tree_s) and tree_s[c+1] != '': preTraverse(tree_s,c+1) preTraverse(tree_s,0) def midTraverse(tree_s,p): #中序遍历 f=p;c=f*2+1 if c<len(tree_s) and tree_s[c] != '': midTraverse(tree_s,c) print(tree_s[f],end=',') if c+1<len(tree_s) and tree_s[c+1] != '': midTraverse(tree_s,c+1) midTraverse(tree_s,0) def afterTraverse(tree_s,p): #后序遍历 f=p;c=f*2+1 if c<len(tree_s) and tree_s[c] != '': afterTraverse(tree_s,c) if c+1<len(tree_s) and tree_s[c+1] != '': afterTraverse(tree_s,c+1) print(tree_s[f],end=',') afterTraverse(tree_s,0)
