数据结构与算法树与叉树

《数据结构与算法树与叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章树与二叉树8/5/20211第4章树与二叉树4.1树的基本概念4.2二叉树4.3二叉树的遍历4.4线索二叉树4.5树和森林4.6哈夫曼树8/5/202124.1树的基本概念4.1.1树的定义及表示树:n个结点的有限集(n>=0)Root树根子树子树8/5/202134.1.2树的常用术语及运算树的结点结点的度---结点拥有的子树的个数叶子结点---度为0的结点，又称终端结点分枝结点---度不为0的结点树的度---树内结点度的最大值树的层次---第一层从根结点开始，根的孩子在第二层，依此类推树的深度---树中结点的最大层次ADEBCFHIGJKM8/5/202144.1.2树的常用

2、术语及运算孩子(结点)---结点的子树的根结点双亲(结点)---结点作为根结点的子树的根结点兄弟(结点)---同一个双亲的孩子结点之间互为兄弟祖先---从根结点到该结点所经分枝上的所有结点子孙---以某结点为根的子树中的任一结点都是该结点的子孙ADEBCFHIGJK8/5/202154.1.2树的常用术语及运算树的基本运算(1)setnull(T):初始化操作，置T为空树。(2)求根结点ROOT(T)或ROOT(x)。求树T的根或求结点x所在的树的根结点。若T是空树或x不在任何一棵树上，则函数值为“空”。(3)求双亲结点RARENT(T,x)。求树T中结点x的双亲结点。若结点x是树T的

3、根结点或结点x不在树T中，则函数值为“空”。(4)求孩子结点CHILD(T,x,i)。求树T中结点x的第i个孩子结点。若结点x是树T的叶子或无第i个孩子或结点x不在树T中，则函数值为“空”。(5)建树creat(x,F)。生成以x结点为根、以森林F为子树森林的树。(6)求右兄弟结点RIGHT_SIBLING(T,x)。求树T中结点x右边的兄弟。若结点x是其双亲的最右边的孩子结点或结点x不在树T中，则函数值为“空”。8/5/202164.1.2树的常用术语及运算树的基本运算(7)插入子树操作addchild(y,i,x)。置以结点x为根的树为结点y的第i棵子树。若原树中无结点y或结点y的

4、子树个数

5、/202194.2.1二叉树的概念二叉树的基本操作：(1)求根结点ROOT(BT)或ROOT(x)。求二叉树BT的根结点或求结点x所在二叉树的根结点。若BT是空树或x不在任何二叉树上，则函数值为“空”。(2)求双亲结点PARENT(BT,x)。求二叉树BT中结点x的双亲结点。若结点x是二叉树BT的根结点或二叉树BT中无x结点，则函数值为“空”。(3)求孩子（左孩子、右孩子）结点LCHILD(BT,x)和RCHILD(BT,x)。分别求二叉树BT中结点x的左孩子和右孩子结点。若结点x为叶子结点或不在二叉树BT中，则函数值为“空”。(4)初始化二叉树setnull(BT)。置BT为空树。(

6、5)建树二叉树CRT_BT(x,LBT,RBT)。生成一棵以结点x为根、二叉树LBT和RBT分别为左、右子树的二叉树。8/5/2021104.2.1二叉树的概念二叉树的基本操作：(6)插入子树（左、右子树）INS_LCHILD(BT,y,x)和INS_RCHILD(BT,y,x)。将以结点x为根且右子树为空的二叉树分别置为二叉树BT中结点y的左子树和右子树。若结点y有左子树／右子树，则插入后是结点x的右子树。(7)删除子树（左、右子树）DEL_LCHILD(BT,x)和DEL_RCHILD(BT,x)。分别删除二叉树中以结点x为根的左子树或右子树。若x无左子树或右子树，则空操作。(8)

7、遍历二叉树TRAVERSE(BT)。按某个次序依次访问二叉树中各个结点，并使每个结点只被访问一次。8/5/2021114.2.2二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。ADEBCFHIGJK20LMNO2122238/5/2021124.2.2二叉树的性质性质2：深度为k的二叉树至多有2k-1个结点(k≥1),最大结点数=20+21+…2K-1=2k-1ADEBCFHIGJKLMNO8/5/2021134.2.2二