第二章非线性数据结构.pptVIP

第三章 非线性数据结构 计算机软件基础 2. 二叉排序树的生成 操作过程： ① 若原二叉排序树为空，则将待插结点作为此树的根结点。 ② 若原二叉排序树不空，则比较待插结点和根结点的关键字值。若待插元素的关键字值小于根结点的关键字值，则将其插入到左子树中；否则，将其插入到右子树中。 ③ 在二叉排序树的左、右子树中的插入过程同上。 主要思想：从一棵空的二叉排序树开始，按关键字值逐个将一组结点依次插入到树中的恰当位置上。 ? ? ? ? 计算机软件基础 例：对于一组关键字{51，34，79，18，45，86}，生成对应的二叉排序树。 51 51 34 51 34 79 51 34 79 18 45 51 34 79 18 86 51 34 79 18 45 ? ? ? ? 计算机软件基础 算法： void insert(bstree *p,bstree *s) /*插入一个新结点的算法*/ { if(s-datap-data) { if (p-lchild==NULL) p-lchild=s; else insert(p-lchild,s); } else { if (p-rchild==NULL) p-rchild=s; else insert(p-rchild,s); } } 根结点的指针 新结点的指针 ? ? ? ? 计算机软件基础 Bstree *bstreecreate() /*二叉排序树的生成算法*/ { int x; bstree *s,*t; /* s 指新结点，t 指根 t=NULL; printf(input the elements of bstree,end flag is -1\n); scanf(%d,x); while(x!=-1) { s=(bstree*)malloc(sizeof(bstree)); s-data=x; s-lchild=s-rchild=NULL; if (t==NULL) t=s; else insert(t,s); scanf(%d,x); } return (t); } ? ? ? ? 计算机软件基础 ? ? ? ? 七. 树的应用 —— 哈夫曼树 1.哈夫曼树的定义 哈夫曼树是一类带权路径最小的二叉树。 2.哈夫曼算法—如何构造一棵哈夫曼树 （1）对于给定的n个权值{w1,w2,…….wn}，构造n棵二叉树的森林，F={T1,T2,……Tn}，每棵二叉树均只有根结点。 （2）在F中选根结点权值最小的两颗二叉树作为左、右子树，构造一棵新的二叉树，新二叉树根结点权值为其左、右子树根结点权值之和。 （3）在F中删除这两颗树，同时将新生成的二叉树加入F中 （4）重复（2）（3）直到F中只剩下一颗二叉树为止。 计算机软件基础 ? ? ? ? 例：给定权值{5,3,7,2}，构造哈夫曼树 5 3 7 2 7 5 2 5 3 5 2 5 3 10 7 17 7 5 2 5 3 10 A B C D 计算机软件基础 ? ? ? ? 3.哈夫曼编码 在哈夫曼树中，左分支用 0 编码表示，右分支用 1 编码表示，则从根结点到某个叶子结点的路径上各左右分支的编码就构成了哈夫曼编码。 7 5 2 5 3 10 17 1 1 1 0 0 0 5 3 7 2 A B C D A：10 B：110 C：0 D：111 A C B D 第五次上机作业 1.输入一组整数，将其作为结点的关键字值建立一棵二叉排序树，并对其进行中序遍历（实现升序排列）。（必做） 2. 统计生成的二叉排序树中叶子结点的数目。（选做） 计算机软件基础 3.3 图 一．图的定义 图G由两个集合V（G）和E（G）组成，记作G=（V，E）。其中V（G）是顶点的有穷非空集合，E（G）是边的有穷集合。 若图G中的边没有方向，则称图G为无向图。 若图G中的边有方向，则称图G为有向图。 ? ? ? ? 计算机软件基础 4. 二叉树的存储 （1）顺序存储结构 实现方法：用一组地址连续的存储单元依次（从上到下，从左到右）存放二叉树中的各个结点的数据信息，借助于各个结点在存储结构中存放的相对位置