数据结构递归树课件.ppt

《数据结构递归树课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、部分地包含自身，直接或间接地调用自身定义递归：longFactor(longn){if(n==0)return1;elsereturnn*Factor(n-1);}参数计算返回00！=11参数计算返回11*Factor(0)参数计算返回22*Factor(1)参数计算返回33*Factor(2)主程序main()32101266数据结构递归:typedefstructtNode{Elemtypedata;tNode*next;}tNode,*link;tNodenewnode;linklist;树n个结点的有限集合,n>1,T:1.一个根结点root2.1245

2、673n=0n=11abdefgc树的术语结点=数据项+分枝结点的度叶、分支、子女、双亲、兄弟祖先、子孙结点所处层次树的高度树的度有序树、无序树森林abdefgcadg二叉树n个结点的集合，T：,n=0T左+T右，n>0T=(a)空二叉树AABABACB(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)2453671当i=1时，只有一个根结点，2i-1=20=1,命题成立。对于j=i-1,假定命题成立，则第j层上至多有2j-1个结点，故第j+1层上最多有2j-1*2即2j个结点，

3、即第i层上最多有2i-1个结点。证毕。性质3：对任何一棵二叉树，如果其叶结点数n0，度为2的结点数为n2，则n0＝n2＋1。性质2：深度为k的二叉树至多有2k－1个结点（k>=1).证明：设二叉树中度为1的结点数为n1，有：N＝n0＋n1＋n2(1)设B为二叉树中的分支总数，则有B=N-1，同时B=n1+2n2,于是有N=n1+2n2-1(2)故n0＝n2＋12453671满二叉树:深度为k且共有2k-1个结点12345612345712367(a)完全二叉树(b)非完全二叉树(c)非完全二叉树2453671完全二叉树叶结点出现在最高或次高层对于任意结点,如果C(Tr)=

4、s,则C(Tl)=s或s+1性质4具有n个结点的完全二叉树深度为123452k-1－11，则双亲【i/2】;2)2i>n，则i为叶子；否则，其左孩子是2i;3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。123456123452453671遍历二叉树2453671LDRDLR——先（根）序遍历LDR——中（根）序遍历LRD——后（根）序遍历二叉树表达式(a+b*(c-d)-e/f)－＋*a/b-

5、dcfe其先序序列为：-+a*b-cd/ef其中序序列为：a+b*c-d-e/f其后序序列为：abcd-*+ef/-链式存储typedefstructBiTNode{Elemtypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreate(BiTreeT){charch;cin>>ch;if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))cout<<"Error!";T->data=ch;T->lchild=Create

6、(T->lchild);T->rchild=Create(T->rchild);}returnT;}ABC##DE#G##F###T^^^^^^^^-+a##*b##-c##d##/e##f##－＋*a/b-dcfe前序遍历voidPreorder(BiTreeT){if(T){cout<data;Preorder(T->lchild);Preorder(T->rchild);}}－＋*a/b-dcfe叶结点个数intSumleaf(BiTreeT){intsum=0,m,n;if(T){if((!T->lchild)&&(!T->rchild))sum++;m=

7、Sumleaf(T->lchild);sum+=m;n=Sumleaf(T->rchild);sum+=n;}returnsum;}－＋*a/b-dcfeintDepth(BiTreeT){intdep=0,depl,depr;if(!T)dep=0;else{depl=Depth(T->lchild);depr=Depth(T->rchild);dep=1+(depl>depr?depl:depr);}returndep;}－＋*a/b-dcfe树的深度线索化二叉树^^^^^^中序遍历BDAEC^^中序遍历BDAEC^^树的