网站漏洞扫描服务,室内设计网站 知乎,龙岩天宫山索道多少钱,做公益网站需要哪些部门认证一.二叉树的基本概念和性质#xff1a;
1.二叉树的递归定义#xff1a;
二叉树或为空树#xff0c;或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成
2.二叉树的特点#xff1a;
#xff08;1#xff09;每个结点最多只有两棵子树#xff0…一.二叉树的基本概念和性质
1.二叉树的递归定义
二叉树或为空树或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成
2.二叉树的特点
1每个结点最多只有两棵子树即不存在结点度大于2的结点
2子树有左右之分不能颠倒。
3.满二叉树
深度为k且有个结点的二叉树。
1每一层上结点数都达到最大。
2度为1的结点数
4.完全二叉树
深度为k结点数为n的二叉树当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时称为完全二叉树。
1完全二叉树的任意结点左子树的高度-右子树的高度0或1
5.二叉树的性质
1在二叉树的第i层至多有个结点。
2深度为k的二叉树上至多含有个结点。
3) 证明如下 二叉树中全部结点数 除根结点外每个结点必有一个直接前驱即一个分支 1度结点必有1个直接后继2度结点必有2个直接后继 即 叶子数2度结点数1 4具有n个结点的完全二叉树的深度为 5)
对有n个结点的完全二叉树的结点按层序编号则对于任一结点i有 如果i1则结点i是二叉树的根无双亲如果i1则其双亲是i/2如果2in则结点i无左孩子如果则其左孩子是2i如果2i1n则结点i无右孩子如果则其右孩子是2i1 例题
设一棵完全二叉树具有1000个结点则它有489个叶子结点有488个度为2的结点有1个结点只有非空左子树有0个结点只有非空右子树。 二.二叉树、树以及森林的存储结构
1.二叉树的顺序存储结构 用一组地址连续的存储单元以层序顺序存放二叉树的数据元素结点的相对位置蕴含着结点之间的关系。 问顺序存储后能否复原成唯一对应的二叉树形状
若是完全二叉树则可以完全复原下标值为i的双亲左孩子为2i右孩子为2i1。 而对于一般的二叉树的存储将其先补成完全二叉树然后按照完全二叉树的顺序存储方式进行存储而新补上的结点只占位置不存放数据元素。 对于一般二叉树的顺序存储如果是斜树则会浪费很多的存储空间而且插入删除不便。 2.二叉树的链式存储结构
有一个指向根的指针root 二叉链表2个链分别存放左孩子和右孩子。 三叉链表2个链分别存放左孩子和右孩子另外一个指向双亲。 线索链表用空链域存放前驱或后继。 2.1 二叉链表
结点结构
lchilddatarchild
typedef struct BiTreeNode{DataType data;struct BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree; 2.2 三叉链表
结点结构
parentlchilddatarchild
typedef struct BiTreeNode{DataType data;struct BiTreeNode *lchild,*rchild,*parent;
}BiTreeNode,*BiTree; 3.树和森林的存储结构
3.1 树的双亲表示法
对于一个结点来说双亲是一定的。
typedef struct PTNode{DataType data;int parent;
}PTNode;
typedef struct PTree{PTNode nodes[MAX_SIZE];int r,n;
}PTree;
3.2 树的孩子表示法
对于一个结点来说孩子的数量是不一定的为了整体元素结构的一致性采用存储地址的方法。
typedef struct CTNode{int child;struct CTNode *next;
}CTNode;typedef struct CTBox{DataType data;CTNode *firstchild;
}CTBox;
typedef struct CTree{CTBox nodes[MAX_SIZE];int n,r;
}CTree;
3.3 树的双亲孩子表示法
结点结构变为
dataparent下标指向第一个孩子的指针
3.4 树的孩子兄弟表示法
typedef struct CSNode{datatype data;struct CSNode *firstchild,*rightsib;
}CSNode; 三.二叉树、树及森林的基本操作
1.二叉树的遍历
顺着某一条搜索路径寻访二叉树中的结点使得每个结点均被访问一次且仅被访问一次。
1.1 先序遍历
根、左、右。 若二叉树非空则 1访问根结点 2先序遍历左子树 3先序遍历右子树 typedef struct BiNode{int data;struct BiNode *rchild,*lchild;
}BiNode;
void preOrder(BiNode *root){if(root){coutroot-data;preOrder(root-lchild);preOrder(root-rchild);}
} 1.2 中序遍历
左、根、右。 若二叉树非空则 1中序遍历左子树 2访问根结点 3中序遍历右子树 void inOrder(BiNode *root){if(root){inOrder(root-lchild);coutroot-data;inOrder(root-rchild);}
} 中序遍历的非递归算法 1.初始化栈将根结点入栈。 2.如果栈空则结束空树或所有结点处理完毕否则进入下一步。 3.p指向栈顶元素如果p不空则左孩子入栈直到左孩子为空。 4.如果栈不空则出栈输出该结点再将其右孩子入栈。以该结点为本子树的根转步骤2继续。 void InOrder(BiNode *root){stack BiNode* s;BiNode* proot;s.push(p);while(!s.empty()){while(p-lchild){//走到最左边pp-lchild;s.push(p);}ps.top();//弹栈s.pop();coutp-data;if(p-rchild){s.push(p-rchild);}}
} 1.3 后序遍历
左、右、根。 若二叉树非空则 1后序遍历左子树 2后序遍历右子树 3访问根结点 void postOrder(BiNode *root){if(root){postOrder(root-lchild);postOrder(root-rchild);coutroot-data;}
} 1.4 层次遍历
从上到下、从左到右。
初始化队列根结点入队列。
如果队列不空则出队列并访问该结点该结点左孩子入队右孩子入队如果队列为空则层次遍历结束。
void levelOrder(BiNode *root){queue BiNode* s;BiNode* proot;s.push(p);while(!s.empty()){ps.front();s.pop();coutp-data;if(p-lchild){s.push(p-lchild);}if(p-rchild){s.push(p-rchild);}}
} 1.5 对遍历的分析
从前面的三种遍历算法可以知道如果将输出语句抹掉从递归的角度看这三种算法是完全相同的或者说这三种遍历算法的访问路径是相同的只是访问结点的时机不同。
从虚线的出发点到终点的路径上每个结点经过三次。 第一次经过时访问先序遍历第二次经过时访问中序遍历第三次经过时访问后序遍历 1.6 二叉树遍历算法的应用举例
1.6.1 表达式树
算数表达式可以表示为一棵二叉树 中缀表达——对树进行中序遍历即可得到表达式。 前缀表达式不含括号的算数表达式将运算符写在前面操作数写在后面。中缀表达式操作符以中缀形式处于操作数中间。后缀表达式不包含括号运算符放在两个运算对象的后面所有的计算按运算符出现的顺序严格的从左到右进行不再考虑运算符的优先次序 表达式树的构建即给出一个中序序列构建出这棵树
顺序扫描中缀表达式 明确左子树的优先级高
当扫描到的是运算数先检查当前的表达式树是否存在。如果不存在则表示扫描到的是第一个运算数将它作为树根。如果树存在则将此运算数作为前一运算符的右孩子。如果扫描到的是或-将它作为根结点原来的树作为它的左子树。如果扫描到的是*或/则与根结点进行比较。如果根节点也是*或/则根结点应该先执行于是将当前的运算符作为根结点原来的树作为左子树。如果根结点是或-则当前运算符应该先运算于是将它作为右子树的根原来的右子树作为它的左子树。
在遇到运算数时如何知道它前面的运算符是谁这只需要判别根结点有没有右孩子。如果没有右孩子则运算数是根节点的右运算数否则就是根结点右孩子的右运算数。 1.6.2 由先序和中序遍历序列建立二叉树
可以唯一的确定一棵二叉树。
void PreInorder(char preorder[],char inorder[],int first1,int end1,int first2,int end2,BiNode *t){//先序序列从first1到end1中序序列从first2到end2建立一棵二叉树放在t中int m;tnew BiNode;t-datapreorder[first1];//二叉树的根mfirst2;while(inorder[m]!preorder[first1]){//在中序序列中定位根结点的位置m;}//建立左子树if(mfirst2){//左子树为空t-lchildNULL;}else{PreInorder(preorder, inorder, first11, first1m-first2, first2, m-1, t-lchild);}//建立右子树if(mend2){//右子树为空t-lchildNULL;}else{PreInorder(preorder, inorder, first1m1-first2, end1, m1, end2, t-rchild);}
}
void CreateBiTree(char preorder[],char inorder[],int n,BiNode *root){if(n0){rootNULL;}else{PreInorder(preorder, inorder, 0, n-1, 0, n-1, root);}
}
1.6.3 二叉树中叶子结点的统计
先序中序或后序遍历二叉树在遍历过程中查找叶子节点将算法中“访问结点”的操作改为判定是否为叶子结点。
叶子结点左右孩子均为空。
1.6.4 二叉树的深度
空树深度0
左右子树为空深度1
其他深度等于1max左子树深度右子树深度
int get_depth(BiNode *t){if(tNULL){return 0;}else if(t-lchildNULLt-rchildNULL){return 1;}else{int depth;int depth1get_depth(t-lchild);int depth2get_depth(t-rchild);depthmax(depth1,depth2);return depth;}
} 2.树和森林的基本操作
2.1 树以及森林和二叉树的相互转换
1树-二叉树 兄弟加线每一个结点只保留与第一个孩子的连线再进行旋转。 树转换成的二叉树其根结点的右子树一定为空。 想要有右子树就必须要有兄弟。将兄弟作为右子树。 2二叉树-树 结点与其右子树、右子树的右子树加线去掉结点与右子树的连线再进行旋转。 3森林-二叉树 将森林中的每一棵树都先转化为二叉树再令第i棵树作为第i-1棵树的右子树。 4二叉树-森林 断开根结点与右子树的关系再将右子树作为新树依次断开根结点与右子树的关系直至右子树为空得到了多棵二叉树。 再将这些二叉树转化为树。 2.2 树的遍历
先序遍历后序遍历层次遍历
没有中序遍历是因为树不分左右子树
2.3 森林的遍历
先序遍历先序遍历每一棵树中序遍历后序遍历每一棵树 四.二叉树的变形
1.二叉排序树BST
对于二叉排序树的插入和删除操作我们需要改变指针指向的地址而在函数中传递指针只能够改变指针指向的内容所以要传递指针的引用。
1.1 定义具有递归性质
二叉排序树或是一颗空树或是一棵具有以下性质的树
1若它的左子树不空则它左子树上所有结点的值均小于根结点的值。
2若它的右子树不空则它右子树上所有结点的值均大于根结点的值。
3它的左右子树都是二叉排序树
1.2 二叉排序树的查找
在二叉排序树中查找给定k值的过程是 1若root是空树则查找失败 2若kroot-data,则查找成功否则 3若kroot-data则在root的左子树上查找否则 4在root的右子树上查找。 上述过程一直持续到k被找到或者待查找的子树为空。如果待查找的子树为空则查找失败。
只需要查找两个子树之一。
BiNode* search(BiNode *root,int key){if(rootNULL){return NULL;}else{while(key!root-data){if(keyroot-data){rootroot-rchild;}else if(keyroot-data){rootroot-lchild;}else{break;}}return root;}
}
1.3 二叉排序树的插入
若二叉排序树为空树则新插入的结点为新的根结点否则新插入的结点必为一个新的叶子结点其插入位置由查找过程得到。
void insert(BiNode *root,int key){BiNode *p;if(rootNULL){pnew BiNode;p-datakey;p-lchildNULL;p-rchildNULL;}else{if(keyroot-data){insert(root-lchild, key);}else{insert(root-rchild,key);}}
}
二叉排序树的构造
BiSortTree::BiSortTree(int array[],int n){rootNULL;for(int i0;in;i){insertBST(root, array[i]);}
} 二叉排序树构造算法总结 1一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列 2每次插入的新结点都是二叉排序树上新的叶子结点 3找到插入位置后不必移动其它结点仅需修改某个结点的指针 4在左子树/右子树的查找过程与在整棵树上查找过程相同 5新插入的结点没有破坏原有结点之间的关系 注 此处函数参数为指针的引用类型 1只传指针的话只能改变指针最初的指向的内容而不能够改变指针所指向的地址。 2而采用指针的引用实际上改变指针就改变了指针指向的地址。 3这样做还能够直接链接起根结点和孩子之间的指针关系。bt-lchild/rchild 就被赋值为下一级函数所开辟出空间的地址 1.4 二叉排序树的删除
在二叉排序树上删除某个结点之后仍然保持二叉排序树的特性。 1被删除的结点是叶子 删除该结点并将该结点的双亲的孩子指针域赋值为空 2被删除的结点只有左子树或只有右子树 将双亲结点相应的指针域的值指向被删除结点的左/右孩子 3被删除的结点既有左子树又有右子树 以其左子树的最大值或右子树的最小值来代替该结点 以其前驱替代然后再删除前驱结点 void deleteNode(BiNode *bt){BiNode *pbt;if(bt-lchildNULLbt-rchildNULL){//叶子结点btNULL;//该结点的双亲结点的相应孩子指针被赋值为空delete p;//返回时其双亲的左右孩子指针均被赋值为NULL}if(bt-lchildNULL){//该结点的左孩子为空只有右子树btbt-rchild;delete p;}if(bt-rchildNULL){//该结点的右孩子为空只有左子树btbt-lchild;delete p;}else{//左右子树均存在选取其前驱作为新的根结点BiNode *parentbt,*prebt-lchild;while(pre-rchild){//找到左子树值最大的结点parent保存这个结点的双亲结点parentpre;prepre-rchild;}bt-datapre-data;//用该结点的直接前驱替代该结点并删除该结点的直接前驱if(parentbt){parent-lchildpre-lchild;}else{parent-rchildNULL;}delete pre;}
}
二叉排序树的性能取决于二叉树的形状
2.平衡二叉树
2.1 定义
平衡二叉树或者是一颗空树或者是具有下列性质的二叉树 是一棵二叉排序树并且任何结点的左右子树的深度之差不超过1 2.2 构造平衡二叉树 在插入过程中采用平衡旋转技术。
1平衡因子BFBalance Factor
左子树高度 - 右子树高度的值
平衡因子的绝对值大于1就需要进行调整。
2最小不平衡子树
距离插入结点最近的且BF的绝对值大于1的结点。
旋转只需要纠正最小不平衡子树即可。
3右旋 旧根结点为新根结点的右子树新根结点的右子树如果存在为旧根结点的左子树 4左旋 旧根结点为新根结点的左子树新根结点的左子树如果存在为旧根结点的右子树 2.3 四种类型的旋转 1LL型 2RR型 3LR型 最小不平衡子树根结点左子树先左旋最小不平衡子树再右旋 4RL型 最小不平衡子树根结点右子树先右旋最小不平衡子树再左旋 3.最优树——哈夫曼树
3.1哈夫曼编码
1前缀码
对每一个字符规定一个01串作为其代码并要求任一字符的代码都不是其他字符代码的前缀。
2前缀码的平均码长
每个字符频率乘以该字符编码的bit数之和。
3最优前缀码
寻找最小的前缀码的平均码长。
4最优树
称树的带权路径长度最短的一类树为“最优树”。
3.2 哈夫曼树的构造 1初始化 由给定的 n个权值构造n棵只有一个根结点的二叉树从而得到一个二叉树集合。 2选取与合并 在二叉树集合中选取根结点的权值最小的两颗二叉树分别作为左、右子树构造一颗新的二叉树这颗新的二叉树的根结点的权值为其左、右子树根结点的权值之和。 3删除与加入 在二叉树集合中删去作为左、右子树的二叉树并将新建立的二叉树加入到二叉树结合中。 4重复 重复23两步直到二叉树集合中只剩下一颗二叉树。 哈夫曼树的左右子树可以进行交换。
有n个叶子结点的哈夫曼树有2n-1个结点。
3.3 哈夫曼算法的实现
1存储结构
weightlchildrchildparent 由于有n个叶子结点的哈夫曼树有2n-1个结点设置数组长度为2n-1。
2伪代码 1.数组huffTree初始化 所有元素结点的双亲、左右孩子都置为-1. 2.权值给定 数组huffTree的前n个元素的权值给定 3.进行n-1次合并 3.1 在二叉树集合中选取两个权值最小的根结点其下标为i1i2 3.2 将二叉树i1i2合并为一棵新的二叉树 struct element{int weight;int lchild,rchild,parent;
};
void select(struct element huffTree[],int k,int i1,int i2){for(int i0;ik;i){//初始化i1i2if(huffTree[i].parent-1){i1i2i;break;}}for(int i0;ik;i){if(huffTree[i].parent-1huffTree[i].weighthuffTree[i1].weight){i1i;}}for(int i0;ik;i){if(huffTree[i].parent-1i!i1huffTree[i].weighthuffTree[i2].weight){i2i;}}
}
void huffmanTree(struct element huffTree[],int w[],int n){int i1,i2,i;for(i0;i2*n-1;i){huffTree[i].parenthuffTree[i].lchildhuffTree[i].rchild-1;}for(i0;in;i){huffTree[i].weightw[i];}for(in;i2*n-1;i){select(huffTree, i, i1, i2);huffTree[i].weighthuffTree[i1].weighthuffTree[i2].weight;huffTree[i1].parenti;huffTree[i2].parenti;huffTree[i].lchildi1;huffTree[i].rchildi2;}
}
4.堆排序 4.1 堆的定义
堆通常是一个可以被看作一棵完全二叉树的数组对象。
每个结点的值都小于或等于其左右孩子结点的值称为小根堆
或每个结点的值都大于或等于其左右孩子结点的值称为大根堆
特点
1.大根堆的根结点是所有结点中值最大的结点。
2.较大结点靠近根节点但不绝对。
3.每次创建一个堆都使数据基本有序。 4.2 堆排序的思想
首先将待排序的记录序列构造成一个堆大根堆此时选出了堆中所有记录的最大者然后将它从堆中移走并将剩余的记录再调整成堆这样又找出了次大的记录以此类推直到堆中只有一个记录。 4.3 堆的存储
将堆用顺序结构存储则堆就对应了一组序列。
根据完全二叉树的性质
结点i的双亲结点编号为i/2左孩子为2i右孩子为2i1 4.4 堆调整
在一棵完全二叉树中根结点的左右子树均是堆如何调整根结点使整个完全二叉树成为一个堆
建立堆从下向上调整调整堆时从上向下处理。
首先根和他两个孩子中较大的那个比较如果根比较大不做处理如果根比较小则交换交换后再去看交换的结果是否影响下面的堆。 4.5 如何处理堆顶元素
堆顶就是r[1]。
第k次处理堆顶就是将堆顶记录r[1]与r[n-k1]交换。 4.6 代码
void sift(int r[],int k,int end){//当前处理的根结点的编号为k堆中最后一个结点的编号为kint ik;int j2*i;int temp;while(jend){if(jendr[j]r[j1]){//找到左右孩子中较大的那个j;}if(r[i]r[j]){tempr[i];r[i]r[j];r[j]temp;}ij;j2*i;}
}
void heapsort(int r[],int n){//初始化得到一个初始堆for(int kn/2;k1;k--){sift(r,k,n);}for(int k1;kn;k){//最大的元素往后挪堆逐渐缩小r[0]r[1];r[1]r[n-k1];r[n-k1]r[0];sift(r,1,n-k);}
}
时间复杂度 不稳定排序
