二叉树遍历例题及答案详解,java入门教程

TheDisguiser 2020-05-28 21:00:18 java常见问答 3970

二叉树是计算机结构中一个重要的要点,学会二叉树也是比较重要的,这里小编整理了一些二叉树的遍历例题,快来瞧瞧吧。

一、输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并输出它的后序遍历序列。

答: 这是递归的简单应用,前序遍历的根在最前面,在中序遍历里找到那个数,然后前序序列和中序序列的分解成为两部分,对这两部分在递归即可。可以直接生成后续遍历的序列,而不用重构出这棵树。

实例:

#include <iostream>
using namespace std;
int pre[1024], post[1024], in [1024];
bool can(int * pre, int * in , int * post, int fpre, int fin, int fpost, int len)
{
    int i;
    if (len <= 0)
    {
        return true;
    }
    for (i = 0; i < len; ++i)
    {
        if (pre[fpre] == in [fin + i])
        {
            break;
        }
    }
    if (i >= len)
    {
        return false;
    }
    if (!can(pre, in , post, fpre + 1, fin, fpost, i))
    {
        return false;
    }
    if (!can(pre, in , post, fpre + i + 1, fin + i + 1, fpost + i, len - i - 1))
    {
        return false;
    }
    post[fpost + len - 1] = pre[fpre];
    return true;
}
int main()
{
    int i, n;
    while (scanf("%d", & n) != EOF)
    {
        for (i = 0; i < n; ++i)
        {
            scanf("%d", pre + i);
        }
        for (i = 0; i < n; ++i)
        {
            scanf("%d", in +i);
        }
        if (can(pre, in , post, 0, 0, 0, n))
        {
            for (i = 0; i < n; ++i)
            {
                printf("%d ", post[i]);
            }
            puts("");
        }
        else
        {
            puts("No");
        }
    }
    return 0;
}

二、给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注:树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

答:

#- * -coding: utf - 8 - * -#class TreeLinkNode: #def __init__(self, x): #self.val = x# self.left = None# self.right = None# self.next = None
class Solution:
    def GetNext(self, pNode): #write code here
if not pNode:
    return None
if pNode.right:
    pNode = pNode.right# 别忘了先到右结点
while pNode.left:
    pNode = pNode.left
return pNode
while pNode.next:
    pRoot = pNode.next
if pRoot.left == pNode:
    return pRoot
pNode = pNode.next#

三、请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

答:

#- * -coding: utf - 8 - * -#class TreeNode: #def __init__(self, x): #self.val = x# self.left = None# self.right = None
class Solution:
    def isSymmetrical(self, pRoot): #write code here
if not pRoot:
    return True
return self.compare(pRoot.left, pRoot.right)
def compare(self, left, right):
    if not left and not right:
    return True
if not left or not right:
    return False
if left.val == right.val:
    if self.compare(left.left, right.right) and self.compare(left.left, right.right):
    return True# 上一行很重要, 要在代码中体现对称
return False

四、请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

答:

#- * -coding: utf - 8 - * -#class TreeNode: #def __init__(self, x): #self.val = x# self.left = None# self.right = None
class Solution:
    def Print(self, pRoot): #write code here# 选用栈解决
if not pRoot:
    return []
result = []#
stack = []# 利用栈实现
stack.append(pRoot)
while stack:
    res = []# 储存下一行的值
nextstack = []# 储存下一行的结点
for i in stack: #遍历完这一行, 包括添加结点与值
res.append(i.val)
if i.left:
    nextstack.append(i.left)
if i.right:
    nextstack.append(i.right)
stack = nextstack
result.append(res)
for i in range(len(result)): 偶数行要反转
if i % 2 == 1:
    result[i].reverse()
return result ''
class Solution:
    def Print(self, pRoot):
    if not pRoot:
    return []
nodeStack = [pRoot]
result = []
while nodeStack:
    res = []
nextStack = []
for i in nodeStack:
    res.append(i.val)
if i.left:
    nextStack.append(i.left)
if i.right:
    nextStack.append(i.right)
nodeStack = nextStack
result.append(res)
returnResult = []
for i, v in enumerate(result):
    if i % 2 == 0:
    returnResult.append(v)
else :
    returnResult.append(v[::-1])
return returnResult

五、从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

答:

#- * -coding: utf - 8 - * -#class TreeNode: #def __init__(self, x): #self.val = x# self.left = None# self.right = None
class Solution: #返回二维列表[[1, 2], [4, 5]]
def Print(self, pRoot): #write code here
if not pRoot:
    return []
result = []
queue = [pRoot]
while queue:
    res = []
nextqueue = []
for i in queue:
    res.append(i.val)# 是小括号!!
if i.left:
    nextqueue.append(i.left)
if i.right:
    nextqueue.append(i.right)
result.append(res)
queue = nextqueue
return result

以上就是关于二叉树遍历试题的所有内容了,更多相关java面试题内容请关注本网站了解详情吧。

推荐阅读:

b树是二叉树吗?b树是什么树?

重建二叉树(思路和实现)

将二叉树变换为源二叉树的镜像如何实现?思路和实现