《大学计算机基础与思维》第3章 非线性数据结构.pptVIP

第3章 非线性数据结构 3.1 树及其基本概念 3.2 二叉树 3.3 二叉树的遍历 3.4 树的存储结构和遍历 3.5 树、森林与二叉树的转换 3.6 霍夫曼树及其应用 3.7 图及其基本概念 3.8 图的存储结构 3.9 图的遍历 3.10 图的连通性及最小生成树 本章小节 习题 例3-1 画出具有3个结点的树和二叉树的所有不同形态。 思考：深度为h的完全二叉树的结点数目不少于 如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第n层，每层从左到右)，则对任一结点i(1≤i≤n)，有 (1) 如果i=1，则i是二叉树的根，无双亲；如果i1，则其双亲是结点 。 (2) 如果2in，则结点i无左孩子；否则其左孩子是2i。 (3) 如果2i+1n，则结点i无右孩子；否则其右孩子是结点2i+1。 证明从略。 对于完全二叉树，按图3-8中的编号顺序存储，就能得到一个足以反映整个二叉树结构的线性序列。将完全二叉树中所有结点按编号顺序依次存储到一组连续的存储单元(即向量)中，既不浪费内存，又可用地址公式确定其结点的位置。但对于一般的二叉树，顺序分配造成内存浪费，图3-8所示的完全二叉树，其顺序存储结构如图3-10(a)所示。 在最坏情况下，一个深度为k且只有k个结点的单支树(树中 无度为2的结点)却需要2k –1个存储单元。浪费很大。 所以，一般用链表来表示二叉树。 为便于找到结点的双亲，还可增加一个指向其双亲的指针 域(parent)。由这种结点结构所得的二叉树存储结构称为 三叉链表。 3.3 二叉树的遍历 遍历二叉树就是按一定的次序，系统地访问树中的所有结点，使每个结点恰好被访问一次。所谓访问结点，其含义是很广的，可以理解为对结点的增、删、修改等各种运算的抽象。在本节讨论中，假定访问结点即为输出结点数据域值。二叉树的遍历是最重要和最基本的运算，二叉树的许多操作都是以遍历为基础的。 二叉链表的C语言描述如下： struct tnode { int data; struct tnode *lchild, *rchild; } typedef struct tnode TNODE; 算法3-1 先序遍历根结点指针为bt的二叉树。 void preorder(TNODE *bt) { if (bt != NULL) { printf(%d \n, bt-data); preorder(bt-lchild); preorder(bt-rchild); } } 算法3-2 中序遍历根结点指针为bt的二叉树。 void inorder(TNODE *bt) { if (bt != NULL) { inorder(bt-lchild); printf(%d \n, bt-data); inorder(bt-rchild); } } 算法3-3 后序遍历根结点指针为bt的二叉树。 void postorder(TNODE *bt) { if (bt != NULL) { postorder(bt-lchild); postorder(bt-rchild); printf(%d \n, bt-data); } } 算法3-4 中序遍历bt所指二叉树，s为存储二叉树结点指针的工作栈。 Step1. [初始化] 置堆栈s为空，设置临时指针变量p(bt→p)； Step2. [判定p==NULL] 若p==NULL，则执行Step4； Step3. [P进栈] 将p指针入栈，然后置p = p-lchild，返回Step2； Step4. [取栈顶元素，并退栈] 若栈s为空，则算法结束，否则，将栈顶元素置指针变量P； Step5. [访问结点p] 访问结点P，然后置p = p-rchild，并返回Step2。 #define N m /* m为二叉树的结点个数*/ void inorderf(TNODE *pt) { TNODE *p; TNODE *s[N]; int top=?1; // Step1. p = bt; // Step1. while ((p!=NULL)||(top!= ?1)) // Step2. { while (p!=NU