资源描述：
《数据结构树与二叉树6.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章 树与二叉树第一节树的基本概念1>定义：树是n(n>=0)个结点组成的有限集。n=0称为空树;n>=1则树是由一个根结点和互不相交的子树构成。AABCDEFGIJHtreetreetree=Nulln=0n=1n=10（1）（2）（3）（3）中有10个结点，可以看成一个根结点和三棵子树构成。子树仍然满足树的定义。22>基本概念结点的度:结点拥有子树的数目叶结点:结点的度为零的结点分枝结点:结点的度非零的结点树的度:树中各结点度的最大值孩子:j,k,l称为i的孩子双亲:i称为j,k,l的双亲兄弟:j,k,l互为兄弟祖先:树的根结
2、点到某结点j路径上的所有结点,为结点j的祖先子孙:结点i下的所有结点,称为结点i的子孙结点层次:从根结点到某结点j路径上结点的数目ijkl3树的深度:树中结点的最大层次有序树:若树中结点的各子树从左到右是有次序的,称该树为有序树,否则为无序树森林:由m棵互不相交的树构成F=(T1,T2,.......Tm)森林可以通过虚设一根结点连成一棵树T=(root,F)rootBCDEFGIJHF43>树的基本操作initial(T)初始化root(T)返回根结点parent(T,x)返回结点x的双亲child(T,x,i)返回结点x的第i个
3、孩子crt_tree(x,F)生成一棵以x为根,F为子树的树ins_child(T,y,i,x)把x插入到y的第i棵子树处del_child(T,y,i)删除结点y的第i棵子树traverse(T)遍历clear(T)清除5第二节二叉树1>定义：二叉树是n(n>=0)个结点组成的有序树,每个结点至多有二棵子树,称为左子树和右子树，n=0称为空树。ABtreeABtreeBtree=NullABtreeABtree62>二叉树的基本操作initial(BT)初始化root(BT)返回根结点parent(BT,x)返回结点x的双亲lch
4、ild(BT,x)返回结点x的左孩子rchild(BT,x)返回结点x的右孩子crt_bt(x,LBT,RBT)生成一棵以x为根,LBT,RBT为子树的树ins_lchild(BT,y,x)把x作为y的左子树插入ins_rchild(BT,y,x)把x作为y的右子树插入del_lchild(BT,y)删除结点y的左子树del_rchild(BT,y)删除结点y的右子树traverse(BT)遍历clear(BT)清除73>二叉树的性质性质1:在二叉树的i层上至多有2i-1个结点。(归纳法证明)性质2:深度为k的二叉树,至多有2k-1
5、个结点。(等比求和)性质3:对任意二叉树BT,若叶结点数为n0,度为2的结点数为n2,则n0=n2+1证明:∵n=n0+n1+n2(n为结点总数)b=n1+2n2(b为分支总数)b=n-1(除根结点外,任一结点都有一分支连入)∴n=n1+2n2+1代入第一等式,得:n0=n2+1证毕8定义:深度为k且有2k-1个结点的二叉树称为满二叉树1234567定义：深度为k且有n个结点的二叉树，当且仅当n个结点都满足满二叉树的位置编号的升序排列结构时，称为完全二叉树结点左上角的数字为满二叉树的位置编号123459性质4：具有n个结点的完全二叉
6、树深度为log2n+1性质5：对结点数为n的完全二叉树，第i个结点有如下特征：(1)若i=1则i为根结点，无双亲若i>1则双亲为parent(i)=i/2；(2)若2i>n则i无孩子,为叶结点否则lchild(i)=2i；(3)若2i+1>n则i无右孩子否则rchild(i)=2i+1。104>二叉树的存储结构(1)顺序存储结构分配2k-1个空间结点按满二叉树编号存储物理位置确定了结点间的关系abcd12345e67例如:abcde123456711(2)链式存储结构lchilddatarchildlchilddataparentr
7、child二叉结构三叉结构例如:a^^b^c^abcda^b^c^^c^^d^12第三节二叉树的遍历ABtree根左子树右子树非空二叉树可看成三部分组成:根左子树右子树左子树和右子树仍然是二叉树.遍历的访问顺序有三种:1>先序访问:根左子树右子树2>中序访问:左子树根右子树3>后序访问:左子树右子树根13123456先序:124536中序:425136后序:452631例如:14Voidpreorder(bt){if(bt){visit(bt->data);preorder(bt->lchild);preorder(bt->rchi
8、ld);}}Voidinorder(bt){if(bt){inorder(bt->lchild);visit(bt->data);inorder(bt->rchild);}}Voidpostorder(bt){if(bt){posto
