清华大学数据结构课件(考研必备)ds2014-chap5-tree.pptx
1第五章树与二叉树数据结构电子教案殷人昆王宏
2IthinkthatIshallneverseeApoemlovelyasatree.——JoyceKilmer(1913)
3第五章树与二叉树树和森林的概念二叉树二叉树遍历二叉树的计数线索化二叉树树与森林堆Huffman树
4树和森林的概念两种树:自由树与有根树。自由树: 一棵自由树Tf可定义为一个二元组 Tf=(V,E) 其中V={v1,...,vn}是由n(n>0)个元素组成的有限非空集合,称为顶点集合。E={(vi,vj)|vi,vj?V,1≤i,j≤n}是n-1个序对的集合,称为边集合,E中的元素(vi,vj〕称为边或分支。
5自由树(未定义根结点)有根树: 一棵有根树T,简称为树,它是n(n≥0)个结点的有限集合。当n=0时,T称为空树;否那么,T是非空树,记作
6r是一个特定的称为根(root)的结点,它只有直接后继,但没有直接前驱;根以外的其他结点划分为m(m?0)个互不相交的有限集合T1,T2,…,Tm,每个集合又是一棵树,并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继。
7树的根本术语子女:假设结点的子树非空,结点子树的根即为该结点的子女。双亲:假设结点有子女,该结点是子女双亲。1层2层4层3层depth=4DACBIJHGFEMLKheight=4
8兄弟:同一结点的子女互称为兄弟。度:结点的子女个数即为该结点的度;树中各个结点的度的最大值称为树的度。分支结点:度不为0的结点即为分支结点,亦称为非终端结点。叶结点:度为0的结点即为叶结点,亦称为终端结点。祖先:某结点到根结点的路径上的各个结点都是该结点的祖先。子孙:某结点的所有下属结点,都是该结点的子孙。
9结点的层次:规定根结点在第1层,其子女结点的层次等于它的层次加1。以下类推。深度:结点的深度即为结点的层次;离根最远结点的层次即为树的深度。1层2层4层3层depth=4DACBIJHGFEMLKheight=4
10高度:规定叶结点的高度为1,其双亲结点的高度等于它的高度加1。树的高度:等于根结点的高度,即根结点所有子女高度的最大值加1。可见,树的高度与深度计算方向相反。有序树:树中结点的各棵子树T0,T1,…是有次序的,即为有序树。无序树:树中结点的各棵子树之间的次序是不重要的,可以互相交换位置。森林:森林是m〔m≥0〕棵树的集合。
11树的抽象数据类型templateclassTclassTree{//对象:树是由n(≥0)个结点组成的有限集合。在//类界面中的position是树中结点的地址。在顺序//存储方式下是下标型,在链表存储方式下是指针//型。T是树结点中存放数据的类型,要求所有结//点的数据类型都是一致的。public:Tree(); ~Tree();positionRoot();//返回根结点地址,假设树为空,返回0
12BuildRoot(constTvalue);//建立树的根结点 positionFirstChild(positionp); //返回p的第一个子女地址,无子女返回0 positionNextSibling(positionp); //返回p的下一兄弟地址,假设无下一兄弟返回0 positionParent(positionp); //返回p的双亲结点地址,假设p为根返回0TgetData(positionp);//返回结点p中存放的值boolInsertChild(positionp,Tvalue);//在结点p下插入值为value的新子女,假设插//入失败,函数返回false,否那么返回true
13boolDeleteChild(positionp,inti); //删除结点p的第i个子女及其全部子孙结//点,假设删除失败,那么返回false,否那么返回true voidDeleteSubTree(positiont);//删除以t为根结点的子树boolIsEmpty();//判树空否,假设空那么返回true,否那么返回falsevo