线性结构第六章.doc

算法实现相关数据类型头文件完整C语言实现可执行文件算法6.1先序遍历二叉树二叉树头文件单击下载单击下载算法6.2中序遍历二叉树单击下载单击下载算法6.3后序遍历二叉树单击下载单击下载算法6.4先序遍历输出二叉树中的结点单击下载单击下载算法6.5先序遍历输出二叉树中的叶子结点单击下载单击下载算法6.6统计叶子结点数目单击下载单击下载算法6.7用“扩展先序遍历序列”建立二叉链表单击下载单击下载算法6.8求二叉树的高度单击下载单击下载算法6.9前序遍历求二叉树的高度递归算法单击下载单击下载算法6.10竖向树状打印二叉树单击下载单击下载算法6.11中序遍历二叉树的非递归算法单击下载单击下载算法6.12后序遍历二叉树的非递归算法单击下载单击下载算法6.13建立中序线索树线索树头文件单击下载单击下载算法6.14在中序线索树中找结点前驱单击下载单击下载算法6.15在中序线索树中找结点后继单击下载单击下载算法6.16在中序线索树中求中序遍历的第一个结点单击下载单击下载算法6.17遍历中序线索树单击下载单击下载算法6.18中序线索二叉树插入结点运算单击下载单击下载算法6.19创建哈夫曼树哈夫曼树头文件单击下载单击下载算法6.20哈夫曼编码单击下载单击下载算法6.21初始化并查集并查集头文件单击下载单击下载算法6.22(a)在并查集中查找某个元素单击下载单击下载算法6.22(b)改进的在并查集中查找某个元素单击下载单击下载算法6.23(a)合并并查集中的子集树单击下载单击下载算法6.23(b)改进的合并并查集中的子集树单击下载单击下载算法6.24判断两颗二叉树是否相似二叉树头文件单击下载单击下载算法6.25求从根结点到某结点间的路径单击下载单击下载算法6.26层次遍历二叉树算法单击下载单击下载6.1void PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/if (root!=NULL)Visit(root -data); /*访问根结点*/PreOrder(root -LChild); /*先序遍历左子树*/PreOrder(root -RChild); /*先序遍历右子树*/6.2void InOrder(BiTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/if (root!=NULL)InOrder(root -LChild); /*中序遍历左子树*/Visit(root -data); /*访问根结点*/InOrder(root -RChild); /*中序遍历右子树*/void PostOrder(BiTree root) /* 后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/if(root!=NULL)PostOrder(root -LChild); /*后序遍历左子树*/PostOrder(root -RChild); /*后序遍历右子树*/Visit(root -data); /*访问根结点*/void PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树根结点的指针*/if (root!=NULL)printf(%c ,root -data); /*输出结点*/PreOrder(root -LChild); /*先序遍历左子树*/PreOrder(root -RChild); /*先序遍历右子树*/void PreOrder(BiTree root) /*先序遍历二叉树, root为指向二叉树根结点的指针*/if (root!=NULL)if (root -LChild=NULL & root -RChild=NULL)printf(%c ,root -data); /*输出叶子结点*/PreOrder(root -LChild); /*先序遍历左子树*/PreOrder(root -RChild); /*先序遍历右子树*/* LeafCount保存叶子结点的数目的全局变量,调用之前初始化值为0 */void leaf_a(BiTree root)if(root!=NULL)leaf_a(root-LChild);leaf_a(root-RChild);if (root -LChild=NULL & root -RChild=NULL)LeafCount+;int leaf_b(BiTree root)int LeafCount2;if(root=NULL)LeafCount2 =0;else if(root-LChild=NULL)&(root-RChild=NULL)LeafCount2 =1;else LeafCount2 =leaf_b(root-LChild)+leaf_b(root-RChild);/* 叶子数为左右子树的叶子数目之和 */return LeafCount2;void CreateBiTree(BiTree *bt) char ch; ch = getchar(); if(ch=.) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); /生成一个新结点 (*bt)-data=ch; CreateBiTree(&(*bt)-LChild); /生成左子树 CreateBiTree(&(*bt)-RChild); /生成右子树nt PostTreeDepth(BiTree bt) /* 后序遍历求二叉树的高度递归算法 */int hl,hr,max;if(bt!=NULL)hl=PostTreeDepth(bt-LChild); /* 求左子树的深度 */hr=PostTreeDepth(bt-RChild); /* 求右子树的深度 */max=hlhr?hl:hr; /* 得到左、右子树深度较大者*/return(max+1); /* 返回树的深度 */else return(0); /* 如果是空树，则返回0 */void PreTreeDepth(BiTree bt, int h)/* 前序遍历求二叉树bt高度的递归算法，h为bt指向结点所在层次，初值为1*/*depth为当前求得的最大层次，为全局变量，调用前初值为0 */ if(bt!=NULL) if(hdepth) depth = h; /*如果该结点层次值大于depth，更新depth的值*/ PreTreeDepth(bt-Lchild, h+1); /* 遍历左子树 */ PreTreeDepth(bt-Rchild, h+1); /* 遍历右子树 */ void PrintTree(BiTree bt,int nLayer) /* 按竖向树状打印的二叉树 */if(bt = NULL) return;PrintTree(bt-RChild,nLayer+1);for(int i=0;idata);PrintTree(bt-LChild,nLayer+1);void inorder(BiTree root); int top=0; p=bt; L1: if (p!=NULL) /* 遍历左子树 */ top=top+2; if(topm) return; /*栈满溢出处理*/ stop-1=p; /* 本层参数进栈 */ stop=L2; /* 返回地址进栈 */ p=p-LChild; /* 给下层参数赋值 */ goto L1; /* 转向开始 */ L2: Visit(p-data); /* 访问根 */ top=top+2; if(topm) return; /*栈满溢出处理*/; stop-1=p; /* 遍历右子树 */ stop=L3; p=p-RChild; goto L1; L3: if(top!=0) addr=stop; p=stop-1; /* 取出返回地址 */ top=top-2; /* 退出本层参数 */ goto addr; /*算法a*/void inorder(BiTree root) /* 中序遍历二叉树，root为二叉树的根结点 */int top=0; BiTree p;BiTree sStack_Size;int m;m = Stack_Size-1;p = root;dowhile(p!=NULL) if (topm) return;top=top+1; stop=p;p=p-LChild; /* 遍历左子树 */if(top!=0) p=stop;top=top-1;Visit(p-data); /* 访问根结点 */p=p-RChild; /* 遍历右子树 */ while(p!=NULL | top!=0); /*算法b*/void InOrder(BiTree root) /* 中序遍历二叉树的非递归算法 */SeqStack S;BiTree p;InitStack (&S);p=root;while(p!=NULL | !IsEmpty(&S) if (p!=NULL) /* 根指针进栈，遍历左子树 */Push(&S,p);p=p-LChild;else /*根指针退栈，访问根结点，遍历右子树*/Pop(&S,&p); Visit(p-data); p=p-RChild; /*算法c*/void PostOrder(BiTree root)BiTNode *p,*q;BiTNode *s;int top=0;q=NULL;p=root;s=(BiTNode*)malloc(sizeof(BiTNode*)*NUM);/* NUM为预定义的常数 */while(p!=NULL | top!=0)while(p!=NULL)top+; stop=p; p=p-LChild; /*遍历左子树*/if(top0) p=stop;if(p-RChild=NULL) |(p-RChild=q)/* 无右孩子，或右孩子已遍历过 */ visit(p-data); /* 访问根结点*/q=p; /* 保存到q，为下一次已处理结点前驱 */top-;p=NULL; elsep=p-RChild;free(s);void Inthread(BiTree root)/* 对root所指的二叉树进行中序线索化，其中pre始终指向刚访问过的结点，其初值为NULL*/if (root!=NULL) Inthread(root-LChild); /* 线索化左子树 */if (root-LChild=NULL)root-Ltag=1; root-LChild=pre; /*置前驱线索 */if (pre!=NULL& pre-RChild=NULL) /* 置后继线索 */pre-RChild=root;pre-Rtag=1;pre=root;Inthread(root-RChild); /*线索化右子树*/BiTNode * InPre(BiTNode *p)/* 在中序线索二叉树中查找p的中序前驱, 并用pre指针返回结果 */ BiTNode *q;if(p-Ltag=1)pre = p-LChild; /*直接利用线索*/else /* 在p的左子树中查找最右下端结点 */for(q = p-LChild;q-Rtag=0;q=q-RChild);pre=q;return(pre);BiTNode * InNext(BiTNode * p) /*在中序线索二叉树中查找p的中序后继结点，并用next指针返回结果*/ BiTNode *Next;BiTNode *q;if (p-Rtag=1) Next = p-RChild; /*直接利用线索*/else /*在p的右子树中查找最左下端结点*/if(p-RChild!=NULL)for(q=p-RChild; q-Ltag=0 ;q=q-LChild);Next=q; elseNext = NULL; return(Next);BiTNode* TinFirst(BiTree root)BiTNode *p;p = root;if(p)while(p-LChild!=NULL)p=p-LChild;return p;void TinOrder(BiTree root)BiTNode *p;p=TinFirst(root);while(p!=NULL)printf(%c ,p-data);p=InNext(p);void InsNode(BiTNode *p , BiTNode *r)BiTNode *s;if(p-Rtag=1) /* p无右孩子 */r-RChild=p-RChild; /* p的后继变为r的后继 */r-Rtag=1;p-RChild=r; /* r成为p的右孩子 */r-LChild=p; /* p变为r的前驱 */r-Ltag=1;else /* p有右孩子 */ s=p-RChild;while(s-Ltag=0)s=s-LChild; /* 查找p结点的右子树的最左下端结点 */r-RChild=p-RChild; /* p的右孩子变为r的右孩子 */r-Rtag=0;r-LChild=p; /* p变为r的前驱 */r-Ltag=1;p-RChild=r; /* r变为p的右孩子 */s-LChild=r; /* r变为p原来右子树的最左下端结点的前驱 */void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) /* w存放已知的n个权值，构造哈夫曼树ht */int m,i;int s1,s2;m=2*n-1;*ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /*0号单元未使用*/for(i=1;i=n;i+) /*1-n号放叶子结点，初始化*/(*ht)i.weight = wi;(*ht)i.LChild = 0;(*ht)i.parent = 0;(*ht)i.RChild = 0;for(i=n+1;i=m;i+)(*ht)i.weight = 0;(*ht)i.LChild = 0;(*ht)i.parent = 0;(*ht)i.RChild = 0; /*非叶子结点初始化*/*-初始化完毕！对应算法步骤1-*/for(i=n+1;i=m;i+) /*创建非叶子结点,建哈夫曼树*/ /*在(*ht)1(*ht)i-1的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/select(ht,i-1,&s1,&s2);(*ht)s1.parent=i;(*ht)s2.parent=i;(*ht)i.LChild=s1;(*ht)i.RChild=s2;(*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight; /*哈夫曼树建立完毕*/void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/char *cd;int i;unsigned int c;int start;int p;hc=(HuffmanCode *)malloc(n+1)*sizeof(char *); /*分配n个编码的头指针*/cd=(char * )malloc(n * sizeof(char ); /*分配求当前编码的工作空间*/cdn-1=0; /*从右向左逐位存放编码，首先存放编码结束符*/for(i=1;i=n;i+) /*求n个叶子结点对应的哈夫曼编码*/start=n-1; /*初始化编码起始指针*/for(c=i,p=(*ht)i.parent; p!=0; c=p,p=(*ht)p.parent) /*从叶子到根结点求编码*/if( (*ht)p.LChild = c) cd-start=0; /*左分支标0*/else cd-start=1; /*右分支标1*/hci=(char *)malloc(n-start)*sizeof(char); /*为第i个编码分配空间*/strcpy(hci,&cdstart);free(cd);for(i=1;inodenum=S-last+1; for(i=0; inodenum; i+) SS-treei.data= S-elemi; SS-treei.parent= -1; int Find_1 ( MFSst *SS, DataType x)/* 确定x属于并查集SS中哪个子集合。如果不属于SS中任一子集，则返回-1，否则返回所在子集树的根结点下标。*/ pos=Locate (SS, x); /* 确定x在SS-tree 中的下标 */ if ( postreei.parent 0 ) i= SS-treei.parent ; return i; /* 返回x所在子集树的根结点下标 */int Find_2 ( MFSst *SS, DataType x)/* 确定x属于并查集SS中哪个子集合，同时调整子集树，降低其高度。如果x不属于SS中任一子集，则返回-1，否则首先找到x所在子集树的根root，然后将x及x的所有祖先（除了root）均改为root的子结点，最后返回root。 */ pos=Locate (SS, x); /* 确定x在SS-tree 中的下标 */ if ( postreei.parent 0 ) i= SS-treei.parent ; root=i; /* 记录x所在子集树的根结点下标 */ i=pos; /* 从pos开始，将x及x的所有祖先（除了root）均改为root的子结点 */ while ( i !=root ) temp= SS-treei.parent ; SS-treei.parent = root; i= temp ; return root; /* 返回x所在子集树的根结点下标 */int Merge_1 ( MFSst *SS, int root1, int root2 )/* root1和root2是并查集SS中两个互不相交的非空子集树的根，将子集树root2并入子集树root1。*/ if ( root1 SS-nodenum-1 ) return ERROR; if ( root2 SS-nodenum-1 ) return ERROR; SS-treeroot2.parent=root1; return OK;int Merge_2 ( MFSst *SS, int root1, int root2 )/* root1和root2是并查集SS中两个互不相交的非空子集树的根，根结点的parent域存放树中结点数目的负值。本算法将结点数目较少的子集树并入结点数目较多的子集树。*/ if ( root1 SS-nodenum-1 ) return ERROR; if ( root2 SS-nodenum-1 ) return ERROR; if ( SS-treeroot1.parent treeroot2.parent ) /* 第一棵子集树中结点数目较多 */ SS-treeroot2.parent=root1; SS-treeroot1.parent+= SS-treeroot2.parent ; else /* 第二棵子集树中结点数目较多 */ SS-treeroot1.parent=root2; SS-treeroot2.parent+= SS-treeroot1.parent ; return OK;int like(BiTree b1, BiTree b2) int like1, like2;if (b1=NULL & b2=NULL) return (1);else if (b1=NULL | b2=NULL) return (0);else like1=like(b1-LChild, b2-LChild);like2