数据结构

节点的度：结点拥有的子树数目称为结点的度，叶子结点 就是度为0的结点 树的度：树内各结点的度的最大值

二叉树： 第i层最多有2^(i-1) 个结点 ; 深度为k的二叉树最多有2^k -1个结点 ; 任一二叉树，如果叶子结点数为n_0,度为2的结点为n_2，则n_0 =n_2+1 ; 满二叉树： 1.每一层上的结点数都是最大。 2.叶子结点全在底层。

完全二叉树： 对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 1、 叶子结点只可能分布在最大的两层上。 2.对于任一结点，如果右子树最大层次为i,则左子树最大层次必为i或i+1。 3.具有n个结点的完全二叉树的深度为⌊log_2 n⌋+1。 4. i结点(i>1)的父结点为⌊i/2⌋, i结点的左子结点是2i,右子结点是2i+1。 二叉树的顺序存储: 1.完全二叉树的顺序存储：从上到下，从左到右。 2.非完全二叉树的顺序存储：把缺少的空位补上0或其它标志，然后当完全二叉树存储。

二叉树的链式存储: 1.二叉链表：一个数据域与两个指针域（指向两个孩子结点）。 1).n个结点的二叉链表中有n+1个空指针域。

2.三叉链表：一个数据域与三个指针域（指向两个孩子结点以及父结点）。

遍历二叉树：（序：访问根节点的次序） 1.先序遍历：（1）访问根节点；（2）先序遍历左子树；（3）先序遍历右子树； 2.中序遍历：（1）中序遍历左子树；（2）访问根节点；（3）中序遍历右子树； 3.后序遍历：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根节点；

根据 先序和中序 或者 后序和中序 还原二叉树图：中序分左右，先序和后序定根。

二叉树的层次遍历：按层次从上到下，从左到右进行遍历。通过队列实现。

线索二叉树：n个结点中总共有2n个指针域，使用的指针域为n-1个，可把剩余的n+1个指针域进行利用，如果左指针域为空则指向其前驱结点，如果右指针域为空则指向其后继结点。可在结构中设标志域ltag和rtag表明指向的是 孩子结点(为0) 还是 前驱和后继结点(为1)。

森林：m(m>=0)棵不相交的树的集合。

树的存储结构（非二叉树，一个结点可以有多个孩子结点）： 1.双亲表示法：由数据域和双亲域(存放父节点的下标或指向父节点的位置)构成； 2.孩子链表：把每个结点的孩子组成一个线性表，该结点作为表头指向该线性表，再用顺序表存放所有结点。 3.孩子兄弟表示法（二叉树表示法，更常用）：用二叉链表作为树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。

树转为二叉树： 1.在相邻兄弟之间加上连线。 2.每个父结点只保留和左孩子（第一个子结点）之前的连线，去掉与其余孩子之间的关系。 二叉树转为树： 1.若p结点是其父结点r的左孩子，则找到p的右孩子a、a的右孩子b…沿分支找到所有右孩子都与p的父节点r作连线,再去掉这些右孩子与原来父结点之间的连线。

森林转为二叉树： 1.将每棵树分别转为二叉树。 2.将每棵树的根节点用线相连。

二叉树转为森林： 1.将二叉树给根节点r与右孩子的连线p，以及p与右孩子a连线…沿分支找到所有右孩子之间的连线都去掉，使其变成孤立的二叉树。 2.将每个孤立的二叉树还原为树。

树的遍历方式（3种）： 1.先根遍历：先访问根结点，再依次先根遍历各子树； 2.后根遍历：先依次后根遍历各子树，然后访问根结点； 3.按层次遍历：按层次从上到下，从左到右遍历各结点；

森林的遍历： 1.先序遍历（即依次对每棵树进行先序遍历）： 1).访问森林中的第一棵树的根节点。 2).先序遍历森林中第一棵树的子树森林。 3).先序遍历森林中其余树构成的森林 2.中序遍历（即依次对每棵树进行后序遍历）： 1). 中序遍历森林中第一棵树的子树森林。 2). 访问森林中的第一棵树的根节点。 3).中序遍历森林中其余树构成的森林

哈夫曼树（最优二叉树, 带权路径长度WPL最短的树）： 1.从一个结点往下可以达到的结点之间的通路，称为路径。 2.某一路径所经过的“边”的数量，称为该路径的路径长度。 3.树的路径长度：从树的根结点到每个结点的路径长度之和。 4.完全二叉树的路径长度最短。 5.给树中的结点赋给一个某种意义的值，称为该结点的权。 6.结点的带权路径长度：从根结点到该结点的路径长度与该结点的权乘积。 7.树的带权路径长度(weighted path length,WPL)：树的所有叶子结点的带权路径长度之和。 WPL=∑_(k=1)^n▒〖w_k l_k 〗 ; 8.哈夫曼树中权越大的叶子离根越近（路径越短）。

构造哈夫曼树： 1.根据给定的n个权值w_1、w_2 …w_n构造n棵单根二叉树，组成二叉树森林。 2.在上面二叉树森林中选择两棵根结点权值最小的树作为左右子树，构成一棵新的二叉树加入到二叉树森林，并在森林中删除选择的左右子树。新的二叉树根结点权值为左右子树的根结点权值之和。 3.在新的二叉树森林中重新重复步骤2，直到只剩下最后一棵二叉树为止。 在上面的哈夫曼算法中，初始有n棵二叉树，要经过n-1次合并形成哈夫曼树，产生n-1个度为2的新结点，因此哈夫曼树共有2n-1个结点，且每个结点的度只为0或2。

哈夫曼编码： 1.可变长度编码，每个字符由0和1构成，把字符出现的概率作为权重把所有字符构造成哈夫曼树，每经过一条左分支加一个0，每经过一条右分支加一个1。 2.为什么哈夫曼编码是前缀编码: 因为每个叶子路径是唯一的，因此每个字符的编码不可能是其它字符编码的前缀。

图：由V和E组成的偶对，G=(V,E); V(Vertex):顶点（数据元素）的有穷非空集合，E(Edge):边的有穷集合。 完全图：任意两个点之间都有边，分为有向完全图和无向完全图。 有向完全图：任意两个点之间都有一条无方向的边，n个顶点有n(n-1)/2条边。 无向完全图：任意两个点之间都有两条有方向的边(弧)，n个顶点有n(n-1)条边(弧)。 稀疏图：有很少边或弧的图。（e if (iNote == NULL) return; cout bTreeNote* p = iNote; stack sNote; while (p || !sNote.empty()) { if (p) { sNote.push(p); p = p->leftSubTree; } else //如果p为空，栈不为空 { p = sNote.top();//获取栈顶结点 cout queue que; que.push(iNote); bTreeNote* p; while (!que.empty()) { p = que.front(); cout rightSubTree) que.push(p->rightSubTree); } } void test10(){ //二叉树为：A,B,F,NULL,C,NULL,G,NULL,NULL,D,E,NULL,NULL,H,NULL // A // / \ // B F // \ \ // C G // / \ / // D E H // bTreeNote* D = new bTreeNote{ "D",NULL,NULL }; bTreeNote* E = new bTreeNote{ "E",NULL,NULL }; bTreeNote* C = new bTreeNote{ "C",D,E }; bTreeNote* B = new bTreeNote{ "B",NULL,C }; bTreeNote* H = new bTreeNote{ "H",NULL,NULL }; bTreeNote* G = new bTreeNote{ "G",H,NULL }; bTreeNote* F = new bTreeNote{ "F",NULL,G }; bTreeNote* A = new bTreeNote{ "A",B,F }; preOrderTraverseTree(A); cout m_pT = new T[que_size]; m_front = m_rear = 0; } bool univerQuePush(T& elem) { if ((m_rear + 1) % que_size == m_front) return false; m_pT[m_rear] = elem; m_rear = (m_rear + 1) % que_size; return true; } void univerQueTraverse() { if (m_front == m_rear) return; int index = m_front; while (index % que_size != m_rear) { cout if (qNodes.empty()) return; string data = qNodes.front(); qNodes.pop(); if (data == "#") node = NULL; else { *node = new bTreeNode{data,NULL,NULL}; creatBiTree(&(*node)->leftSubTree, qNodes); creatBiTree(&(*node)->rightSubTree, qNodes); } } ``cpp void test13(){ //二叉树先序遍历为：ABC##DE#G##F### queue qNodes; qNodes.push("A");qNodes.push("B");qNodes.push("C");qNodes.push("#");qNodes.push("#");qNodes.push("D"); qNodes.push("E");qNodes.push("#");qNodes.push("G");qNodes.push("#");qNodes.push("#");qNodes.push("F"); qNodes.push("#");qNodes.push("#");qNodes.push("#"); bTreeNode* bTree = NULL; creatBiTree(&bTree, qNodes); preOrderTraverseTree(bTree); cout newTree = NULL; return; } else { *newTree = new bTreeNode{ srcTree->data,NULL,NULL}; copyBTree(srcTree->leftSubTree, &(*newTree)->leftSubTree); copyBTree(srcTree->rightSubTree,&(*newTree)->rightSubTree); } } //计算二叉树的深度 int getBTreeDepth(bTreeNode* tree) { if (tree == NULL) return 0; else { int leftDepth = getBTreeDepth(tree->leftSubTree); int rightDepth = getBTreeDepth(tree->rightSubTree); return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; } } //计算二叉树结点的个数 int getBTreeNodeCount(bTreeNode* tree) { if (tree == NULL) return 0; else { return getBTreeNodeCount(tree->leftSubTree)+ getBTreeNodeCount(tree->rightSubTree)+1; } } //计算二叉树的叶子结点个数 int getLeafNodeCount(bTreeNode* tree) { if (tree == NULL) return 0; else if (tree->leftSubTree == NULL && tree->rightSubTree == NULL) return 1; else return getLeafNodeCount(tree->leftSubTree) + getLeafNodeCount(tree->rightSubTree); } void test14() { //二叉树先序遍历为：ABC##DE#G##F###; (#表示该位置为空) // A // / // B // / \ // C D // / \ // E F // \ // G // queue qNodes; qNodes.push("A");qNodes.push("B");qNodes.push("C");qNodes.push("#");qNodes.push("#");qNodes.push("D"); qNodes.push("E");qNodes.push("#");qNodes.push("G");qNodes.push("#");qNodes.push("#");qNodes.push("F"); qNodes.push("#");qNodes.push("#");qNodes.push("#"); bTreeNode* bTree = NULL; creatBiTree(&bTree, qNodes); bTreeNode* copyTree = NULL; copyBTree(bTree, ©Tree); preOrderTraverseTree(copyTree); cout