考研论坛

 找回密码
 立即注册
查看: 852|回复: 15

计算机考研:数据结构常用算法精析(6)

[复制链接]

33万

主题

33万

帖子

100万

积分

论坛元老

Rank: 8Rank: 8

积分
1007237
发表于 2017-8-6 14:43:22 | 显示全部楼层 |阅读模式
数据结构是计算机考研408计算机学科专业基础综合的重要组成部分,考生需要认真复习,尤其是对于数据结构中一些常用的算法问题,考生一定要弄懂弄会,理解的去掌握。新东方在线小编下面一一为大家分析一下,帮助考生更好地去掌握。
        第六章
    结点的出度(OD):结点拥有的非空子树数目。
    结点的入度(ID):指向结点的分支(或有向弧、指针)的数目。
    树的度(TD):树中结点出度的最大值。
    结点的度:该结点的出度
    例如 在下述结论中,正确的是( D )【南京理工大学 1999 一、4 (1分)】
    ①只有一个结点的二叉树的度为0; ②二叉树的度为2;
③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
    A.①②③ B.②③④ C.②④ D.①④
    有关二叉树下列说法正确的是( B )【南京理工大学 2000 一、11 (1.5分)】
    A.二叉树的度为2 B.一棵二叉树的度可以小于2
    C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2
    有序树和无序树:若树中任一结点的各子树从左到右有序,则该树为有序树(强调子树的次序),否则为无序树。(只强调各子树之间相对有序,而并不像二叉树那样,当只有一个子树是要么是左子树要么是右子树。而在有序树中,只有一个子树的有序树就不唯一了。)
    例题:在下列情况中,可称为二叉树的是( B )
    A.每个结点至多有两棵子树的树 B. 哈夫曼树 C.每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E.以上答案都不对
    C错在有序树不一定是二叉树,有序只是子树的相对保持有序,并没有严格定义具体那颗子树就是第几颗子树。
    森林(或树林):m(m≥0) 棵互不相交的有序树的有序集合。
    深度=h(h≥1)的K(K>1)叉树至多有( -1)/(K-1)个结点。
    包含n(n≥0)个结点的K(K>1)叉树的最小深度为:
    证:设有n个结点的K叉树的深度为h,若该树h-1层都是满的,即每层有最大结点数
-1(1≤i≤h-1),且其余结点都落在第h层,则该树的深度达最小,如图6.11所示:
                    
回复

使用道具 举报

0

主题

7652

帖子

1万

积分

论坛元老

Rank: 8Rank: 8

积分
16082
发表于 2017-8-6 15:50:43 | 显示全部楼层
    或:(Kh-1 -1)
    即:Kh-1
    取对数:(h-1)
    因为h为正整数,所以:h=
    含有n(n ≥1)个结点的完全二叉树的深度
    n个叶结点的非满的完全二叉树的高度是élog2nù+1。(最下层结点数>=2)。
    设完全二叉树BT结点数为n,结点按层编号。对BT中第i结点(1≤i≤n),注意结点编号从1开始,在数组存储时也是从数组1开始,若题目已然确定从0开始,则在计算孩子父亲结点时都需要重新变换一下。
    有:
    (1)若i=1,则i结点(编号为i的结点)是BT之根,无双亲;否则( i>1),parent(i)= ,即i结点双亲的编号为 ;
    (2)若2i>n,则i结点无左子,否则Lchild(i)=2i,即i结点的左子位于第2i号结点;
    (3)若2i+1>n,则i结点无右子,否则Rchild(i)=2i+1,即i结点的右子位于第2i+1号结点。
    证明:采用数学归纳法,先证(2)和(3)。
    设n个结点的完全二叉树如图所示。
    i=1时,显然 i 结点的左子编号为2,i的右子编号为2+1=3,除非2>n , 3>n 。
    设对i结点,命题(2)、(3)成立,即Lchild(i)=2i,Rchild(i)=2i+1。根据按层编号规则,i+1时有:
    Lchild(i+1)=(2i+1)+1=2(i+1),除非2(i+1)>n,
    Rchild(i+1)=(2i+1)+1+1=2(i+1)+1,除非2(i+1)+1>n,
    故(2)、(3)得证。
    再证(1),它可看作是(2)、(3)的推广。
    因Lchild(j)=2j,所以Parent(2j)=j,令2j=i,有 Parent(i)=i/2= (i/2为正整数);
    又:Rchild(j)=2j+1,所以Parent(2j+1)=j,令2j+1=i (i=3,5,7…),有:
    Parent(i)=(i-1)/2= ,证毕。
    n
    2i
    2i+1
    1
    2
    3
    2i+1+1
    2i+1+2
    i
    i+1
                    
回复 支持 反对

使用道具 举报

0

主题

7708

帖子

1万

积分

论坛元老

Rank: 8Rank: 8

积分
16188
发表于 2017-8-6 16:55:03 | 显示全部楼层
    例题:一棵完全二叉树上有1001个结点,其中叶子结点的个数是( )【西安交通大学 1996 三、2 (3分)】
    A. 250 B. 500 C.254 D.505 E.以上答案都不对 501
    例题1:由二叉树结点的公式:n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1,
因为n=1001,所以1002=2n0+n1,在完全二叉树树中,n1只能取0或1,在本题中只能取0,故n=501,因此选E。
    例题2:高度为K的完全二叉树至少有_ __个叶子结点。(刚好第K上只有一个叶子时,高度为K,N= -1+1=
例题3:在顺序存储的二叉树中,编号为i和j的两个结点处在同一层的条件是
    用顺序存储二叉树时,要按完全二叉树的形式存储,非完全二叉树存储时,要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t
,则结点i和j在同一层上的条件是ëlog2sû=ëlog2tû。
        二叉树的存储结构
        1.顺序存储结构
    用一组连续的存储单元(一维数组)存储二叉树中元素,称为二叉树的顺序存储结构。描述如下:
    #define maxsige 1024 //二叉树结点数最大值//
    typedef datatype sqtree [maxsize];
    若说明sqtree bt; 则( bt[o] bt[1] … bt[maxsize-1])为二叉树的存储空间。每个单元bt
可存放类型为datatype的树中元素。
    2.链式存储结构
    二叉结中结点的一般形式为:
    lchild
    data
    rchild
    遍历的递归算法
    void preorder( BTptr T) //对当前根结点指针为T的二叉树按前序遍历//
    {
    if (T) { visit(T); // 访问T所指结点 //
    preorder(T–>Lchild); //前序遍历T之左子树//
    preorder(T–>Rchild); //前序遍历T之右子树//
    }
    }
    void Inorder (BTptr T) //对当前根结点指针为T的二叉树按中序遍历//
    {
    if (T) { Inorder( T->Lchild); //中序遍历T之左子树//
    visit(T); //访问T所指结点//
    Inorder(T->Rchild); //中序遍历T之右子树//
    }
    }
    void postorder ( BTptr T) //对当前根结点指针为T的二叉树按后序遍历//
    {
    if (T) { postorder(T–>Lchild); //后序遍历T之左子树//
    postorder(T–>Rchild); //后序遍历T之右子树//
    visit(T); //访问T所指结点//
    }
    }
    从上述三个算法中看出,若抹去
visit(T)语句,则三个算法是一样的,可以推断,这三个算法的递归路线是一致的(走的线路是一样的,只是对结点的访问时间不同而已,前序是第一次碰到就访问,中序是第一次返回时访问,后序是第二次返回时访问。
                    
回复 支持 反对

使用道具 举报

0

主题

7800

帖子

1万

积分

论坛元老

Rank: 8Rank: 8

积分
16366
发表于 2017-8-6 18:33:27 | 显示全部楼层
  遍历非递归算法
        1.前序遍历二叉树的非递归算法
    算法思路:设一存放结点指针的栈S。从根开始,每访问一结点后,按前序规则走左子树,但若该结点右子树存在,则右子指针进栈,以便以后能正确地遍历相应放回到该右子树上访问。
    算法描述: void Preoder-1(BTptr T) //前序非递归遍历二叉树T//
    { BTptr p;stacktype s;
    Clearstack(s);
    push(s,T); //置栈S为空、根指针T进栈//
    while (!Emptystack(s) )
    { p=pop(s); //出栈,栈顶=>P//
    while (p)
    {
    visit (p); //访问p结点//
    if (p–>Rchild) push(s,p–>Rchild); //右子存在时,进栈//
    p=p–>Lchild;
    } //向左走//
    }
    }
    说明:内部循环是从P结点出发一直走到最左,走的过程中保存了每一个右子树的地址,(因为右子树还没有被访问)而且是先进后出的,即先保存的比后保存的更先被用作返回地址,所以是用栈。外循环正好是当内部循环不下去的时候,退一栈的情形。即换成他的右子树
    2.中序遍历二叉树的非递归算法
    算法思路:同前序遍历,栈S存放结点指针。对每棵子树(开始是整棵二叉树),沿左找到该子树在中序下的第一结点(但寻找路径上的每个结点指针要进栈),访问之;然后遍历该结点的右子树,又寻找该子树在中序下的第一结点,..….直到栈S空为止。
                    
回复 支持 反对

使用道具 举报

0

主题

7708

帖子

1万

积分

论坛元老

Rank: 8Rank: 8

积分
16188
发表于 2017-8-6 19:59:48 | 显示全部楼层
  算法描述: void Inorder-1 (BTptr T) // 中序非递归遍历二叉树T//
    { BTptr p; stacktype s;
    Clearstack(s);
    push (s,T); //置栈S空、根指针进栈//
    while (!Emptystack(s))
    {
    while ((p=Getstop (s))&& p) // 取栈顶且栈顶存在时//
    push(s,p->lchild); //p之左子指针进栈//
    p=pop(s); //去掉最后的空指针//
    if (!Emptystack (s))
    { p=pop(s); //取当前访问结点的指针=>P//
    visit(p); //访问P结点//
    push(s,p-> Rchild); //遍历P之右子树//
    }
    }
    }
    说明:和前序不一样,这里的栈保存的是根结点的地址(因为中序遍历先访问左子树,而根结点没有被访问到。而前序遍历不一样,他一开始就访问根结点,所以他不保存根结点的地址而是保存右子树的地址,因为右子树还没有被访问。总之,用栈就是为了帮我们保存还没有被访问的地址,以便将来我们能找到返回的地址)
        3.后序遍历二叉树的非递归算法
    算法思路:后序非递归遍历较之前序、中序算法要复杂一些。原因是对一个结点是否能访问,要看它的左、右子树是否遍历完,所以每结点对应一个标志位—tag。tag=0,表示该结点暂不能访问;tag=1,表示该结点可以访问。其实是区分这次返回是遍历完左子树返回的还是遍历完右子树返回的,如果是左子树返回那么就不能访问根结点,如果是右子树返回的就能访问根结点。
    当搜索到某P结点时,先要遍历其左子树,因而将结点地址P
及tag=0进栈;当P结点左子树遍历完之后,再遍历其右子树,又将地址P及tag=1进栈;当P结点右子树遍历完后(tag=1),便可以对P结点进行访问。
    栈元素类型: typedef struct
    {BTptr q; // 存放结点地址 //
    int tag; //存放当前状态位//
    }stype ;
                    
回复 支持 反对

使用道具 举报

0

主题

7652

帖子

1万

积分

论坛元老

Rank: 8Rank: 8

积分
16082
发表于 2017-8-6 20:19:51 | 显示全部楼层
  算法步骤如下:
    ①若二叉树T=∧(空树),返回,算法终止;
    ②初始化:置栈S空,根指针T=>p;
    ③反复以下过程,直到p=∧且栈S=∧时算法终止:
    若p≠∧,(p,o)进栈,p=p–>Lchild (遍历左子树) ,……,直到 p=∧;出栈, 栈顶=>(p,
tag);若tag=0,(p,1)进栈,p=p–>Rchild(遍历右子树),否则,访问p结点,并置p=∧。
    算法描述:void postorder-1(BTptr T) //后序非递归遍历二叉树T//
    {
    int tag; BTptr p; stype sdata;
    Clearstack (s); // 置栈空 //
    p=T;
    do {
    while (p)
    {
    sdata.q=p; sdata.tag=0;
    push (s, sdata); // (p,0)进栈//
    p=p–>Lchild; //遍历p之左子树//
    }
    sdata=pop(s); //退栈
    p=sdata.q; //取指针
    tag=sdata.tag;//状态位//
    if (tag= =0)//从左子树返回时,根的tag=0
    {
    sdata. q=p;
    sdata.tag=1; //这时要进入根的右子树了,所以将根的tag=1,
    //下次碰到根时就可以访问了
    push(s,sdata); // (p,1) 进栈,根还得进一次栈
    p=p–>Rchild; //遍历右子树//
    }
    else //tag=1,这时说明右子树访问完了后返回,所以这次要对根访问了
    {
    visit(p); //访问p结点//
    p=NULL;//要再退到上层,因为该棵树已经彻底访问完了
    } //之所以把p=null是不让他进入while
    }while ( p|| !Emptystack(s));
    }
                    
回复 支持 反对

使用道具 举报

0

主题

7652

帖子

1万

积分

论坛元老

Rank: 8Rank: 8

积分
16082
发表于 2017-8-6 21:16:07 | 显示全部楼层
    例题:假设二叉树采用链式存储结构进行存储,root^为根结点,p^为任一给定的结点,
    写出求从根结点到p^之间路径的非递归算法。
    [题目分析]采用后序非递归遍历二叉树,栈中保留从根结点到当前结点的路径上所有结点。
    void PrintPath(BiTree bt,p) //打印从根结点bt到结点p之间路径上的所有结点
    {
    BiTree q=bt,s[]; //s是元素为二叉树结点指针的栈,容量足够大
    int top=0; tag[];//tag数组元素值为0或1,访问左、右子树标志,tag和s同步
    if (q==p)
    { printf(q->data);
    return;
    } //根结点就是所找结点
    while(q!=null || top>0)
    {
    while(q!=null) //左子女入栈,并置标记
    if(q==p) //找到结点p,栈中元素均为结点p 的祖先
    { printf(“从根结点到p结点的路径为\n”);
    for(i=1;idata);
    printf(q->data);
    return;
    }
    else
    { s[++top]=q;
    tag[top]=0;
    q=q—>lchild;
    } //沿左分支向下
    while(top>0 && tag[top]==1))
    top--;//本题不要求输出遍历序列,这里只退栈
    if (top>0)
    { q=s[top];
    q=q->rchild;
    tag[top]=1;
    } //沿右分支向下
    }//while(q!=null || top>0)
    }//结束算法PrintPath
    按层次遍历二叉树
                    
回复 支持 反对

使用道具 举报

0

主题

7652

帖子

1万

积分

论坛元老

Rank: 8Rank: 8

积分
16082
发表于 2017-8-6 22:43:30 | 显示全部楼层
  算法描述:
    void Layerorder(BTptr T) //对二叉树T按层次遍历//
    {
    BTpfr p; qtype Q;
    if (T)
    {
    Clearqueue (Q); //置队Q空//
    Enqueue (Q,T); //将根指针进队//
    while (!Emptyqueue(Q) )
    {
    p=Dequeue(Q); //出队,队头元素Þp//
    visit (p); //访问p结点//
    if (p->Lchild) Enqneue (Q,p->Lchid); //左子指针进队//
    if (p->Rchild) Enqneue (Q,p->Rchid); //右子指针进队//
    }
    }
    }
    遍历算法的应用
    凡是对二叉树中各结点进行一次处理的问题,都可以用遍历算法来完成。
    1.利用遍历算法对二叉树中各类结点计数
    设二叉树中出度=0、1、2的结点数分别为n0、 n1 和n2 ,初值均为0。
    套用遍历算法(前序、中许、后序均可),扫描到树中某p结点时,若:
    if ((p->Lchild==NULL)&&(p->Rchild==NULL))
    n0++; //p为叶子//
    else if((p->Lchild)&&(p->Rchild))
    n2++; //p为出度=2的结点//
    else n1++; // p为出度=1的结点//
    如:只要把遍历算法在遍历时稍微改变一下。
    n0=n1=n2=0;
    void preorder( BTptr T) //对当前根结点指针为T的二叉树按前序遍历//
    {
    if (T) { // visit(T); 访问T所指结点 //
    if ((T->Lchild==NULL)&&(T->Rchild==NULL))
    n0++; //p为叶子//
    else if((T->Lchild)&&(T->Rchild))
    n2++; //p为出度=2的结点//
    else
    n1++; // p为出度=1的结点//
    preorder(T–>Lchild); //前序遍历T之左子树//
    preorder(T–>Rchild); //前序遍历T之右子树//
    }
    }
                    
回复 支持 反对

使用道具 举报

0

主题

7800

帖子

1万

积分

论坛元老

Rank: 8Rank: 8

积分
16366
发表于 2017-8-6 23:21:38 | 显示全部楼层
    2.前序遍历算法交换二叉树中各结点左、右子树(递归的交换),对每一个结点都只需要一次访问就够了,所以用遍历算法稍微改一下,把VISIT改成我们要做的事就OK了
    void preexchange (BTpfr T)
    {
    BTptr p;
    if(T)
    { p=T->Lchild;T->Lchild=T->Rchild;T->Rchild =
p;//交换当前T的左右子树//
    preexchage(T->Lchild); //处理左子树//
    preexchage(T->Rchild); //处理右子树//
    }
    }
    例题1:一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足( )【南开大学 2000 一、2】
    A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树
    前序序列是“根左右”,后序序列是“左右根”,若要这两个序列相反,只有单支树,所以本题的A和B均对,单支树的特点是只有一个叶子结点,故C是最合适的,选C。A或B都不全。
    例题2:某二叉树的前序序列和后序序列正好相反,则该二叉树一定是()的二叉树。【武汉大学2000二、4】
    A.空或只有一个结点 B.任一结点无左子树 C.高度等于其结点数 D.任一结点无右子树
    和上题类似的BD都可以但是是单选题就只能选C了
    例题3:在二叉树结点的先序序列,中序序列和后序序列中,所有叶子结点的先后顺序( )
    A.都不相同    B.完全相同 C.先序和中序相同,而与后序不同
    D.中序和后序相同,而与先序不同
                    
回复 支持 反对

使用道具 举报

0

主题

7604

帖子

1万

积分

论坛元老

Rank: 8Rank: 8

积分
15982
发表于 2017-8-7 00:38:02 | 显示全部楼层
  二叉树的线索化
    线索化分成,前序线索化和中序线索化后序线索化,他们的区别在于每个结点的前驱和后继的不同,各种不同的遍历得到不同的前驱和后继。如果考手画线索化二叉树,则三种都有可能,如果考算法描述,那么就只能考中序线索化二叉树了(其它两个的比较繁琐)。
    LchildLtagdataRtagRchild
    我们讨论建立中序线索二叉树。
    算法思路:利用中序递归遍历算法,即:
    1线索化根的左子树 2 线索化当前结点 3 线索化根的右子树。
    其中pre为外部指针(初值=NULL),在算法运行中,pre为当前搜索结点的前驱指针。
    算法描述:
    typedef struct Bnode
    { int Ltag,Rtag; //左右特征位//
    datatype data;
    struct Bnode *Lchild,*Rchild ;
    }BTnode , *BTptr;
    总控函数:中序线索化二叉树另外加了一个结点(相当于循环链表的头结点)。
    Status InorderTheaing(BinThrtree& Thrt,BiThrTree T)
    {
    if(!(Thr=(BinThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
    Thrt->LTag=Link;Thrt->RTag=Threak;
    Thrt->rchild=Thrt;//相当于空的循环链表,先将尾指针指向头结点。
    if(!T) Thrt->lchild=Thrt;//空树那么整个也是空的了,只有一个附加的头结点了
    else
    {
    Thrt->lchild=T;
    pre=Thrt;//因为pre始终是当前结点的前驱结点,那么初始值就应该是头结点
    Inthreadbt(T);将整个树线索化
    pre->RTag=Thread;//当整个树都线索化了那么,pre肯定指向最后一个结点了
    pre->rchhild=Thrt;//所以pre的后继应该是头结点
    }
    return OK;
    }
    void Inthreadbt (BTptr T) //中序线索二叉树//
    {
    if (T)
    {
    Inthreadbt(T->Lchild);//线索化左子树//
    visit(T); 改成 if(T->Lchild==NULL)
    {
    T->Ltag=Thread;
    T->Lchild=pre;
    }
    if(pre ->rchild= =NULL)
    { pre->RTag=Thread;
    pre->Rchild=T;
    }
    pre=T;
    Inthreadbt(T->Rchild); //线索化右子树//
    }
    }
                    
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|新都网 ( 京ICP备09058993号 )

GMT+8, 2024-3-29 01:09 , Processed in 0.076125 second(s), 7 queries , WinCache On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表