《树和二叉树》ppt课件

《《树和二叉树》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树和线索二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换6.4.3树和森林的遍历6.5赫夫曼树及其应用6.5.1最优二叉树(赫夫曼树)6.5.2赫夫曼编码16.1树的定义和基本术语树是一类重要的非线性数据结构，是以分支关系定义的层次结构。树的递归定义：树(Tree)是n(n>=0)个结点的有限集。当n=0时,是一棵空树。当n>0时

2、,(1)有且仅有一个特定的称为根(Root)的结点；(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...,Tm,其中每个集合本身又是一棵树。称为子树(SubTree)。2A只有根结点的树ABCDEFGHIJKLM有子树的树根子树3T={A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P}T1={B,C,D,E,F}T11={C,D,E}T111={D}T112={E}T12={F}T2={G,H}T21={H}T3={I,J,K,L,M,N,O,P}T31={J,K,L,M,N}T32

3、={O}T33={P}T311={K}T312={L}...JCFHIGBAEMKPLODN树TCFBEDT1HGT2例：有16个结点的树。JIMKPLONT341.树型表示法：2.嵌套集合表示法：ABCDABCD3.广义表表示法：(A(B(D),C))4.凹入表示法：树的表示法ABDC5基本术语结点(Node)——表示树中的元素，包括数据项及若干指向其子树的分支。结点的度(Degree)——结点拥有的子树数。叶子或终端节点(Leaf)——度为0的结点。非终端节点或分支结点——度不为0的结点。孩子(Child)——结点子树的

4、根称为该结点的孩子。双亲(Parents)——孩子结点的上层结点叫该结点的双亲。兄弟(Sibling)——同一双亲的孩子。树的度——一棵树中最大的结点度数。结点的祖先——从根到该结点所经分支上的所有结点。结点的子孙——以某结点为根的子树中的任一节点。结点的层次(Level)——从根结点算起，根为第一层，它的孩子为第二层……堂兄弟——双亲在同一层上的结点互为堂兄弟。树的深度或高度(Depth)——树中结点的最大层次数。森林(Forest)——m(m0)棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给

5、森林增加一个统一的根结点，森林就变成一棵树。ABCDEFGHIJKLM6任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林。ABCDEFGHIJKLM7ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G互为堂兄弟结点A是结点F，G的祖先8有序树与无序树：树中

6、结点的各子树从左至右是有次序的（不能互换）则称该树为有序树，否则称该树为无序树。因此，有序树和无序树的区别在于：子树之间是否存在次序关系。BAFECGBADFC有序树T1有序树T2EGBADFECGBADFCEGD无序树T1无序树T19树结构和线性结构的比较：线性结构树结构(1)第一个数据元素根结点(无前驱)(无前驱)(2)最后一个数据元素多个叶子结点(无后继)(无后继)(3)其它数据元素树中其它结点(一个前驱、一个后继)(一个前驱、多个后继)10ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D

7、为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。基本操作P（15个）：查找（8个）：Root(T);Value(T,cur_e);Parent(T,cur_e);LeftChild(T,cur_e);RightSibling(T,cur_e);TreeEmpty(T);TreeDepth(T);TraverseTree(T,Visit());插入（4个）

8、：InitTree(&T);CreateTree(&T,definition);Assign(T,cur_e,value);InsertChild(&T,&p,i,c);删除（3个）：ClearTree(&T);DeleteChild(&T,&p,i);DestroyTree(&T);}A