562010年计算机专业统考试题数据结构

第6章树和二叉树基本内容1、知识点（1）二叉树的性质及证明方法，并把这种方法推广到K叉树。（2）二叉树遍历的递归和非递归算法（前序、中序、后序、层次）。遍历的应用算法，如求二叉树的高度、各节点的层次数、度为0、1、2的结点数，二叉树的相似、全等、复制等。（3）由二叉树遍历的前序和中序或后序和后序或中序和层次序列可以唯一的确定一课二叉树，要会手工模拟和编写算法。（4）二叉树的线索化，实质是建立结点在相应序列中与其前驱和后继之间的直接联系。（5）完全二叉树的高度及其双亲与子女的编号关系，二叉树顺序存储结构和链式存储结构的相互转化算法。（6）树、森林和二叉树的相互转换。（7）哈夫曼树的定义、构造及求哈夫曼编码。基本内容2、树的定义及相关概念树是n个结点的有限集，在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点，（2）当n1时，其余结点可分为m个互不相交的有限集T1，T2，…Tm，其中每一个集合本身又是一棵树，并且称为根的子树。3、二叉树的定义每个结点最多只有两棵子树，二叉树的子树有左右之分，次序不能颠倒。二叉树或者为空，或者由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成（可以为空树）。基本内容4、二叉树的性质（1）在二叉树的第i层上至多有结点。（2）深度为k的二叉树的最大结点数为（3）对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。（4）具有n个结点的完全二叉树的深度为。（5）如果对一棵有n个结点的完全二叉树的结点按层次编号，则对任一结点i有：a、若i=1，则结点i是二叉树的根，无双亲，若i1，则其双亲是；b、若2in，则结点i为左孩子，否则其左孩子是2i；c、若2i+1n，则结点i无右孩子，否则右孩子为2i+1。12i12k1log2n2/i基本内容5、二叉树的存储结构（1）顺序存储（2）链式存储（二叉链表）typedefstructBiTree{ElemTypedata;structBiTree*lchild,*rchild;}BiTNode,*BiTree;基本内容6、二叉树的遍历（1）递归算法（2）非递归算法voidPreOrder(BitreeT){InitStack(S);Push(S,T);while(!StackEmpty(S)){while(Gettop(S,p)&&p){visit(p-data);push(S,p-lchild);}/*向左走到尽头*/pop(S,p);if(!StackEmpty(S)){pop(S,p);push(S,p-rchild);/*向右一步*/}}}voidPreOrder(BitreeT){InitStack(S);Push(S,T);while(!StackEmpty(S)){pop(S,p);visit(p-data);if(p-rchild!=NULL)push(S,p-rchild);if(p-lchild!=NULL)push(S,p-lchild);}}voidInOrder(BitreeT){InitStack(S);p=T;while(!StackEmpty(S)||p!=NULL){while(p!=NULL){push(S,p);p=p-lchild;}if(!StackEmpty(S)){pop(S,p);visit(p-data);p=p-rchild;}}}voidPostOrder(BitreeT){Bitreestack[],p;inttag[],top=0;p=T;while(top0||p!=NULL){while(p!=NULL){top++;stack[top]=p;tag[top]=0;p=p-lchild;}if(top0){p=stack[top];while(tag[top]==1){top--;visit(p-data);p=stack[to}if(top0){p=stack[top];p=p-rchild;tag[top]=1;}}}}voidLayerOrder(BitreeT{InitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);visit(p-data);if(p-lchild)EnQueue(Q,p-lchild);if(p-rchild)EnQueue(Q,p-rchild);}}基本内容7、线索二叉树前序：结点x的后继为其左孩子的根，若没有左孩子，则为右孩子的根，若既无左孩子又无右孩子，后继为祖先结点的右孩子的根。中序：结点x的右孩子不为空，后继为其右孩子的根结点，若右孩子为空，后继为其双亲结点。后序：若结点x是二叉树的根，后继为空；若结点x是其双亲的右孩子或是左孩子且双亲没有右孩子，后继为双亲；若结点x是其双亲的左孩子且双亲有右孩子，后继为双亲的右孩子中按后序遍历的第一个结点。基本内容8、树和森林（1）树的存储结构双亲表示法孩子表示法孩子兄弟表示法（2）森林和二叉树的转换基本内容9、哈夫曼树及其应用（1）哈夫曼树的概念（2）哈夫曼树的构造不唯一，但带权路径长度相同（3）哈夫曼编码基本内容10、树与等价问题确定等价类的算法：（1）令S中每个元素各自形成一个只含单个元素的子集，记作S1，S2，…，Sn。（2）重复读入m个序偶对，对每个读入的偶对x,y，判定x和y所属子集。当m个序偶对都被处理后，S1，S2，…，Sn中所有非空子集极为S的R等价类。例题1、求二叉树中叶子结点的数目intLeafCount_BiTree(BitreeT){if(!T)return0;/*空树没有叶子*/elseif(!T-lchild&&!T-rchild)return1;elsereturnLeaf_Count(T-lchild)+Leaf_Count(Trchild);}例题2、交换所有结点的左右子树。voidBitree_Revolute(BitreeT){if(T!=NULL)T-lchild-T-rchild;if(T-lchild)Bitree_Revolute(T-lchild);if(T-rchild)Bitree_Revolute(T-rchild);}例题3、求二叉树中以值为x的结点为根的子树深度。intGet_Sub_Depth(BitreeT,intx){if(T-data==x){printf(%d\n,Get_Depth(T));exit1;}else{if(T-lchild)Get_Sub_Depth(T-lchild,x);if(T-rchild)Get_Sub_Depth(T-rchild,x);}}intGet_Depth(BitreeT){if(!T)return0;else{m=Get_Depth(T-lchild);n=Get_Depth(T-rchild);return(mn?m:n)+1;}}例题4、判断两棵树是否相似的递归算法。intBitree_Sim(BitreeB1,BitreeB2){if(!B1&&!B2)return1;elseif(B1&&B2)return(Bitree_Sim(B1-lchild,B2-lchild)&&Bitree_Sim(B1-rchild,B2-rchild))elsereturn0;}例题5、判断一二叉树是否为完全二叉树。intFull_Bitree(BitreeT){InitQueue(Q);flag=0;EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);if(!p)flag=1;elseif(flag)return0;else{EnQueue(Q,p-lchild);EnQueue(Q,p-rchild);}}return1;}例题6、在二叉树中查找值为x的结点，编写算法输出x的所有祖先。voidPostOrder(BitreeT，intx){Bitreestack[],p;inttag[],top=0;p=T;while(top0||p!=NULL){while(p!=NULL&&p-data!=x){top++;stack[top]=p;tag[top]=0;p=p-lchild;}if(p-data==x){printf(“”);for(i=1;i=top;i++)printf(stack[i]-data);return;}while(tag[top]==1&&top1)top--;if(top0){p=stack[top];p=p-rchild;tag[top]=1;}}}例题7、将二叉树表示的表达式按中缀形式输出，并加上相应的括号。分析：当根结点运算符优先级高于左子树（或右子树）根结点运算符时，须加括号。intprecede(charoptr1,optr2){swith(optr1){case’+’:case’-’:if(optr2==‘+’||’optr2==‘-’)return0;elsereturn-1;case’*’:case’/’:if(optr2==‘+’||optr2=‘-’)return1;elsetrturn0;}}voidinorderexp(Bitreebt){if(bt){if(bt-lchild!=NULL){m=precede(bt-data,bt-lchild-data);if(m==1)printf(“(“);inorderexp(bt-lchild);if(m==1)printf(“)”);}printf(bt-data);if(bt-rchild!=NULL){m=precede(bt-data,bt-rchild-data);if(m==1)printf(“(“);inorderexp(bt-rchild);if(m==1)printf(“)”);}}}例题8、以孩子兄弟连标作为存储结构，设计递归和非递归算法求树的深度。intheight(CSTreebt){if(bt==NULL)return0;else{hc=height(bt-firstchild);hs=height(bt-nextsibling);if(hc+1hs)returnhc+1;elsereturnhs;}}intheight(CSTreebt){if(bt==NULL)teturn0;else{front=1;rear=1;last=1;h=0;q[rear]=bt;while(front=last){t=q[front];front++;while(t!=NULL){if(t-firstchild){rear++;q[rear]=t-firstchild}t=t-nextsibling;}if(frontlast){h++;last=rear;}}returnh;}}例题9、由二叉树的前序和中序序列建立一棵二叉树。charPred,Ind;BitreeBuild_Sub(intPre_S,intPre_E,intIn_S,intIn_E){sroot=(BTNode*)malloc(sizeof(BTNode));sroot-data=Pre[Pre_S];for(i=In_S;In[i]!=sroot-data;i++);leftl=i-In_S;rightl=In_E-i;if(leftl){lroot=Build_Sub(Pre_S+1,Pre_S+leftl,In_S,In_S+leftl-1)；sroot-lchild=lroot;}if(rightl){rroot=Build_Sub(Pre_E-rightl+1,Pre_E,In_E-rightl+1,In_E);sroot-rchild=rroot;}retur