数据结构与算法-东北林业大学 数据结构演示文稿6[1].ppt

《数据结构与算法-东北林业大学 数据结构演示文稿6[1].ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构主讲：王阿川第六章树和二叉树树的结构定义和基本操作二叉树遍历二叉树和线索二叉树树和森林哈夫曼树及其应用6.1树的结构定义和基本操作定义：Tree=(D,R)关系的特点是一对多树是n(n>=0)个结点的有限集合。AACBDEFKLGHIJM基本述语：结点结点的度叶子(终端结点)分支(非终端)结点树的度孩子双亲兄弟祖先子孙层次堂兄弟深度有序树无序树森林（树也可用森林和树相互递归来定义）ACBDEFKLGHIJM树的基本操作：INITIATE(T)(初始化操作）ROOT(T)/ROOT(x)（求根函数）PARE

2、NT(T,x)（求双亲函数）CHILD(T,x,i)（求孩子函数）RIGHTSIBLING(T,x)（求右兄函数）CRT_TREE(x,F)（建树函数）INS_CHILD(y,i,x)（插入子树操作）DEL_CHILD(x,i)（删除子树操作）TRAVERSE(T)(遍历操作）CLEAR(T)(清空操作）数据结构主讲：王阿川ABDCGHMJIEKLF（a)以嵌套集合的形式表示树(b)以广义表的形式表示树（A（B（E（K，L），F），C（G），D（H（M），I，J）））树的表示形式ABEKLFCGDHMIJ（c)以

3、凹入表示法表示树6.2二叉树定义：Binary_tree=(D,R)特点:结点的度不超过2，孩子有左右之分。ABCDEHFGI二叉树的5种基本形态由3个结点构成的二叉树的5种形态二叉树的基本操作：InitBiTree(&BT)(初始化操作）DestroyBiTree(&T);CreateBiTree(&T,definition);ClearBiTree(&T);BiTreeEmpty(T)BiTreeDepth(T)ROOT(BT)/ROOT(x)（求根函数）Value(T,e)Assign(T,&e,valu

4、e)PARENT(BT,x)（求双亲函数）LeftChild(BT,x)（求左孩子结点函数）RightChild(T,e);LeftSibling(BT,x)（求左兄弟结点函数）RightSibling(T,e);CRT_BT(x,LBT,RBT)（建树函数）InsertChild(BT,y,x)（插入左子树操作）DEL_LCHILD(BT,x)（删除左子树操作）TRAVERSE(BT)(遍历操作）PreOrderTraverse(T,Visit())InOrderTraverse(T,Visit())PostO

5、rderTraverse(T,Visit())LevelorderTraverse(T,Visit())二叉树的基本性质：性质1在二叉树的第i层上至多有2i-1个结点(i1)性质2深度为k的二叉树至多有2k-1个结点(i1)性质3对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则有n0=n2+1满二叉树：深度为k且有2k-1个结点完全二叉树：“去掉”满二叉树最后一层“右边”的若干个结点ABCDEHFGIJKLMNO123456789101112131415数据结构主讲：王阿川二叉树的顺序存储

6、ABCDEFG123456789101112131415ABCDEFGbt结构关系被隐含定位方便操作简单存储器利用率低二叉树的链式存储ABCDEFGA^BC^E^F^^G^^D^btlchilddatarchildlchilddataparentrchild数据结构主讲：王阿川遍历二叉树和线索二叉树遍历：每个元素访问且仅访问一次遍历方法（递归）：1.先序遍历2.中序遍历3.后序遍历ABCDEFG先序:ABDCEGF中序:BDAEGCF后序:DBGEFCA树的二叉链表结构定义：TYPEbitreper=bnode

7、tp;bnodetp=RECORDdata:datatype;lchild,rchild:bitreptrEND;先序遍历根结点指针为bt的二叉树算法：PROCPreorder(bt:bitreptr);IFbtNILTHEN[visite(bt);Preorder(bt.lchild);Preorder(bt.rchild)]END;中序遍历根结点指针为bt的二叉树算法：PROCInorder(bt:bitreptr);IFbtNILTHEN[Inorder(bt.lchild);visite(bt

8、);Inorder(bt.rchild)]END;后序遍历根结点指针为bt的二叉树算法：PROCLastorder(bt:bitreptr);IFbtNILTHEN[Lastorder(bt.lchild);Lastorder(bt.rchild);visite(bt)]END;线索二叉树在结点的空指针域中存储按某种顺序遍历时的“前驱”结点地址和“后继”结点地