(清华版)数据结构-count.ppt

,*,Folientitel(Arial 24 fett),Erste Ebene(Arial 22 fett)text text text text text text text text text text text,Erste Ebene ohne Aufz,鋒,lungszeichen(Arial 22 fett)text text text text text text text text text text text,Zweite Ebene(Arial 18 fett)text text text text text text text text text text text,Zweite Ebene ohne Aufz,鋒,lungszeichen(Arial 18 fett)text text text text text text text text text text text text text,Dritte Ebene(Arial 18 normal)text text text text text text text text text text text,*,物料管理,ALDS,*,*,Algorithms and,Data,Strucstures,:Trees,8、树的计数,1、互不相似的二叉树的棵数的计算,实例：,e.g:,当 二叉树的结点个数,n=3,前序序列为 1、2、3,时,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1、进栈,2、进栈,3、进栈,3、出栈,2、出栈,1、出栈,1、进栈,2、进栈,2、出栈,3、进栈,3、出栈,1、出栈,1、进栈,2、进栈,2、出栈,1、出栈,3、进栈,3、出栈,1、进栈,1、出栈,2、进栈,3、进栈,2、出栈,3、出栈,1、进栈,1、出栈,2、进栈,2、出栈,3、进栈,3、出栈,进出栈序列总数的计算为,2,n,个方格中放置 3 个 1 的组合数,不合理的序列总数,e.g:n=3,时，6格放置3个 1 的序列,情况：1 代表进栈，0 表示出栈,1 1 1 0 0 0,1 1 0 0 1 0,1 1 0 1 0 0,1 0 1 1 0 0,1 0 1 0 1 0,0 0 0 1 1 1,1 0 0 1 1 0,合,理,不合理,8、树的计数,1、互不相似的二叉树的棵数的计算,进出栈序列总数的计算为,2,n,个方格中放置,n,个 1 的组合数,不合理的序列总数,e.g:n=3,时，6格放置3个 1 的序列,情况：1 代表进栈，0 表示出栈,1 1 1 0 0 0,1 1 0 0 1 0,1 1 0 1 0 0,1 0 1 1 0 0,1 0 1 0 1 0,0 0 0 1 1 1,1 0 0 1 1 0,合,理,不合理,n=3,时，6 格放置 3 个 1 的序列情况：,3,序列总数,2,3,3 1,不合理的序列总数：,2,3,因此，,n=3,时进出栈序列的总数为：,3 3+1,2,32,3,推广到结点数为,n,时的进出栈序列总数：,nn+1,2,nn+1,