首页 > 编程学习 > 树和森林基础

树和森林基础

发布时间:2022/11/11 14:57:29

目录

一、树的基本概念 

二、结点之间的关系描述 

三、结点、树的属性描述 

 四、有序树,无序树和森林

 五、树的常考性质


 

一、树的基本概念 

 

  • 树:从树根生长,逐级分支
  • 空树:结点数为0的树 
  • 非空树的特性:

1.有且仅有一个根节点 
2.没有后继的结点称为“叶子结点”(或终端结点) 
3.有后继的结点称为“分支结点”(或非终端结点)
4.除了根节点外,任何一个结点都且仅有一个前驱
5.每个结点可以有0个或多个后继

  • 树是n(n>=0)个结点的有限集合,n=0时,称为空树,这是一种特殊情况。在任意一颗非空树中应满足: 

1.有且仅有一个特定的称为根的结点
2.当n>1的时候,其余结点可分为m(m>0)个互不相干的有限集合T1,T2...Tm,其中每个集合本身又是一颗树,并且称为
根结点的子树。 

 

二、结点之间的关系描述 

 

  • 祖先结点:是从根到该结点所经分支上的所有结点

上图中,“你”结点的祖先结点有“父亲”,“爷爷”
“M”结点的祖先结点有“H”,“三叔”,“爷爷”

  • 子孙结点:以某结点为根的子树中任一结点都称为该结点的子孙。

上图中,“父亲”结点的子孙结点有“你”,“K”,“L”和“F”

  • 双亲结点(父结点):一个结点的直接前驱是它的父结点

上图中,“你”的双亲结点是“父亲”

  • 孩子结点:一个结点的直接后继就是它的孩子结点

上图中,“你”结点,“F”结点都是“父亲”结点的孩子结点

  • 兄弟结点:由同一个结点得到的其它结点且位于同一层的结点是兄弟结点

上图中,“父亲”结点,“二叔”结点和“三叔”结点之间是兄弟的关系,所有可以说“二叔”结点是“父亲”结点的
兄弟结点

  • 堂兄弟结点:其双亲在同一层的结点互为堂兄弟
  • 两个结点之间的路径:该路径是单向的,且只能从上往下
  • 路径长度:指经过了几条边 

三、结点、树的属性描述 

  • 结点的层次(深度)--从上往下数

“爷爷”结点位于第一层,“父亲”,“二叔”和“三叔”位于第二层...

  • 结点的高度--从下往上数

“K”,“L”和“M”三个结点的高度都是为1;....;“父亲”,“二叔”和“三叔”三个结点的高度都是3...

  • 树的高度(深度)--总共多少层

上图中,树的高度为4

  • 结点的度--有几个孩子(分支)

上图中,“父亲”结点有两个分支,所以它的度为2;“二叔”结点有一个分支,所以它的度为1;“K”结点没有分支,所以它的度为0

  • 树的度--各结点的度的最大值

上图中,“三叔”结点的分支最多为3,所有树的度为3 

 四、有序树,无序树和森林

  • 有序树--从逻辑上看,树中结点的各子树从左至右是有次序的,不能互换
  • 无序树--从逻辑上看,树中结点的各子树从左至右是无次序的,可以互换
  • 注意:具体要看你用树存什么,是否需要用结点的左右位置反映某些逻辑关系 
  • 森林是m(m>=0)棵互不相交的树的集合。
  • 结点的度--结点有几个孩子 

 

 五、树的常考性质

  • 考点1:结点数=各结点的度数和(总度数)+1 

比如“A”结点的度数为3(3相当于第2层的结点个数);“B”结点的度数为2,“C”结点的度数为1,“D”结点的度数为3,那么2+1+3=6(相当于是第3层的结点个数);“E”结点的度数为2,“H”结点的度数为1,那么2+1=3(相当于是第4层的结点个数)

各结点的总度数=第2层结点数+第3层结点数+....
所以结点数=总度数+1 

  • 考点2:度为m的树,m叉树的区别

 树的度--各结点的度的最大值;m叉树--每个结点最多只能有m个孩子的树

 

  • 考点3:度为m的树第i层至多有m^(i-1)个结点(i>=1)

m叉树第i层至多有m^(i-1)个结点 

 

  •  考点4:高度为h的m叉树至多有((m^h)-1)/(m-1)个结点

分析:高度为h---意味着该树有h层;m叉树---意味着每个结点最多只能有m个孩子
计算该树最多的结点数目的时候:第1层有m^0=1个结点;第2层有m个结点,第3层:第2层的第1个结点有m个结点(对应第3层有m个结点),第3层的第2个结点有m个结点(对应第3层有m个结点)+.....,一共有m个m,也就是m^2,所以第3层有m^2个结点;第4层有m^2个m的结点,也就是m^3个结点.....第n=h层有m^(h-1)个结点。
最多的结点数:1+m+m^2+....+m^(h-1)=(1-m^h)/(1-m)

 

  •  考点5:高度为h的m叉树至少有h个结点;高度为h,度为m的树至少有h+m-1个结点

对于第一种:可以让第1层到第h层都是1个结点。
对于第二种:度为m---意味着有一个结点必须有m个孩子,那么可以让第1层到第h-1层都是一个结点,第h层有m个结点此时共有h-1+m个结点 

 

 

 

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式