二叉树是计算机结构中一个重要的要点，学会二叉树也是比较重要的，这里小编整理了一些二叉树的遍历例题，快来瞧瞧吧。
一、输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {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面试题内容请关注本网站了解详情吧。
推荐阅读：