| « | June 2026 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | | | | | |
|
公告 |
| 暂无公告... |
| Blog信息 |
|
blog名称:
日志总数:32
评论数量:44
留言数量:0
访问次数:181886
建立时间:2005年1月4日 |
| |
|
 数据结构--树和二叉树
文章收藏
eaglebetter 发表于 2006/8/6 0:24:12 |
| 6-1 树的定义和术语6-1-1 树的定义1．树的定义2．树的其他表示法 （1） 嵌套集合法（2） 圆括号表示法（3） 凹入法6-1-2 基本术语6-2 二叉树6-2-1 二叉树的定义1．定义2．二叉树的形态3．二叉树的基本操作：6-2-2 二叉树的性质（1） 满二叉树（2） 完全二叉树6-2-3 二叉树的存储1．顺序存储结构（1） 一维数组存储法（2） 二维数组存储法2．链式存储结构（1） 二叉链表存储typedef struct BT // 定义二叉树结构体{ char data; // 定义数据域BT *lchild; // 定义结点的左指针BT *rchild; // 定义结点的右指针}BT; // 将BT定义为指向二叉树结点结构体的指针类型（2） 三叉链表存储6-3 遍历二叉树和线索二叉树6-3-1 遍历二叉树1．先序遍历（DLR） void Preorder(BT *T) // 先序遍历二叉树BT{ if (bt==NULL) return; // 递归调用的结束条件 { printf(T->data); // 输出结点的数据域 Preorder(T->lchild); // 先序递归遍历左子树 Preorder(T->rchild); // 先序递归遍历右子树 }}2．中序遍历（LDR）void Inorder(BT *T) // 中序遍历二叉树BT{ if (bt==NULL) return; // 递归调用的结束条件 { Inorder(T->lchild); // 中序递归遍历左子树printf(T->data); // 输出结点的数据域Inorder(T->rchild); // 中序递归遍历右子树 }}3．后序遍历（LRD）void Postorder(BT *T) // 后序遍历二叉树BT{ if (bt==NULL) return; // 递归调用的结束条件 { Postorder(T->lchild); // 后序递归遍历左子树 Postorder(T->rchild); // 后序递归遍历右子树 printf(T->data); // 输出结点的数据域 }}4．层次遍历void Levelorder(BT *T) // 按层次遍历二叉树BT{ int i,j;BT *q[MAXLEN],*p; // 设置一个数组来模拟队列p=T;if(p!=NULL) // 若二叉树非空，则根结点地址入队 { i=1;q[i]=p;j=2; }while(i!=j) { p=q[i];printf(p->data); // 访问队首结点的数据域 if( p->lchild!=NULL) // 将队首结点的左孩子结点入队列{ q[j]=p->lchild;j++;}if(p->rchild!=NULL) // 将队首结点的右孩子结点入队列{ q[j]=p->rchild;j++; }i++; }}6-3-2 恢复二叉树1．由先序和中序恢复二叉树2．由中序和后序恢复二叉树6-3-3 线索二叉树1．什么是线索二叉树2．线索二叉树的方法3．线索二叉树的优点4．线索二叉树的缺点6-4 二叉树的转换6-4-1 一般树转换为二叉树1．一般树和二叉树的二叉链表存储结构比较2．将一棵树转换为二叉树的方法：6-4-2 森林转换为二叉树【例6-5】将图6-22给出的森林转换为二叉树。6-4-3 二叉树转换为树和森林【例6-6】将图6-24给出二叉树转换为树的过程。6-5 二叉树的应用6-5-1 二叉树的基本应用1．统计二叉树叶子结点数（1） 基本思想（2） 算法void Leafnum(BT *T) // 求二叉树叶子结点数{ if(T) // 若树不为空 // 开始时，BT为根结点所在的链结点的指针，返回值为BT的叶子数{ if(T->lchild==NULL&&T->rchild==NULL)count++; // 若左子树和右子树都为空，count计数器加1 Leafnum(T->lchild); // 递归统计T的左子树叶子结点数 Leafnum(T->rchild); // 递归统计T的右子树叶子结点数}}2．求二叉树结点总数（1） 基本思想（2） 算法void Nodenum(BT *T) // 求二叉树总结点数{ if(T) { count++; // 如果二叉树不空，加上一个结点数Nodenum(T->lchild); // 递归统计T的左子树结点数Nodenum(T->rchild); // 递归统计T的右子树结点数 }}3．求二叉树的深度（1） 基本思想（2） 算法int TreeDepth(BT *T) // 求二叉树深度{int ldep,rdep; // 定义两个整型变量，用以存放左、右子树的深度 if(T==NULL) // 若树空则返回0 return 0;else{ ldep=TreeDepth(T->lchild); // 递归统计T的左子树深度 rdep=TreeDepth(T->rchild); // 递归统计T的右子树深度 if(ldep>rdep) // 若左子树深度大于右子树深度，则返回左子树深度加1 return ldep+1; else return rdep+1; // 否则返回右子树深度加1}}4．查找数据元素（1） 基本思想（2）算法BiTree Search（BiTree bt，elemtype x）{ BiTree p; if (bt->data==x) return bt; // 若查找根结点成功，即返回。否则，分别在左、右子树查找 if (bt->lchild!=NULL) return (Search (bt->lchild,x)); // 在bt->lchild为根结点指针的二叉树中查找数据元素x if (bt->rchild!=NULL) return (Search (bt->rchild,x)); // 在bt->rchild为根结点指针的二叉树中查找数据元素x return NULL; // 查找失败，返回}6-5-2 标识符树与表达式1．标识符树的特点2．从表达式产生标识符树的方法3．应用举例6-6 哈夫曼树及其应用6-6-1 哈夫曼树的引入1．几个术语2．如何求树的带权路径长度3．为什么要使用哈夫曼树if (n<60) b="E";else if (n<70) b="D" else if (n<80) b="C" else if (n<90) b="B" else b="A";表6-1分数n 0～59 60～69 70～79 80～89 90～100 比例数 5% 15% 40% 30% 10% 等级b E D C B A 6-6-2 哈夫曼树的建立1．哈夫曼树构成的基本思想是：2．哈夫曼树的构造算法6-6-3 哈夫曼编码1．什么是哈夫编码2．求哈夫曼编码的方法（1） 构造哈夫曼树（2） 在哈夫曼树上求叶子结点的编码3．哈夫曼树及哈夫曼编码的源程序#include <stdio.h>#define MAXLEN 100typedef struct // 定义结构体{ int weight; // 定义一个整型权值变量int lchild,rchild,parent; // 定义左、右孩子及双亲指针}HTNode;typedef HTNode HFMT [MAXLEN]; // 是向量类型的int n;void InitHFMT (HFMT T) // 初始化 { int i;printf ("\n\t\t请输入共有多少个权值 (小于100)：");scanf ("%d",&n);getchar();for (i=0; i<2*n-1; i++){ T[i].weight=0;T[i].lchild=-1;T[i].rchild=-1;T[i].parent=-1;}}void InputWeight(HFMT T) // 输入权值{ int w;int i;for (i=0; i<n;i++){ printf ("\n\t\t输入第%d个权值:",i+1);scanf ("%d",&w);getchar();T[i].weight=w; }}void SelectMin (HFMT T, int i, int *p1,int *p2) // 选择两个结点中小的结点{ long min1=999999; // 预设两个值，并使它大于可能出现的最大权值long min2=999999; int j;for (j=0;j<=i;j++){ if (T[j].parent==-1){ if (min1>T[j].weight){ min1=T[j].weight; // 找出最小的权值*p1=j; // 通过*p1带回序号}}}for (j=0;j<=i;j++){ if (T[j].parent==-1){ if (min2>T[j].weight&&j!=(*p1)){ min2=T[j].weight; // 找出次最小的权值*p2=j; // 通过*p2带回序号}}}} // 选择结束void CreatHFMT (HFMT T) // 构造哈夫曼树，T[2*n-1]为其根结点{ int i,p1,p2;InitHFMT (T);InputWeight (T);for (i=n;i<2*n-1;i++){ SelectMin (T,i-1,&p1,&p2);T[p1].parent=T[p2].parent=i;T[i].lchild=T[p1].weight;T[i].rchild=T[p2].weight;T[i].weight=T[p1].weight+T[p2].weight;}}void PrintHFMT (HFMT T) // 输出向量状态表{ int i,k=0;for (i=0; i<2*n-1; i++)while (T[i].lchild!=-1){ if (!(k%2))printf ("\n");printf ("\t\t(%d %d),(%d %d)",T[i].weight,T[i].lchild,T[i].weight,T[i].rchild);k++;break;}}void hfnode (HFMT T,int i,int j){ j=T[i].parent;if (T[j].rchild= =T[i].weight) printf("1");else printf("0");if(T[j].parent!= -1) i=j,hfnode (T,i,j);}void huffmannode (HFMT T) // 求哈夫曼编码{ int i,j,a,k=0;printf ("\n");for (i=0;i<n;i++){ j=0;a=i;if (!(k%2))printf ("\n"); printf("\t\t%i: ",T[i].weight);k++;hfnode(T,i,j);i=a;}}void main() // 主函数{ HFMT HT;CreatHFMT(HT);PrintHFMT(HT);huffmannode(HT);printf("\n ");}小结实验6 树子系统1．实验目的2．实验内容3．实验步骤：4．参考程序#include <stdio.h>#define MAXLEN 100typedef struct BT // 定义二叉树结构体{ char data;BT* lchild;BT*rchild;}BT;BT *CreateBT(); void ShowTree(BT *T);void Preorder(BT *T);void Postorder(BT *T);void Levelorder(BT *T);void Inorder(BT *T);void Leafnum(BT *T);void Nodenum(BT *T);int TreeDepth(BT *T);int count=0; // 定义计算结点个数数的变量void main() // 树子系统住函数{ BT *T=NULL;char ch1,ch2,a;ch1='y';while(ch1=='y'||ch1=='Y'){ printf("\n\n\n\n");printf("\n\n\t\t\t二 叉 树 子 系 统\n");printf("\n\t\t***************************************");printf("\n\t\t* 1---------建 二 叉 树 *");printf("\n\t\t* 2---------凹 入 显 示 *");printf("\n\t\t* 3---------先 序 遍 历 *");printf("\n\t\t* 4---------中 序 遍 历 *");printf("\n\t\t* 5---------后 序 遍 历 *");printf("\n\t\t* 6---------层 次 遍 历 *");printf("\n\t\t* 7---------求 叶 子 数 *");printf("\n\t\t* 8---------求 结 点 数 *");printf("\n\t\t* 9---------求 树 深 度 *");printf("\n\t\t* 0---------返 回 *");printf("\n\t\t***************************************");printf("\n\t\t请选择菜单号(0--9):");scanf("%c",&ch2);getchar();printf("\n");switch(ch2){case '1':printf("\n\t\t请输入按先序建立二叉树的结点序列：");printf("\n\t\t说明:'0'代表后继结点为空,请逐个输入,按回车输入下一结点。");printf("\n\t\t请输入根结点：");T=CreateBT();printf("\n\t\t二叉树成功建立!\n");break;case '2':ShowTree(T);break;case '3':printf("\n\t\t该二叉树的先序遍历序列为：");Preorder(T);break;case '4':printf("\n\t\t该二叉树的中序遍历序列为：");Inorder(T);break;case '5':printf("\n\t\t该二叉树的后序遍历序列为：");Postorder(T);break;case '6':printf("\n\t\t该二叉树的层次遍历序列为：");Levelorder(T);break;case '7':count=0;Leafnum(T);printf("\n\t\t该二叉树有%d个叶子。\n",count);break;case '8':count=0;Nodenum(T);printf("\n\t\t该二叉树总共有%d个结点。\n",count);break;case '9':printf("\n\t\t该树的深度是：%d",TreeDepth(T));break;case '0':ch1='n';break;default:printf("\n\t\t***请注意：输入有误!***");}if(ch2!='0'){ printf("\n\n\t\t按回车键继续，按任意键返回主菜单!\n");a=getchar();if(a!='\xA'){ getchar();ch1='n'; }}}}BT *CreateBT() // 建立二叉树{ BT *t;char x;scanf("%c",&x);getchar();if(x=='0')t=NULL;else{ t=new BT;t->data=x;printf("\n\t\t请输入%c结点的左子结点：",t->data);t->lchild=CreateBT();printf("\n\t\t请输入%c结点的右子结点：",t->data);t->rchild=CreateBT();}return t;}void Preorder(BT *T) // 先序遍历{ if(T){ printf("%3c",T->data);Preorder(T->lchild);Preorder(T->rchild);}}void Inorder(BT *T) // 中序遍历{ if(T){ Inorder(T->lchild);printf("%3c",T->data);Inorder(T->rchild);}}void Postorder(BT *T) // 后序遍历{ if(T){ Postorder(T->lchild);Postorder(T->rchild);printf("%3c",T->data);}}void Levelorder(BT *T) // 层次遍历{int i,j;BT *q[100],*p;p=T;if(p!=NULL){i=1;q[i]=p;j=2;}while(i!=j){p=q[i];printf("%3c",p->data);if(p->lchild!=NULL){q[j]=p->lchild;j++;}if(p->rchild!=NULL){q[j]=p->rchild;j++;}i++;}}void Leafnum(BT *T) // 求叶结点数{if(T){if(T->lchild==NULL&&T->rchild==NULL)count++;Leafnum(T->lchild);Leafnum(T->rchild);}}void Nodenum(BT *T) // 求二叉树总结点数{if(T){count++;Nodenum(T->lchild);Nodenum(T->rchild);}}int TreeDepth(BT *T) // 求树深度{int ldep,rdep;if(T==NULL)return 0;else{ ldep=TreeDepth(T->lchild);rdep=TreeDepth(T->rchild);if(ldep>rdep)return ldep+1;elsereturn rdep+1;}}void ShowTree(BT *T) // 凹入法显示二叉树{BT *stack[MAXLEN],*p;int level[MAXLEN][2],top,n,i,width=4;if(T!=NULL){printf("\n\t\t二叉树的凹入表示法：\n\t\t");top=1;stack[top]=T; // 根结点入栈level[top][0]=width;while(top>0){p=stack[top]; // 退栈并显示结点的值n=level[top][0];for(i=1;i<=n;i++) // n为显示宽度，字符以右对齐显示printf(" ");printf("%c",p->data);for(i=n+1;i<50;i+=2)printf("▃");printf("\n\t\t");top- -;if(p->rchild!=NULL){ // 右子树根结点入栈top++;stack[top]=p->rchild;level[top][0]=n+width; // 显示宽度增加widthlevel[top][1]=2; // 左子树根结点入栈}if(p->lchild!=NULL){top++;stack[top]=p->lchild;level[top][0]=n+width; // 显示宽度增加widthlevel[top][1]=1;}}}} |
|
|