二叉树的遍历
标签: 数据结构
学习人数: 6601


全屏播放
赞赏支持

二叉树遍历

二叉树的遍历一个重点考查的知识点。

二叉树的遍历是指从二叉树的根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次,且仅被访问一次。

二叉树的访问次序可以分为四种:

前序遍历
中序遍历
后序遍历
层序遍历

 

前序遍历

前序遍历通俗的说就是从二叉树的根结点出发,当第一次到达结点时就输出结点数据,按照先向左在向右的方向访问。

上图所示二叉树访问如下:

从根结点出发,则第一次到达结点A,故输出A;
继续向左访问,第一次访问结点B,故输出B;
按照同样规则,输出D,输出H;
当到达叶子结点H,返回到D,此时已经是第二次到达D,故不在输出D,进而向D右子树访问,D右子树不为空,则访问至I,第一次到达I,则输出I;
I为叶子结点,则返回到D,D左右子树已经访问完毕,则返回到B,进而到B右子树,第一次到达E,故输出E;
向E左子树,故输出J;
按照同样的访问规则,继续输出C、F、G;

则上图所示二叉树的前序遍历输出为:

ABDHI...

登录查看完整内容


课后作业

课后练习

【2019年真题】若将一棵树T转化为对应的二又树BT,则下列对BT的遍历中,其遍历序列与T的后根遍历序列相同的是
A. 先序遍历      B. 中序遍历      C. 后序遍历      D. 按层遍历

参考答案:B

 

【2017年真题】要使一颗非空二叉树的先序序列与中序序列相同,其所有非叶节点须满足的条件是()
A.只有左子树        B.只有右子树        C.结点的度均为1        D.结点的度均为2

参考答案:B

 

【2017年真题】已知一颗二叉树的树形如下图所示,其后序序列为e,a,c,b,d,g,f,树中与结点a同层的结点是()

A.c        B.d        C.f        D.g

参考答案:B

 

【2015年真题】先序序列为 a,b,c,d 的不同二叉树的个数是()。
A.13    B.14    C.15    D.16

参考答案:B

 

【2013年真题】已知三叉树 T 中 6 个叶结点的权分别是 2,3,4,5,6,7,T 的带权(外部)路径长度最小是
 A. 27         B. 46         C. 54         D. 56

参考答案:B
答案解析:利用三叉树的 6 个叶子结点的权构建最小带权生成树,最小的带权路径长度为(2 + 3) * 3 + (4 + 5) * 2 + (6 + 7) * 1 = 46。

 

【2012年真题】若一棵二叉树的前序遍历序列为 a, e, b, d, c,后序遍历序列为 b, c, d, e, a,则根结点的孩子结点()
A. 只有 e 
B. 有 e、b 
C. 有 e、c 
D. 无法确定 

参考答案:A
答案解析:考查树的遍历、及由遍历序列确定二叉树的树形。 
前序序列和后序序列不能唯一确定一棵二叉树,但可以确定二叉树中结点的祖先关系:当两个结点 的前序序列为 XY 与后序序列为 YX 时,则 X 为 Y 的祖先。考虑前序序列 a,e,b,d,c、后序序列 b,c,d,e,a, 可知 a 为根结点,e 为 a 的孩子结点;此外,a 的孩子结点的前序序列 e,b,d,c、后序序列 b,c,d,e,可知 e 是 bcd 的祖先,故根结点的孩子结点只有 e。本题答案为 A。

 

【2011年真题】若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1,则该二叉树的 中序遍历序列不会是()
A.1,2,3,4 
B.2,3,4,1 C.3,2,4,1
D.4,3,2,1 

解答:C。由前序和后序遍历序列可知3为根结点,故(1,2)为左子树,(4)为右子树, 
C不可能。或画图即可得出结果。 

 

【2009年真题】给定二叉树如右图所示。设 N 代表二叉树的根,L 代表根结点的左子树,R 代表根结点的右子树。若遍历后的结点序列是 3,1,7,5,6,2,4,则其遍历方式是()。 

A.LRN         B.NRL         C.RLN         D.RNL

参考答案:D
答案解析:考查平衡二叉树的定义。 
根据平衡二叉树的定义有,任意结点的左右子树高度差的绝对值不超过 1。而其余三个答案均可以找到不符合的结点。


【2017年真题】请设计一个算法,将给定的表示式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出。例如,当下列两颗表达式树作为算法的输入时:

输出的等价中缀表达式分别为(a+b)*(c*(-d))和(a*b)+(-(c-d))。
二叉树结点定义如下:

typedef struct node {    
    char data[10];  //存储操作数或操作符    
    struct node *left, *right;    
}BTree;    

    要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。

参考答案:
(1)算法的基本设计思想
表达式的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。
表达式树中分支结点所对应的子表达式的计算次序,由该分支点所处的位置决定。为得到正确的中缀表达式,需要在生成遍历序列的同时,在适当位置增加必要的括号。显然,表达式的最外层(对应根节点)及操作数(对应叶节点)不需要添加括号。
(2)算法实现

void BtreeToE(BTree *root) {  
    BtreeToExp(root, 1);    //根的高度为1  
}  
void BtreeToExp(BTree *root, int deep) {  
    if (root == NULL) return;  
    else if (root->left == NULL && root->right == NULL)  
        //若为叶结点  
        printf("%s", root->data);  
    else {  
        if (deep > 1) printf("("); //若有子表达式则加1层括号  
        BtreeToExp(root->left, deep + 1);  
        printf("%s", root->data);   //输出操作符  
        BtreeToExp(root->right, deep + 1);  
        if (deep > 1) printf(")") //若有子表达式则加1层括号  
    }  
}  

 

【2014年真题】二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 T,采用二叉链表存储,结点结构为: 

其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 T 的根结点的指针,请 
设计求 T 的 WPL 的算法,要求: 
1)给出算法的基本设计思想; 
2)使用 C 或 C++语言,给出二叉树结点的数据类型定义; 
3)根据设计思想,采用 C 或 C++语言描述算法,关键之处给出注释。 

参考答案:
考查二叉树的带权路径长度,二叉树的带权路径长度为每个叶子结点的深度与权值之积 
的总和,可以使用先序遍历或层次遍历解决问题。 
1)算法的基本设计思想: 
①基于先序递归遍历的算法思想是用一个 static 变量记录 wpl,把每个结点的深度作为 
递归函数的一个参数传递,算法步骤如下: 
若该结点是叶子结点,那么变量 wpl 加上该结点的深度与权值之积; 
若该结点非叶子结点,那么若左子树不为空,对左子树调用递归算法,若右子树不为空, 
对右子树调用递归算法,深度参数均为本结点的深度参数加一; 
最后返回计算出的 wpl 即可。 
②基于层次遍历的算法思想是使用队列进行层次遍历,并记录当前的层数, 
当遍历到叶子结点时,累计 wpl; 
当遍历到非叶子结点时对该结点的把该结点的子树加入队列; 
当某结点为该层的最后一个结点时,层数自增 1; 
队列空时遍历结束,返回 wpl 
2)二叉树结点的数据类型定义如下: 

typedef struct BiTNode{  
    int weight;  
    struct BiTNode *lchild, *rchild;  
}BiTNode, *BiTree;  

算法代码如下: 
①基于先序遍历的算法: 

int WPL(BiTree root) {  
    return wpl_PreOrder(root, 0);  
}  
int wpl_PreOrder(BiTree root, int deep) {  
    static int wpl = 0; //定义一个 static 变量存储 wpl  
    if(root->lchild == NULL && root->lchild == NULL) //若为叶子结点,累积 wpl  
        wpl += deep*root->weight;  
    if(root->lchild != NULL) //若左子树不空,对左子树递归遍历  
        wpl_PreOrder(root->lchild, deep+1);  
    if(root->rchild != NULL) //若右子树不空,对右子树递归遍历  
        wpl_PreOrder(root->rchild, deep+1);  
    return wpl;  
}  

②基于层次遍历的算法: 

#define MaxSize 100 //设置队列的最大容量  
int wpl_LevelOrder(BiTree root) {  
    BiTree q[MaxSize]; //声明队列,end1 为头指针,end2 为尾指针  
    int end1, end2; //队列最多容纳 MaxSize-1 个元素  
    end1 = end2 = 0; //头指针指向队头元素,尾指针指向队尾的后一个元素  
    int wpl = 0, deep = 0; //初始化 wpl 和深度  
    BiTree lastNode; //lastNode 用来记录当前层的最后一个结点  
    BiTree newlastNode; //newlastNode 用来记录下一层的最后一个结点  
    lastNode = root; //lastNode 初始化为根节点  
    newlastNode = NULL; //newlastNode 初始化为空  
    q[end2++] = root; //根节点入队  
    while(end1 != end2){ //层次遍历,若队列不空则循环  
        BiTree t = q[end1++]; //拿出队列中的头一个元素  
        if(t->lchild == NULL & t->lchild == NULL){  
            wpl += deep*t->weight;  
        } //若为叶子结点,统计 wpl  
        if(t->lchild != NULL){ //若非叶子结点把左结点入队  
            q[end2++] = t->lchild;   
            newlastNode = t->lchild;  
        } //并设下一层的最后一个结点为该结点的左结点  
        if(t->rchild != NULL){//处理叶节点  
            q[end2++] = t->rchild;  
            newlastNode = t->rchild;  
        }  
        if(t == lastNode){ //若该结点为本层最后一个结点,更新 lastNode  
            lastNode = newlastNode;  
            deep += 1; //层数加 1   
        }   
    }  
    return wpl; //返回 wpl  
}  

 


登录后发布评论

暂无评论,来抢沙发