分享内容后序加中序构建二叉树二叉搜索树的定义二叉搜索树的遍历和查询构建二叉树知识回顾根据二叉树遍历序列构建一棵二叉树的两种方式:(1)先序加中序构建二叉树(2)后序加中序构建二叉树由先序序列或后序序列确定根结点,再由中序序列进行左右子树的分割。先序加中序构建二叉树(知识回顾)指定先序和中序序列创建二叉树的步骤总结:1、根据先序序列(第一个字符)确定根,并存储到数组(此时保存的是根结点的值)2、记录根结点在数组中的下标3、找出根字符在中序序列中的下标i,算出左右子树的范围(确定子树的先序序列和中序序列)4、递归创建左右子树(并记录子树根结点的下标)5、左右子树都创建好之后,两个子树的根结点下标保存到根结点的leftchild、rightchild。子树创建好之后,才知道子树的根结点保存在数组哪个位置递归出口:指定的序列长度不足1时。结构体和全局变量:structtreenode{intls,rs;//ls:左孩子结点编号,rs:右孩子结点编号charvalue;};tree node tree[LEN];//保存构建的二叉树charpreorder[LEN];//先序序列charinorder[LEN];//中序序列intp1;//在tree[]中放入结点的位置指针递归函数:intbuildTree(intpreStart,intpreEnd,intinStart,intinEnd);函数功能:根据先序序列和中序序列创建二叉树,保存到tree[]。返回值:返回二叉树的根结点的编号(下标)。参数:preStart、preEnd:先序序列的下标范围。inStart、inEnd:中序序列的下标范围。其他说明:先序序列和中序序列分别保存在全局变量preorder[]、inorder[]中。intbuildTree(intpreStart,intpreEnd,intinStart,intinEnd){//递归出口,序列长度不足1,返回空结点编号if(preStartpreEnd||inStartinEnd)return0;// 根结点的值先放入tree[]中p指向的位置tree[p].valuepreorder[preStart];// 保存根结点的下标introotIdptt;//找到根结点在中序序列中的下标iintiinStart;while(iinEndpreorder[preStart]!inorder[i])i;// 算出左子树的长度intleni-inStart;// 递归构建左右子树,并把返回的子树跟结点编号存入根结点的 1s,rstree[rootId].lsbuildTree(preStart1,preStartlen,inStart,i-1);tree[rootId].rsbuildTree(preStartlen1,preEnd,i1,inEnd);returnrootId;//返回根在tree数组中的下标后序加中序构建二叉树后序加中序构建二叉树(模版代码)intbuildTree(intpostStart,intpostEnd,intinStart,intinEnd){//递归出口,序列长度不足1,返回空结点编号if(postStartpostEnd||inStartinEnd)return0;// 根结点的值(后序序列最后一个值)先放入tree[]中p指向的位置tree[p].valuepostorder[postEnd];//后序序列最后一个值是根的值// 保存根结点的下标introotIdpt;// 找到根结点在中序序列中的下标iintiinStart;while(iinEndpostorder[postEnd]!inorder[i])//后序序列最后一个值是根的值i;//算出左子树的长度intleni-inStart;// 递归构建左右子树,并把返回的子树跟结点编号存入根结点的 1s,rstree[rootId].lsbuildTree(postStart,postStartlen-1,inStart,i-1);//左右子树的序列范围不要传错tree[rootId].rsbuildTree(postStartlen,postEnd-1,i1,inEnd);returnrootId;//返回根在tree数组中的下标求先序排列给出一棵二叉树的后序与中序排列,求出它的先序排列。约定树结点用不同的大写字母表示,序列长度 8。【输入描述】两行,每行一个字符串,分别表示后序和中序排列。【输出描述】一个字符串,表示所求先序排列。【输入样例】DBGEFCADBAEGCF【输出样例】ABDCEGF本题要求先根据后序与中序序列创建二叉树,然后先序遍历得到先序序列。1、定义结构体和全局变量:structtreenode{intls,rs;//ls:左孩子结点编号,rs:右孩子结点编号charvalue;};tree_node tree[LEN];//保存构建的二叉树,下标1开始放charpostorder[LEN];//后序序列charinorder[LEN];//中序序列intp1;//在tree[]中放入结点的位置2、编写“后序加中序构建二叉树”的递归函数intbuildTree(intpostStart,intpostEnd,intinStart,intinEnd){//递归出口,序列长度不足1,返回空结点编号if(postStartpostEnd||inStartinEnd)return0;// 根结点的值(后序序列最后一个值)先放入tree[]中p指向的位置tree[p].valuepostorder[postEnd];// 保存根结点的下标introotIdp;// 找到根结点在中序序列中的下标iintiinStart;while(iinEndpostorder[postEnd]!inorder[i])i;// 算出左子树的长度intleni-inStart;// 递归构建左右子树,并把返回的子树跟结点编号存入根结点的 1s,rstree[rootId].lsbuildTree(postStart,postStartlen-1,inStart,i-1);tree[rootId].rsbuildTree(postStartlen,postEnd-1,i1,inEnd);returnrootId;//返回根在tree数组中的下标}3、编写先序遍历的递归函数// 先序遍历voidpreOrder(introot){if(root!0){//非空结点couttree[root].value;//访问根preOrder(tree[root].ls);//递归遍历左子树preOrder(tree[root].rs);//递归遍历右子树}}4、实现main函数1)读入并保存后序、中序序列2)构建二叉树3)先序遍历二叉树intmain(){// 读入cinpostorderinorder;intlenstrlen(postorder);//序列长度introotidbuildTree(0,len-1,0,len-1);preOrder(rootid);//遍历时传入根结点下标return0;}【注意】使用strlen()需要#includecstring完整代码#includeiostream#includecstringusingnamespacestd;#defineLEN9structtreenode{intls,rs;//ls:左孩子结点编号,rs:右孩子结点编号charvalue;}tree_node tree[LEN];//保存构建的二叉树,下标1开始放charpostorder[LEN];//后序序列charinorder[LEN];//中序序列intp1;//在tree[]中放入结点的位置下标// 根据后序序列和中序序列创建二叉树// 返回二叉树的根结点的编号(下标)// 后序序列和中序序列分别保存在全局变量postorder[]、inorder[]中// poststart、postEnd:后序序列的下标范围// inStart、inEnd:中序序列的下标范围intbuildTree(intpostStart,intpostEnd,intinStart,intinEnd){//递归出口,序列长度不足1,返回空节点编号if(postStartpostEnd||inStartinEnd)return0;// 根结点的值(后序序列最后一个值)先放入tree[]中p指向的位置tree[p].valuepostorder[postEnd];// 保存根结点的下标introotIdp;// 找到根结点在中序序列中的下标intiinStart;while(iinEndpostorder[postEnd]!inorder[i])i;// 算出左子树的长度intleni-inStart;// 递归构建左右子树,并把返回的子树跟结点编号存入根结点的 1s,rstree[rootId].lsbuildTree(postStart,postStartlen-1,inStart,i-1);tree[rootId].rsbuildTree(postStartlen,postEnd-1,i1,inEnd);returnrootId;//根在tree数组中的下标}// 先序遍历voidpreOrder(introot){if(root!0){//非空结点couttree[root].value;//访问根preOrder(tree[root].1s);//递归遍历左子树preOrder(tree[root].rs);//递归遍历右子树}}intmain(){// 读入cinpostorderinorder;intlenstrlen(postorder);//序列长度introotidbuildTree(0,len-1,0,len-1);preOrder(rootid);return0;}二叉搜索树二叉搜索树(binary search tree)是满足以下条件的二叉树:(1)对于根结点,左子树中所有结点的值根结点的值右子树中所有结点的值。(2)任意结点的左、右子树也是二叉搜索树,即同样满足条件1。二叉搜索树简称BST,又称二叉排序树。【注意】空树也是二叉搜索树。二ヌ搜索树的特点1、二叉搜索树的中序序列总是是升序的,因为· 中序遍历遵循“左 根右”的遍历顺序· 而二叉搜索树满足“左子结点根结点右子结点”的大小关系2、二叉搜索树的最小值位于最左叶子结点,即树的最左下结点3、二叉搜索树的最大值位于树的最右下结点二ヌ搜索树的表示和存储对于不涉及插入和删除操作的二叉搜索树,一般采用静态结点数组的方式表示。1、结点结构体包含左右子结点下标:structNode{intvalue;//结点的值intleft;//左子结点的下标intright;//右子结点的下标};2、一个静态结点数组保存树的结点Node tree[SIZE];二ヌ搜索树的遍历二叉搜索树的遍历和普通二叉树一样:● 层序遍历借助队列实现● 先序、中序、后序遍历用递归法实现对于二叉搜索树,中序遍历最常用,因为中序遍历可以得到升序序列。#define NULLID 0//定义常量NULLID表示空结点编号// 中序遍历二叉树voidinOrder(introot){if(rootNULLID)return;inOrder(tree[root].left);couttree[root].value ;inOrder(tree[root].right);//时间复杂度为O(n)}查找最小/最大值由二叉搜索树的性质可得,二叉搜索树上的最小值位于最左下结点,最大值位于最右下结点。// 返回二叉搜索树的最小值(最左结点)intfindMin(introot){if(rootNULLID)returnNULLID;while(tree[root].left!NULLID){roottree[root].left;}returnroot;}// 返回二叉搜索树的最大值(最右结点)intfindMax(introot)if(rootNULLID)returnNULLID;while(tree[root].right!NULLID)roottree[root].right;}returnroot;}时间复杂度为O(h),h是二叉树的深度。查找某个值在以root为根结点的二叉搜索树中查找一个值为num的结点:若root为空,没找到。若root的权值等于num,找到了。若root的权值大于num,在root的左子树中继续搜索。若root的权值小于num,在root的右子树中继续搜索。在左右子树查找是更小规模的同类问题,用递归实现。// 在二叉搜索树中搜索num,找到返回结点下标,没找到返回0。intsearch(introot,intnum){if(rootNULLID)returnNULLID;if(tree[root].valuenum)returnroot;if(tree[root].valuenum)//在右子树中搜索returnsearch(tree[root].right,num);else//在左子树中搜索returnsearch(tree[root].left,num);}二叉搜索树的查找操作每比较一次深入一层。最多进行二叉树的深度次比较,即时间复杂度为O(h),h是二叉树的深度。二叉搜索树的插八和制除操作除了遍历、查找之外,二叉搜索树在实际应用中经常需要进行插入和删除操作。插入和删除过程中需要动态增加、删除结点,如果继续使用静态数组会有容量不足的问题。所以对于涉及插入和删除操作的二叉搜索树推荐使用链式存储而不是静态数组。下节课内容:· 二叉搜索树的链式存储· 二叉搜索树的插入和删除操作判断二叉搜索树给定一棵二叉树,要求判断是否二叉搜索树。【输入描述】第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n(1 n 10),根结点为1。接下来有n行,依次对应二叉树的n个结点。每行有3个整数,分别表示该结点的值、左儿子和右儿子的结点编号。如果第2个(第3个)数为-1则表示没有左(右)儿子。【输出描述】是二叉搜索树则输出“yes,否则输出“no”。本题要求先根据输入保存二叉树,然后判断是否二叉搜索树。有效的二叉搜索树的中序序列总是升序的。反之可以根据中序序列判断二叉树是否二叉搜索树:在中序遍历的过程中,检查当前访问的结点的数据总是大于上一个,否则这个就不是二叉搜索树。1、定义结点(结构体)和数组结构体只需要存储每个结点的值,以及左右孩子编号。structNode{intvalue;//结点的值intleft;//左子结点的下标intright;//右子结点的下标};#defineSIZE101//数组的大小为最大结点数1(结点编号从1开始)Node tree[SIZE];2、在中序遍历过程中判断是否二叉搜索树intpreValINT MIN;//保存前一个值,初始值为最小负整数boolisBSTtrue;//标记是否二叉搜索树// 中序遍历二叉树 同时判断是否合规的二叉搜索树voidinOrder(introot){if(root-1)return;inOrder(tree[root].left);// 先判断(非升序说明不是二叉搜索树)if(tree[root].valuepreVal){isBSTfalse;return;// 出结果了,直接终止遍历}// 后保存preValpreValtree[root].value;inOrder(tree[root].right);}INT MIN:是C/C标准库climits中预定义的宏常量,表示int类型变量能存储的最小负整数。3、main函数1)读入并保存树2)中序遍历并判断是否二叉搜索树4)输出结果intmain(){// 读入和保存树cinn;for(inti1;in;i){cintree[i].valuetree[i].lefttree[i].right;}inOrder(1);if(isBST)coutyes;elsecoutno;return0;}完整代码#includeiostream#includeclimitsusingnamespacestd;#defineSIZE101#defineNULLID-1//本题-1是空节点编号structNode{intvalue;//结点的值intleft;//左子结点的下标intright;//右子结点的下标};Node tree[SIZE];intn;intpreValINT MIN;// 保存前一个值,初始值为最小负整数boolisBSTtrue;7tric// 中序遍历二叉树,同时判断是否合规的二叉搜索树voidinorder(introot){if(rootNULLID)return;inOrder(tree[root].left);//左子树递归//先判断(非升序说明不是二叉搜索树)if(tree[root].valuepreVal){isBSTfalse;return;// 出结果了,直接终止遍历}//后保存preValtree[root].value;inOrder(tree[root].right);//右子树递归}intmain(){cinn;for(inti1;in;i){cintree[i].valuetree[i].lefttree[i].right;}inOrder(1);if(isBST)coutyes;elsecoutno;return0;}本次课程的知识点根据后序与中序序列创建二叉树二叉搜索树的定义和特点二叉搜索树的遍历和查询1、在二叉搜索树中,以下哪种遍历方式可以生成一个递增的有序序列?BA、前序遍历B、中序遍历C、后序遍历D、层序遍历2、在二叉搜索树中,查找一个特定值的时间复杂度是多少?(n表示结点数。h表示树的深度)DA、O(1)B、O(logn)C、O(n)D、O(h)第k小的值给定一棵n个结点的二叉搜索树,要求其中第k小的值(k n)。数据保证输入的是二叉搜索树。【输入描述】第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n(1 n 10),根结点为1。接下来有n行,依次对应二叉树的n个结点。每行有3个整数,分别表示该结点的值、左儿子和右儿子的结点编号。如果第2个(第3个)数为-1则表示没有左(右)儿子。最后一行一个整数表示k(k n)。【输出描述】一个整数表示二叉搜索树中第k小的值。【提示】中序遍历二叉搜索树,遍历到第k个结点输出。#includeiostreamusingnamespacestd;#defineSIZE101#defineNULLID-1//本题-1是空节点编号structNode{intvalue;//结点的值intleft;//左子结点的下标intright;//右子结点的下标};Node tree[SIZE];intn,k;intcnt0;// 中序遍历二叉树,遍历到个结点输出voidinOrder(introot){if(rootNULLID)return;inOrder(tree[root].left);//左子树递归//cout tree[root].value ;cnt;if(cntk){couttree[root].value;}inOrder(tree[root].right);//riy}intmain(){cinn;for(inti1;in;i){cintree[i].valuetree[i].lefttree[i].right;}cink;inOrder(1);return0;}