数据结构C版学习教案

1、会计学1数据结构数据结构(sh j ji u)课件课件C版版第一页，共69页。2022-5-9驱；根以外的其他结点划分为驱；根以外的其他结点划分为m (m 0) 个互不相交的有限集个互不相交的有限集合合T1, T2, , Tm，每个集合又，每个集合又是一棵树，并且称之为根的子是一棵树，并且称之为根的子树。树。00n,T,.,T,Tr,n,Tm21第1页/共69页第二页，共69页。2022-5-9最大值称为树的度。n分支结点：度不为0的结点即为分支结点，亦称为非终端结点。第2页/共69页第三页，共69页。2022-5-9第3页/共69页第四页，共69页。2022-5-9第4页/共69页第五页，共

2、69页。2022-5-9第5页/共69页第六页，共69页。2022-5-90,0nTTrnTRL第6页/共69页第七页，共69页。2022-5-9第7页/共69页第八页，共69页。2022-5-9第8页/共69页第九页，共69页。2022-5-9第9页/共69页第十页，共69页。2022-5-9第10页/共69页第十一页，共69页。2022-5-9n i , 且且i != 1, 弟为弟为i-1；n若若 i 为偶数为偶数, 且且i != n, 则其右兄则其右兄弟为弟为i+1；n结点结点i 所在的层次为所在的层次为log2i+1第11页/共69页第十二页，共69页。2022-5-9第12页/共69

3、页第十三页，共69页。2022-5-9第13页/共69页第十四页，共69页。2022-5-9第14页/共69页第十五页，共69页。2022-5-9第15页/共69页第十六页，共69页。2022-5-9第16页/共69页第十七页，共69页。2022-5-9二叉树的链表表示(biosh)第17页/共69页第十八页，共69页。2022-5-9n TElemType data;n struct TriTNode *lchild, *rchild; / 左右孩子指针n struct TriTNode *parent; /双亲指针n TriTNode, *TriTree;基于二叉树的二叉链表存储表示(bi

4、osh)的基本操作的函数原形见教材p127第18页/共69页第十九页，共69页。2022-5-9第19页/共69页第二十页，共69页。2022-5-9第20页/共69页第二十一页，共69页。2022-5-9 / printf( e ); / 实用时，加上格式串 / return OK; / / 调用(dioyng)实例：PreOrderTraverse(T, PrintElement);第21页/共69页第二十二页，共69页。2022-5-9 / PreOrderTraverse第22页/共69页第二十三页，共69页。2022-5-9n/法，对每个数据元素调用函数Visit。n第23页/共69

5、页第二十四页，共69页。2022-5-9 Push(S, p-rchild); return OK; / InOrderTraverse第24页/共69页第二十五页，共69页。2022-5-9第25页/共69页第二十六页，共69页。2022-5-9 return OK; / InOrderTraverse第26页/共69页第二十七页，共69页。2022-5-9第27页/共69页第二十八页，共69页。2022-5-9第28页/共69页第二十九页，共69页。2022-5-9第29页/共69页第三十页，共69页。2022-5-9第30页/共69页第三十一页，共69页。2022-5-9第31页/共69

6、页第三十二页，共69页。2022-5-9第32页/共69页第三十三页，共69页。2022-5-9第33页/共69页第三十四页，共69页。2022-5-9 第34页/共69页第三十五页，共69页。2022-5-9第35页/共69页第三十六页，共69页。2022-5-9/ 左右标志左右标志 BiThrNode, *BiThrTree;第36页/共69页第三十七页，共69页。2022-5-9线索二叉树-通过中序遍历(bin l)建立中序线索化二叉树第37页/共69页第三十八页，共69页。2022-5-9第38页/共69页第三十九页，共69页。2022-5-9 pre-RTag = Thread; p

7、re-rchild = p; pre = p; / 保持pre指向p的前驱(qinq) InThreading(p-rchild); / 右子树线索化 / InThreading第39页/共69页第四十页，共69页。2022-5-9rchild!=T) p = p-rchild; Visit(p-data); / 访问(fngwn)后继结点 p = p-rchild; / p进至其右子树根 return OK; / InOrderTraverse_Thr第40页/共69页第四十一页，共69页。2022-5-9后继为右子女结点后继为当前结点右子树的中序下的第一个结点！=NULL无后继无此情况=N

8、ULL=1=0RTagrchild第41页/共69页第四十二页，共69页。2022-5-9前驱为左子女结点前驱为当前结点左子树中序下的最后一个结点！=NULL无前驱无此情况=NULL=1=0LTaglchild第42页/共69页第四十三页，共69页。2022-5-9第43页/共69页第四十四页，共69页。2022-5-9第44页/共69页第四十五页，共69页。2022-5-9第45页/共69页第四十六页，共69页。2022-5-9ntypedef struct /n CTBox nodesMAX_TREE_SIZE;n int n, r; / 结点数和根结点的位置n CTree;第46页/共6

9、9页第四十七页，共69页。2022-5-9一结点在存储(cn ch)时总是有顺序的。第47页/共69页第四十八页，共69页。2022-5-9第48页/共69页第四十九页，共69页。2022-5-9第49页/共69页第五十页，共69页。2022-5-9第50页/共69页第五十一页，共69页。2022-5-9第51页/共69页第五十二页，共69页。2022-5-9第52页/共69页第五十三页，共69页。2022-5-9第53页/共69页第五十四页，共69页。2022-5-9第54页/共69页第五十五页，共69页。2022-5-9第55页/共69页第五十六页，共69页。2022-5-9外其他树组成的森林(snln)T2, ., Tm。第56页/共69页第五十七页，共69页。2022-5-9第57页/共69页第五十八页，共69页。2022-5-9第58页/共69页第五十九页，共69页。2022-5-9niiPL12log332222110第59页/共69页第六十页，共69页。2022-5-9niiPL12logniiilwWPL1第60页/共69页第六十一页，共69页。2022-5-9第61页/共69页第六十二页，共69页。2022-5-9第62页/共69页第六十三页，共69页。2022-5-94.23(zhdo)F棵树为止，这棵树为Huffman树。第63