二叉树的遍历及相关题目.pdf

⼆⼆叉叉树树的的遍遍历历及及相相关关题题⽬⽬

⼆⼆叉叉树树的的遍遍历历及及相相关关题题⽬⽬

1.1⼆⼆叉叉树树遍遍历历的的概概念念

⼆叉树结构体的定义：

typedefstructnode

{

ElemTypedata;

structnode*lchild;

structnode*rchild;

}

⼆叉树的遍历是指按照⼀定的次序访问⼆叉树中的所的节点，并且每个节点仅访问⼀次的过程。

若规定先遍历左⼦树，后遍历右⼦树，则对于⾮空⼆叉树，可得到如下3种递归的遍历⽅法：

（1）先序遍历

访问根节点，先序遍历左⼦树，先序遍历右⼦树。（根，左，右）

（2）中序遍历

中序遍历左⼦树，访问根节点，中序遍历右⼦树。（左，根，右）

（3）后序遍历

后序遍历左⼦树，后序遍历右⼦树，访问根节点。（左，右，根）

除此之外也层次遍历。先访问根节点，在从左到右访问第⼆层的所节点，从左到右访问第三层的所节点

1.2⼆⼆叉叉树树遍遍历历递递归归算算法法

先序遍历递归算法：

voidPreOrderBTNode*b)

{

ifn!=NULL)

{

coutb-data;

PreOrderb-lchild);

PreOrderb-rchild);

}

}

中序遍历递归算法

voidInOrderBTNode*b)

{

ifn!=NULL)

{

InOrderb-lchild);

coutb-data;

InOrderb-rchild);

}

}

后序遍历递归算法：

voidPostOrderBTNode*b)

{

ifb!=NULL)

{

PostOrderb-lchild);

PostOrderb-rchild);

coutb-data;

}

}

题⽬1：输出⼀个给定⼆叉树的所的叶⼦节点：

voidDispLeafBTNode*b)

{

ifb!=NULL)

{

ifb-lchild==NULLb-rchild==NULL)

coutb-data;

DispLeafb-lchild);

DispLeafb-rchild);

}

}

以上算法采⽤先序遍历输出了所的叶⼦节点，所以叶⼦节点是从左到右输出的。从右到左输出所的叶⼦节点就需要才⽤后序遍历的思

想。

voidDispLeaf1BTNode*b)

{

ifb!=NULL)

{

ifb-lchild==NULLb-rchild==NULL)

coutb-data;

DispLeaf1b-rchild);

DispLeaf1b-lchild);

}

}

题⽬2：求⼆叉树中节点值为x的节点的层数（假设⼆叉树中的节点的值都不同）。

题解：采⽤递归算法，设计函数Levelb,x,h)，其返回值为在⼆叉树b中节点值x的节点所在的层次，返回0时表⽰未找到。h表⽰b所指节点的

层次，从根节点开始查找，根节点的层次为1，所以h的初值为1。

intLevelBTNode*b,ElemTypex,inth)//h的初始值为1

{

ifb==NULL)

{

return0;

}

elseifb-data==x)

{

returnh;

}else

{

intlevel=Levelb-lchild,x,h+1);

iflevel!=0)

returnlevel;

else

returnLevelb-rchild,x,h+1);

}

}

题⽬3：判断两颗⼆叉树是否相似。所谓⼆叉树b1和b2相似是指b1和b2都是空的⼆叉树；或者b1和b2的根节点相似，且左⼦树和右⼦树分

别相似。不必⽐较数值，结构⼀样就是相似。

//相似返回true，不相似返回false

boolLikeBTNode*b1,BTNode*b2)

{

ifb1==NULLb