2023年离散数学树知识点总结

第六章树一、掌握基本概念树的子树是互不相交的，树可认为空(空树)非空的树中，只有一个结点是没有前趋的,那就是根。非空树只有一个树根，是一对多的关系。叶子结点、结点的度、树的度、结点的层次、树的深度、树的四种表达方法二、二叉树的定义、特点、五种基本形态二叉树是有序树，左右子树不能互相颠倒二叉树中结点的最大度为２,但不一定都是2。三、二叉树的性质要掌握性质1:二叉树的第i层上至多有2i-1（i1）个结点。性质２:深度为k的二叉树中至多２k－1个结点。性质3：对任何一棵二叉树T,假如其终端结点数为n0，度为2的结点数为n2，则n0＝n2+1。证明：1)结点总数ｎ=ｎ0+n1+ｎ2(n1是度为1的结点数)2）进入分支总数m（每个结点唯一分支进入)n＝m+１3)m个分支是由非叶子结点射出m=n1+２n2性质４：具有n个结点的完全二叉树的深度ｋ为[log2n]+1四、满二叉树和完全二叉树的区别是什么？满二叉树一定是完全二叉树,但是完全二叉树不一定是满二叉树。深度为ｋ的二叉树,最少有k个结点，最多有２k-1深度为ｋ的完全二叉树，最少有2k－1-１+１个结点,最多有2ｋ-1五、二叉树的存储结构(可以通过下标找结点的左右孩子)1.顺序存储结构合用于满二叉树和完全二叉树。（其缺陷是必须把其他二叉树补成完全二叉树，从上到下,从左到右依次存储在顺序存储空间里,会导致空间浪费）2.二叉链表存储结构(其优点是找左孩子和右孩子方便，但缺陷是找父节点麻烦）lchild Ｄaｔａﻩｒｃhｉｌｄ(重点）3.三叉链表存储结构不仅找其左、右孩子很方便，并且找其双亲也方便六、遍历的概念是什么？七、二叉树的遍历有三种：前序(先序、先根）遍历、中序（中序、中根)遍历、后序(后序、后根)遍历１.给出一棵二叉树,要会二叉树的三种遍历2.给出两种遍历(必须有中序遍历)，规定会画该二叉树。八、了解引入线索（中序、先序、后序）二叉树的因素是什么?九、会在二叉树上画先序线索化、中序线索化、后序线索化。在线索二叉树的格式中,可以找到任意结点的直接后继。(错)在线索二叉树中,假如某结点的右孩子为空，那么可以找到该结点的直接后继。（对）在线索二叉树中,假如某结点的左孩子为空,那么可以找到该结点的直接前趋。（对）十、树.森林和二叉树的互相转换树转换成二叉树后，转换后的二叉树根的右子树为空。十一、森林的遍历(只有先序遍历和后序遍历）先序遍历一棵树，相称于先序遍历该树所相应的二叉树。后序遍历一棵树，相称于中序遍历该树所相应的二叉树。十二、赫夫曼树(又称最优二叉树或哈夫曼树）、赫夫曼树编码1.赫夫曼树中，权越大的叶子离根越近，其形态不唯一，但是ＷPL带权途径长度一定是最小。2.一定要会构造哈夫曼树,在构造好的哈夫曼树上会构造哈夫曼编码。(认真看题目规定）第６章算法设计题1.已知二叉树中的结点类型用ＢiTNｏｄe表达，被定义描述为:ＴypｅdefstｒuctBiTNｏｄe{ＴEｌemTｙpedatａ；structBiTNodｅ*ＬＣhild,*RChiｌd；｝BiＴNode,＊ＢｉＴree;其中datａ为结点值域，LChｉld和ＲChild分别为指向左、右孩子结点的指针域，编写出求一棵二叉树高度的算法。InｔBＴreeHeｉght（BiTreeＢＴ）{if(ＢT=＝NＵLＬ）reｔuｒn0；elsｅ{h1=ＢTreｅHeigｈt（BＴ－>LＣhild）；h2=BTrｅeHｅｉght(ＢT->ＲChｉlｄ);if(h１＞h2)reｔｕrn(ｈ1+1);elsｅrｅturn(h２+1)；}}２．已知二叉树中的结点类型用BｉＴＮode表达，被定义描述为：TyｐeｄｅfsｔｒuctBiＴNode{TEleｍＴypedａta;structＢｉTNoｄe*LCｈｉld,*Rchｉld；}BiTＮodｅ,＊ＢiＴrｅe;BiTreeＴ;其中ｄatａ为结点值域,ＬＣｈild和RCｈiｌd分别为指向左、右孩子结点的指针域，编写算法,求出二叉树中２度结点个数。intdｅｇree2nodenｕｍ(BiTreeT）{iｆ(Ｔ){ｉｆ(Ｔ-＞lｃhild！=NULL＆&T->cｈild！=NUＬＬ)cｏｕnt＋+;leafｎｏdenuｍ(l－>lchｉlｄ)；lｅａfnｏdenum(l->ｒchild);}retｕrｎcoｕnt;}3.已知二叉树中的结点类型用ＢiTNode表达，被定义描述为:TｙpeｄefstructBｉTNode{ＴEleｍTｙｐeｄａta；strｕｃtBiTNode*LＣhｉlｄ,*ＲChｉld;}BiTNodｅ,*BiTｒeｅ;BiTreeT;其中data为结点值域,LChiｌd和RChｉｌd分别为指向左、右孩子结点的指针域，写一算法,求出二叉树中的叶子结点个数。ｖｏidBTrｅeLeaｆ(BiTｒeeＢT）｛if（BT){if（BT->LChｉlｄ=＝NULＬ&&ＢＴ->RCｈild==ＮＵLL)count+＋;BＴreeLeaf(BT-＞LChild)；／/访问左子树BTreeLeaf(BＴ->RCｈild);//访问右子树}}或下面算法均可编写递归算法,计算二叉树中叶子结点的数目。ｉnｔLeafCouｎt＿BiTrｅe(BｉtreeＴ)//求二叉树中叶子结点的数目{

iｆ(!T）ｒeturn0；//空树没有叶子

elsｅif(!T－>lchild＆&！T-＞rchild)return１;//叶子结点

elsereturｎLeaf_Coｕｎt(T-＞lｃｈild）+Leaf_Count(T－>rchiｌｄ)；/／左子树的叶子数加上右子树的叶子数}/／LｅａｆCoｕnt_BiＴｒeｅ4．PPT上的三种遍历递归算法和课本上P１31先序递归创建二叉链表。5.给定一棵二叉树，其根指针为rｏｏt。试写出求二叉树结点数目的算法（递归算法或非递归算法）。ﻩ【提醒】采用递归算法实现。ｉntcｏｕnt(ＢｉTｒeｅt）{if(ｔ==NULL)rｅturn０;eｌseretｕrnｃount(t->lchｉlｄ）+ｃounｔ(t->rｃhｉｌｄ)＋1；}6.以二叉链表为存储结构，写一算法互换各结点的左右子树。【分析】依题意，设t为一棵用二叉链表存储的二叉树，则互换各结点的左右子树的运算基于后序遍历实现：互换左子树上各结点的左右子树;互换右子树上各结点的左右子树;再互换根结点的左右子树。【算法】voｉdExchg(BｉTree*t)｛ＢinNｏde＊p;ｉf(t){Ｐ=(*t)-＞lchild；(*ｔ)->ｌchild=(＊ｔ)－＞rｃｈiｌd;(*ｔ）-＞rcｈｉlｄ＝p;Ｅxchg(&(（＊t）－>lchiｌd））;Exｃhg（&（(*t)->ｒchilｄ）);}｝７．已知一棵二叉树采用二叉链表结构存储,每个结点的值为整数类型。规定：给出相应的语言描述，在此基础上设计计算二叉树中所有结点值之和的算法。tyｐedefstruｃｔlｉnｋ｛inｔ