数组_叉树.pptVIP

* * 数组 1 定义：有限个相同类型的变量组成的序列 若每个变量是一维数组，称为二维数组。 若每个变量是n-1维数组，称为n维数组。 数组的顺序存储——行优先 序号：num=(i-1)*n+j 地址： 数组的顺序存储——列优先 序号：num=(j-1)*m+i 地址： 对称矩阵的压缩（行优先） 对称矩阵 序号：num=1+2+3+…+ (i-1)+j 地址： 三角矩阵的压缩存储 序号：num=1+2+3+(i-1)+j 地址： 对称矩阵的压缩存储方法适用于三角矩阵 三对角矩阵的压缩（行优先） 序号：num=3 (i-1)-1+(j-i+2)=2i+j-2 |i-j|=1 地址： 稀疏矩阵的压缩存储 mXn的矩阵含t个非零元素，则称 稀疏因子 通常认为 的矩阵为稀疏矩阵 三元组表 三元组链表表示稀疏矩阵 struct B { int i; int j; float v; B *next; }; B *in_array() { B *head,*p,*q; int k,m,n,mm,nn,tt; float d; head=NULL; q=NULL; cinmmnntt; for(k=0;ktt;k++) { cinmnd; p=new(B); p-i=m-1;p-j=n-1;p-v=d; p-next=NULL; if(head==NULL)head=p; else q-next=p; q=p; } return head; } 输入行数列数及非零元素个数 构造新结点 数据结构:线性结构和非线性结构 线性结构(线性表, 栈,队列等) 非线性结构: 至少存在一个数据元素有不止一个直接前驱或后继(树,图等) 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。 树型结构实例 家族树 树的逻辑结构和存储结构 家族树 祖父 伯父 父亲 叔父 堂兄 堂姐 本人 堂弟 侄儿 ( a ) 家族树 ， ， 树与二叉树 A B C D E F G H I J 树的特点： 1 树的根结点没有前驱结点，除根结点外的所有结点有且只有一个前驱结点； 2 所有结点可以有0个或多个后继结点； 3 树中没有封闭环的存在 A B C D E F A B C D E F G 树的相关术语 1 结点的度：结点拥有子树的个数（结点的孩子数） 2 叶子结点：终端结点（度为0） 3 分支结点：非终端结点（度不为0） 4 父结点、子结点：一个结点其下有分支，则分支结点称为子结点，该结点为子结点的父结点。同一父结点的子结点互称为兄弟。 若有一条由k到达ks的路径，则称k是ks的祖先，ks是k的子孙。 A B C D E F G H I J 结点层数：从根结点到该结点的代数（根结点的层数为1）。其它任何结点的层数等于它的父结点的层数加1 树的深度：树中最大代数 树的度：各结点度的最大值 A B C D E F G H I J 二叉树 1 每个结点最多有两个子树，称为该结点的左子树与右子树 左子树 2 二叉树的5种基本形态 空树，即结点数为0 单结点二叉树，有且仅有一个结点 右子树 左子树 右子树 4 深度为m的二叉树最多有 个结点 A B C D H E F G I J K L M N O A B C D E F G 深度为3的满二叉树 深度为4的满二叉树 3 在二叉树的第K层中最多有 个结点 4 完全二叉树——在满二叉树的最下一层，从右到左多依次连续去掉若干个结点的二叉树（最下层的结点集中到左边） A B C D H E F G I J K L M N O A B C D H E F G I J K L M N 完全二叉树 非完全二叉树 二叉树的存储 struct bnode { int d; bnode *lchild,*rchild; }; A B C D a Λ c Λ b Λ Λ d Λ rchild data lchild 指向右孩子的指针 指向左孩子的指针 b