XIAOSUO 记录个人学习的足迹

摘要：一、多重链表表示法 　　由于树中每个结点都有零个或多个孩子结点，因此，可以令每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域值反映出树中各结点之间的逻辑关系。这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法被称为多重链表法。 　　一个树中各结点的度数各异，因此结点的指针域个数有两种设置方法。方法① 每个结点指针域个数等于该结点的度数... 阅读全文

摘要：一、树和森林的定义 　　树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： 　　　　(1)有且仅有一个特定的称为根(Root)的结点； 　　　　(2)其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树。 　　森林(Forest)是m(m≥0)棵互不相交的树的集合。 　　树和森林的概念相近。删去一棵... 阅读全文

摘要：一、怎样从顶部开始逐层打印二叉树结点数据 二、设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得分。 三、如何不用递归实现二叉树的前序/后序/中序遍历 四、在二叉树中找出和为某一值的所有路径 阅读全文

摘要：一、概念 　　树的路径长度：树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。** **　　结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。 　　结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。 　　树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和... 阅读全文

摘要：二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉查找树或者是空树，或者是满足如下性质的二叉树： ①若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ③左、右子树本身又各是一棵二叉查找树。 　　上述性质简称二叉查找树性质(BST性质)，故二叉查找树实际上是满足BST性质的二叉树。 阅读全文

摘要：一、先序遍历（DLR） 　　先序遍历的递归过程为：若二叉树为空，遍历结束。否则， 　　　　（1） 访问根结点； 　　　　（2）先序遍历根结点的左子树； 　　　　（3） 先序遍历根结点的右子树。 　　　　　　 　　算法实现如下： //前序遍历 public void preorder(NodeT ptr) { if (IsEmpty()) { Console.WriteLine(Tree... 阅读全文

摘要：一、顺序存储结构表示二叉树 　　所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。 　　依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系。 　　　　　　 　　对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能... 阅读全文

摘要：一、二叉树的定义 　　二叉树（Binary Tree）是n(n≥0)个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 　　　　 　　二叉树的5中形态 　　　　 二、二叉树的相关术语 （1）结点的度。结点所拥有的子树的个数称为该结点的度。 （2）叶结点... 阅读全文

摘要：一、稀疏矩阵的定义 　　对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵（sparse）。 　　人们无法给出稀疏矩阵的确切定义，一般都只是凭个人的直觉来理解这个概念，即矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素没有分布规律。 　　　　 二、稀疏矩阵的压缩存储 　　由于稀疏矩阵中非零元素较少，零元素较多，因此可以采用只存储非零元素的方法来进行压缩... 阅读全文

摘要：一、特殊矩阵的定义 　　　　对那些具有相同值元素或零元素在矩阵中分布具有一定规律的矩阵，被称之为特殊矩阵。特殊矩阵通常有： 　　对角矩阵（d i a g o n a l）：M是一个对角矩阵当且仅当i≠j 时有M(i, j) = 0。下图a 所示。 　　三对角矩阵（ t r i d i a g o n a l）：M是一个三对角矩阵当且仅当| i - j | 1 时有M(i, j ) = 0。下... 阅读全文