数据结构-数和二叉树

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,数据结构课,件,第,5,章,树和二叉树,本章中主要介绍下列内容：,树的逻辑定义和存储结构,二叉树的逻辑定义、存储结构,二叉树的基本操作算法,树和二叉树的转换,哈夫曼树及其应用,退出,5.1,树,5.2,二叉树,5.3,哈夫曼树及其应用,5.1,树,5.1.1,树的定义和基本运算,1.,定义,树是一种常用的非线性结构。我们可以这样定义：,树,是,n,（,n0,）个结点的有限集合。若,n=0,，则称为,空树,；否则，有且仅有一个特定的结点被称为,根,，当,n1,时，其余结点被分成,m,（,m0,）个互不相交的子集,T1,，,T2,，,.,，,Tm,，每个子集又是一棵树。由此可以看出，树的定义是递归。,图,5_1,K L M,E F G H I J,B C D,A,A,(a),(b),(c),结点,数据元素的内容及其指向其子树根的分支统称为结点。,结点的度,结点的分支数。,终端结点（叶子）,度为,0,的结点。,非终端结点,度不为,0,的结点。,结点的层次,树中根结点的层次为,1,，根结点子树的根为第,2,层，以此类推。,树的度,树中所有结点度的最大值。,树的深度,树中所有结点层次的最大值。,有序树、无序树,如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,森林,是,m,（,m,0,）棵互不相交的树的集合。,在树结构中，结点之间的关系又可以用家族关系描述，定义如下：,孩子、双亲,结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。,子孙,以某结点为根的子树中的所有结点都被称为是该结点的子孙。,祖先,从根结点到该结点路径上的所有结点。,兄弟,同一个双亲的孩子之间互为兄弟。,堂兄弟,双亲在同一层的结点互为堂兄弟。,2.,树的基本运算,常用操作：,（,1,）构造一个树,CreateTree(T),（,2,）清空以,T,为根的树,ClearTree(T),（,3,）判断树是否为空,TreeEmpty(T),（,4,）获取给定结点的第,i,个孩子,Child(T,node,i),（,5,）获取给定结点,typedef st(T,node),（,6,）遍历树,Traverse(T),对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依,5.1.2,树的存储结构,1.,双亲表示法,树的双亲表示法主要描述的是结点的双亲关系。,图,5-3,A,B,D,C,E,F,G,H,I,J,类型定义：,#define MAX_TREE_NODE_SIZE 100,typedef struct ,TEntryType info;,int parent;,ParentNode;,typedef struct,ParentNode itemMAX_TREE_NODE_SIZE;,int n;/,树中当前的结点数目,ParentTree;,这种存储方法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。,算法实现举例：,int Parent(ParentTree T,int node),if(node=T.n)return-2;,else return T.itemnode.parent;,2.,孩子表示法,孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定，所以利用链式存储结构更加适宜。举例：,图,5-4,root,0 A 2 1 4 ,1 C ,2 B 3 5 ,3 E ,4 D 6 ,5 F ,6 G 7 8 9 ,7 H ,8 I ,9 J ,在,C,语言中，这种存储形式定义如下：,#define MAX_TREE_NODE_SIZE 10,typedef struct ChildNode,int child;/,该孩子结点在一维数组中的下标值,struct ChileNode*next;/,指向下一个孩子结点,CNode;,typedef struct,TEntryType info;/,结点信息,CNode*firstchild;/,指向第一个孩子结点的指针,TNode;,typedef struct,TNode itemMAX_TREE_NODE_SIZE;,int n,root;,/n,为树中当前结点的数目，,root,为根结点在一维数组中的位置,ChildTree;,这种存储结构的特点是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以，在必要的时候，可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域,parent,，用来指示结点的双亲在一维数组中的位置。,