XIAOSUO 记录个人学习的足迹

摘要：插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的数据序列的适当位置，直到全部记录插入完成为止。 一、基本思想 假设待排序的记录存放在数组R[0…n-1]中。初始时，R[0]自成1个有序区，无序区为R[1…n-1]。从i=1起直至i= n-1为止，依次将R[i]插入当前的有序区R[0…i-1]中，生成含n个记录的有序区。 通常将一个记录Ri插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第i趟插入排序。 排序过程的某一中间时刻，R被划分成两个子区间R[0…i-1]（已排好序的有序区）和[i…n-1]（当前未排序的部分，可称无序区）。 插入排序的基本操作是将当前无序区的第1个记录R[0]插人到有序区R[0…i-1]中适当的位置上，使 R[0…i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。 下图为插入排序是示意图： 二、插入排序的实现 public class InsertSort { public static Listint Demo(Listint data) { int preIndex, currentIndex; for (var i = 1; i data.Count; i++) { preIndex = i - 1; currentIndex = data[i]; while (preIndex = 0 data[preIndex] currentIndex) { data[preIndex + 1] = data[preIndex]; preIndex--; } data[preIndex + 1] = currentIndex; } return data; } } 三、时间复杂度分析 插入排序算法的时间复杂度分为最好、最坏和随机三种情况： （1）最好的情况是关键字在序列中顺序有序。这时外层循环的比较次数为n-1，i…… 阅读全文

摘要：设树T如下图所示，结点R是根，根的子树从左到右依次为T1，T2，…，Tk。 一、树的前序遍历 若树T非空，则： ①访问根结点R； ②依次前序遍历根R的各子树T1，T2，…，Tk。 先序遍历树结点算法实现如下： //先序遍历树结点 public void PreOrder(MLNodeT root) { if (root == null) { return; } //访问根结点 Console.Write(root.Data + ); //按先序访问子树结点 for (int i = 0; i root.Childs.Length; i++) { PreOrder(root.Childs[i]); } } 二、树的后序遍历 若树T非空，则： ①依次后序遍历根T的各子树Tl，T2，…，Tk； ②访问根结点R。 后序遍历树结点算法实现如下： //后序遍历树结点 public void PostOrder(MLNodeT root) { if (root == null) { return; } //按先序访问子树结点 for (int i = 0; i root.Childs.Length; i++) { if (root.Childs[i] != null) { PostOrder(root.Childs[i]); } } //访问根结点 Console.Write(root.Data + ); } 三、树的层序遍历 按照树的结构从上到下、从左到右的顺序访问树的结点。 层序遍历树结点算法实现如下： //层序遍历 public void BroadOrder(MLNodeT root) { Console.WriteLine(遍历开始:); if (root == null) { Console.WriteLine(没有结点！); return; } MLNodeT tmp = root; Queue que = new Queue(); //根结点入队列 que.Enqueue(tmp); while (que.Count 0) { //结点出队列并访问 tmp = (ML…… 阅读全文

摘要：树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树；反之，任何一棵二叉树也能惟一地对应到一个森林或一棵树。 一、树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树： ①在所有兄弟结点之间加一连线； ②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。 下面(a)图所示的树可转换为(c)图所示的二叉树。 　　 注意：由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。 二、森林转换为二叉树 具体方法是： ① 将森林中的每棵树变为二叉树 ② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。 下图中，左边包含三棵树的森林可转换为右边的二叉树。 **　　** 三、二叉树转换为树或森林 把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。 阅读全文

摘要：三、 孩子链表表示法 孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。 下面的(a)图就是用孩子链表表示法来存储图中的树。 注意： ① 孩子结点的数据域仅存放了它们在向量空间的序号。 ② 与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。 ③ 将双亲链表表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。 孩子链表实现树形结构的代码如下： public class ChildNode { private int pos; private ChildNode nextChild; public ChildNode() { pos = -1; nextChild = null; } public ChildNode(int p, ChildNode nc) { pos = p; nextChild = nc; } //孩子结点在一维数组中的位置序号 public int Pos { get { return pos; } set { pos = value; } } //下一个孩子结点的地址信息 public ChildNode NextChild { get { return nextChild; } set { nextChild = value; } } } public class CLNodeT { private T data; private ChildNode firstChild; public CLNode(){ data = default(T); firstChild = null; } public CLNode(T d, ChildNode c) { data = d; firstChild = c; } //孩子结点的数据信息 public T Data { get { return data; } set { data = value; } } //第一个孩子结点的信息 public ChildNode FirstChild { get { return firstChild; } set { fi…… 阅读全文

摘要：一、多重链表表示法 由于树中每个结点都有零个或多个孩子结点，因此，可以令每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域值反映出树中各结点之间的逻辑关系。这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法被称为多重链表法。 一个树中各结点的度数各异，因此结点的指针域个数有两种设置方法。方法① 每个结点指针域个数等于该结点的度数；方法② 每个结点指针域个数等于该树的度数。对于方法①它虽然在一定程度上节约了存储空间，但由于树中各个结点的度数是不相同的，各种操作不容易实现，所以一般采用方法②来实现多重链表法。显然，该方法适用于各个结点的度相差不大的情况。 下图为多重链表表示存储结构示意图 双重链表实现树形结构的代码如下： public class MLNodeT { //存储结点的数据 private T data; //存储子结点的位置 private MLNodeT[] childs; //初始化结点 public MLNode(int max) { childs = new MLNodeT[max]; for (int i = 0; i childs.Length; i++) { childs[i] = null; } } public T Data { get { return data; } set { data = value; } } public MLNodeT[] Childs{ get { return childs; } set { childs = value; } } } public class MLTreeT { private MLNodeT head; public MLNodeT Head { get { return head; } set { head = value; } } public MLTree() { head = null; } public MLTree(MLNodeT node) { head = node; } //求树的根结点，如果树非空，返回根结点，否则返回空 public MLNodeT Root() { retur…… 阅读全文

摘要：一、树和森林的定义 树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： (1)有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树。 森林(Forest)是m(m≥0)棵互不相交的树的集合。 树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。 二、树的相关术语 1. 一个结点的子树的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。 2. 树中度为零的结点称为叶结点或终端结点。 3. 树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。 4. 结点的子树的根成为该结点的孩子，相应地，该结点称为孩子的双亲。 5. 如果存在树中的一个结点序列K1,K2,..,Kj，使得结点Ki是结点Ki+1的父结点(1≤i≤j)，则称该结点序列是树中从结点K1到结点Kj的一条路径或道路。我们称这条路径的长度为j-1，它是该路径所经过的边(即连接两个结点的线段)的数目。树中任一结点有一条到其自身的长度为零的路径。 6. 如果在树中存在一条从结点K到结点M的路径，则称结点K是结点M的祖先，也称结点M是结点K的子孙或后裔。 7. 我们将树中一个结点的非自身祖先和子孙分别称为该结点的真祖先和真子孙。在一棵树中，树根是唯一没有真祖先的结点。叶结点是那些没有真子孙的结点。子树是树中某一结点及其所有真子孙组成的一棵树。 8. 树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。 9. 从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点n的深度或层数。根结点的深度为0，其余结点的深度为其父结点的深度加1。深度相同的结点属于同一层。 10. 树的定义在某些结点之间确定了父子关系，我们又将这种关系延拓为祖先子孙关系。但是树中的许多结点之间仍然没有这种关系。例如兄弟结点之间就没有祖先子孙关系。如果我们在树的每一组兄弟结点之间定义一个从左到右的次序，则得到一棵有序树；否则称为无序树。设结点n的所有儿子按其从左到右的次序排列为n1,n2,..,nk，则我们称n1是n的最左儿子，或简称左儿子，并称ni是ni-1的右邻兄弟，或简称…… 阅读全文

摘要：首先写一个二叉树的C#实现，这是我们的基石： public class BinNode { public int Element; public BinNode Left; public BinNode Right; public BinNode(int element, BinNode left, BinNode right) { this.Element = element; this.Left = left; this.Right = right; } public bool IsLeaf() { return this.Left == null this.Right == null; } } 一、怎样从顶部开始逐层打印二叉树结点数据 有2种算法： 算法1：基于Queue来实现，也就是广度优先搜索（BFS）的思想 static void PrintTree1(BinNode root) { if (root == null) return; BinNode tmp = null; Queue queue = new Queue(); queue.Enqueue(root); while (queue.Count 0) { tmp = (BinNode)queue.Dequeue(); Console.WriteLine(tmp.Element); if (tmp.Left != null) queue.Enqueue(tmp.Left); if (tmp.Right != null) queue.Enqueue(tmp.Right); } } 话说，BFS和DFS思想本来是用于图的，但我们不能被传统的思维方式所束缚。 算法2：基于单链表实现 如果没有Queue给我们用，我们只好使用单链表，把每个节点存在单链表的Data中，实现如下： public class Link { public Link Next; public B…… 阅读全文

摘要：一、概念 树的路径长度：树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。** **　　结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。 结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。 树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和，通常记为： 其中： n表示叶子结点的数目 wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。 树的带权路径长度亦称为树的代价。 哈夫曼树或最优二叉树：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为哈夫曼树或最优二叉树。 【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为： (a)WPL=72+52+22+42=36 (b)WPL=73+53+21+42=46 (c)WPL=71+52+23+43=35 其中(c)树的WPL最小，可以验证，它就是哈夫曼树。 注意： ① 叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。 ② 最优二叉树中，权越大的叶子离根越近。 ③ 最优二叉树的形态不唯一，WPL最小。 二、构造最优二叉树 **　　**哈夫曼算法经常用来解决编码方面的问题，运用这种方式的编码我们称做哈夫曼编码，它是一种变长编码，其优点是可以根据字符出现的不同频率来节省空间。假设给定8个叶子结点Z、K、F、C、U、D、L、E，分别带权2、7、24、32、37、42、42、120，我们来看看这组数的哈夫曼编码过程。 最终的哈夫曼树，我们加入编码后的效果如下图： 前缀特性：一组编码中，其他任何字符的编码都不是某个字符编码的前缀。 DEED的编码: 10100101 1011001110111101的解码: DUCK 每个字符的平均编码位数：Σ(ci*fi) / fT= 785 / 306 = 2.56536 三、哈夫曼算法 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，故称其为哈夫曼算法。其基本思想是： (1)根据给定的n个权值wl，w2，…，wn构成n棵二叉树的森林F={T1，T2，…，…… 阅读全文

摘要：一、定义 二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉查找树或者是空树，或者是满足如下性质的二叉树： ①若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ③左、右子树本身又各是一棵二叉查找树。 上述性质简称二叉查找树性质(BST性质)，故二叉查找树实际上是满足BST性质的二叉树。 二、特点 由BST性质可得： （1） 二叉查找树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。 （2） 二叉查找树中，各结点关键字是惟一的。注意：实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉查找树定义中BST性质(1)里的小于改为大于等于，或将BST性质(2)里的大于改为小于等于，甚至可同时修改这两个性质。 （3） 按中序遍历该树所得到的中序序列是一个递增有序序列。如下图所示的两棵树均是二叉查找树，它们的中序序列均为有序序列：2，3，4，5，7，8。 三、插入运算 在二叉查找树中插入新结点，要保证插入后仍满足BST性质。其插入过程是： (a)若二叉查找树T为空，则为待插入的关键字key申请一个新结点，并令其为根； (b)若二叉查找树T不为空，则将key和根的关键字比较： (i)若二者相等，则说明树中已有此关键字key，无须插入。 (ii)若keyT→key，则将key插入根的左子树中。 (iii)若keyT→key，则将它插入根的右子树中。 子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的叶结点的关键字插入到二叉查找树中，或者直到发现树中已有此关键字为止。 注意：输入序列决定了二叉查找树的形态。二叉查找树的中序序列是一个有序序列。所以对于一个任意的关键字序列构造一棵二叉查找树，其实质是对此关键字序列进行排序，使其变为有序序列。因此，人们又常常将二叉查找树称为二叉排序树。通常将这种排序称为树排序(Tree Sort)，可以证明这种排序的平均执行时间亦为O(nlgn)。对相同的输入实例，树排序的执行时间约为堆排序的2至3倍。因此在一般情况下，构造二叉排序树的目的并非为了排序，而是用它来加速查找，这是因为在一个有序的集合上查找通常比在无序集合上查找更快，“查找树的名称也由此而来。 四、删除运算…… 阅读全文

摘要：一、先序遍历（DLR） 先序遍历的递归过程为：若二叉树为空，遍历结束。否则， （1） 访问根结点； （2）先序遍历根结点的左子树； （3） 先序遍历根结点的右子树。 算法实现如下： //前序遍历 public void preorder(NodeT ptr) { if (IsEmpty()) { Console.WriteLine(Tree is empty); return; } if (ptr != null) { Console.Write(ptr.Data + ); preorder(ptr.LChild); preorder(ptr.RChild); } } 二、中序遍历（LDR） 中序遍历的递归过程为：若二叉树为空，遍历结束。否则， （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 算法实现如下： //中序遍历 public void inorder(NodeT ptr) { if (IsEmpty()) { Console.WriteLine(Tree is empty); return; } if (ptr != null) { inorder(ptr.LChild); Console.Write(ptr.Data + ); inorder(ptr.RChild); } } 三、后序遍历（LRD） 后序遍历的递归过程为：若二叉树为空，遍历结束。否则， （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树。 （3）访问根结点； 算法实现如下： //后序列遍历 public void postorder(NodeT ptr) { if (IsEmpty()) { Console.WriteLine(Tree is empty); return; } if (ptr != null) { postorder(ptr.LChild); postorder(ptr.RChild); Console.Write(ptr.Data + ); } } 四、层次遍历 所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。 算法实现如下：…… 阅读全文