考研 期末 数据结构 第六章_树和二叉树.ppt

第六章 树和二叉树 Status PreOrderTraverse( BiTreee T, Status ( * Visit)(TElemType e) ) { //采用二叉链表存储结构， Visit是对数据元素操作的应用//函数，先序遍历二叉树T的递归算法，对每个数据元素调用//函数Visit。最简单的Visit函数是： // Status PrintElement(TElemType e){ //输出元素e的值 // printf( e ); //实用时，加上格式串 // return OK; // } //调用实例： PreOrderTraverse( T, PrintElement); if (T) { if (Visit(T-data )) if (PreOrderTraverse(T-lchild, Visit)) if (PreOrderTraverse(T-rchild, Visit)) return OK; return ERROR; }else return OK; }// PreOrderTraverse Status InOrderTraverse( BiTreee T, Status ( * Visit)(TElemType e) ) { //采用二叉链表存储结构， Visit是对数据元素操作的应用 //函数。中序遍历二叉树T的非递归算法，对每个数据元素调用//函数Visit。 InitStack(S); Push(S,T); //根指针进栈 while (! StackEmpty(S)) { while (GetTop(S,p)) p) Push(S,p-lchild); //向左走到尽头 Pop(S,p); //空指针退栈 if (!StackEmpty(S)) { //访问结点，向右一步 Pop(S,p); if( !Visit(p-data)) return ERROR; Push(S,p-rchild); }//if }//While return OK; }// InOrderTraverse Status InOrderTraverse( BiTreee T, Status ( * Visit)(TElemType e) ) { //采用二叉链表存储结构， Visit是对数据元素操作的应用//函数。中序遍历二叉树T的非递归算法，对每个数据元素调 //用函数Visit。 InitStack(S); p=T; while (p|| !StackEmpty(S)) { if (p) {Push(S,p); p=p-lchild); //根指针进栈，遍历左子树 else{ //根指针退栈，访问根结点，遍历右子树 Pop(S,p); if( !Visit(p-data)) return ERROR; p=p-rchild }//else }//While return OK; }// InOrderTraverse Status CreateBiTree( BiTreee T ) { //按先序次序输入二叉树中结点的值（一个字符），空 //字符表示空树。构造二叉链表表示的二叉树T。 scanf(ch); if (ch==‘ ’) T=NULL; else{ if( !(T=(BiTNode * )malloc(sizeof(BiTNode)))) exit(OVERFLOW); T-data=ch; //生成根结点 CreateBiTree(T-lchild); //构造左子树 CreateBiTree(T-rchild); //构造右子树 } return OK; }// CreateBiTree 4、建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的建立算法。 6.6 赫夫曼树及其应用 //－－－－赫夫曼树和赫夫曼编码的存储表示－－－－ typedef struct { unsigned int weight ; unsig