转载请注明出处：/wuzetiandaren/p/4252095.html
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
解题思路：
　　1.输入一个整型数组a，根据该数组创建二叉排序树，即二元查找树。
　　2.后序遍历遍历该二叉排序树，将结果保存到另一个整形数组b。
　　3.输入一个待比较的整型数组c，比较b和c里面的值是否相等。比较的方法：
　　　　a.如果b和 c的长度不相等，返回false。
　　　　b.否则，循环遍历b和 c中的元素，若有一个不相等则结束比较，返回false。
　　　　c.否则，返回true。
java实现：
1 package com.
* 判断整数序列是不是二元查找树的后序遍历结果
* @author wjh
8 public class _9IsLRDTraversal {
* @param args
private static int k=0;
public static void main(String[] args) {
int[] a = {56,45,47,67,35,76,22,89,91,27,11,21,19,87};
int[] b = new int[a.length];
//用于保存以a创建的二叉树的后序遍历结果
int[] c = {19, 22, 11, 27, 22, 35, 47, 45, 87, 91, 89, 76, 67, 56 };
Node root = null;
root = createTree( root, a);
System.out.println("打印想要比较的整数序列：");
printArr(c);
//2)印想要比较的证书序列
System.out.println("二叉树的后序遍历结果：");
postOrder(root,b);
//3)打印后序遍历结果
System.out.println();
boolean result = compare(b, c);
//4)比较是否相等
System.out.println("比较结果："+result); //5)打印比较结果
//判断输入的整数序列是不是二元查找树的后序遍历结果
private static boolean compare(int[] b, int[] c){
int blength = b.
int clength = c.
if(blength!=clength){
System.out.println("输入的数据与二叉树的长度不一致，不是该二叉树的后序遍历结果！");
return false;
for(int i=0;i&i++){
if(b[i]!=c[i]){
System.out.println("输入的数据与该二叉树后序遍历结果不一致，不是该二叉树的后序遍历结果！");
return false;
System.out.println("输入的数据与该二叉树后序遍历结果一致！");
return true;
//创建二叉排序树
public static Node
createTree(Node root, int[] r){
int n = r.
System.out.println("建树过程(a&--b表示在a的左边插入b;a--&b表示在a的右边插入b)：");
for(int i=0;i&n;i++){
Node child = new Node(r[i],null,null);
root = insert(root, child);
//二叉排序树的插入算法
public static Node insert(Node root, Node child){
//寻找插入位置
if(root==null){
System.out.println(root.data);
if(root.data&child.data){
System.out.print(root.data+"&--");
root.left = insert(root.left, child);
System.out.print(root.data+"--&");
root.right = insert(root.right,child);
//二叉树的后序遍历
public static void postOrder(Node root,int[] b){
if(root==null){
postOrder(root.left,b);
postOrder(root.right,b);
System.out.print(root.data+" ");
b[k++] = root.
//打印数组
private static void printArr(int[] a){
int n = a.
for(int i=0;i&n;i++){
System.out.print(a[i]+" ");
System.out.println();
//节点的数据结构
private static class Node {
public int
//指向左子树
//指向右子树
public Node() {
// TODO Auto-generated constructor stub
public Node(int data, Node left, Node right) {
this.data =
this.left =
this.right =
运行结果：
1. 因长度不相等：
建树过程(a&--b表示在a的左边插入b;a--&b表示在a的右边插入b)：5656&--4556&--45--&4756--&6756&--45&--3556--&67--&7656&--45&--35&--2256--&67--&76--&8956--&67--&76--&89--&9156&--45&--35&--22--&2756&--45&--35&--22&--1156&--45&--35&--22&--11--&2156&--45&--35&--22&--11--&21&--1956--&67--&76--&89&--87打印想要比较的整数序列：19 21 11 27 22 35 47 二叉树的后序遍历结果：19 21 11 27 22 35 47 45 87 91 89 76 67 56 输入的数据与二叉树的长度不一致，不是该二叉树的后序遍历结果！比较结果：false
2.因内容不相等：
建树过程(a&--b表示在a的左边插入b;a--&b表示在a的右边插入b)：5656&--4556&--45--&4756--&6756&--45&--3556--&67--&7656&--45&--35&--2256--&67--&76--&8956--&67--&76--&89--&9156&--45&--35&--22--&2756&--45&--35&--22&--1156&--45&--35&--22&--11--&2156&--45&--35&--22&--11--&21&--1956--&67--&76--&89&--87打印想要比较的整数序列：19 22 11 27 22 35 47 45 87 91 89 76 67 56 二叉树的后序遍历结果：19 21 11 27 22 35 47 45 87 91 89 76 67 56 输入的数据与该二叉树后序遍历结果不一致，不是该二叉树的后序遍历结果！比较结果：false
3.是二元查找树的后序遍历结果：
建树过程(a&--b表示在a的左边插入b;a--&b表示在a的右边插入b)：5656&--4556&--45--&4756--&6756&--45&--3556--&67--&7656&--45&--35&--2256--&67--&76--&8956--&67--&76--&89--&9156&--45&--35&--22--&2756&--45&--35&--22&--1156&--45&--35&--22&--11--&2156&--45&--35&--22&--11--&21&--1956--&67--&76--&89&--87打印想要比较的整数序列：19 21 11 27 22 35 47 45 87 91 89 76 67 56 二叉树的后序遍历结果：19 21 11 27 22 35 47 45 87 91 89 76 67 56 输入的数据与该二叉树后序遍历结果一致！比较结果：true
阅读(...) 评论()第四题&二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
&&&5&&&7&&&9&&11
因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
----------------------------------------------------------------------------------------------------------------------------
三个条件可以方便我们的分析：
后序遍历的访问顺序：LRN。先访Left
subtree, 然后访问Right subtree,
最后访问Node。因此作为最后被访问的Node，一定要出现在序列的最后。之前的元素为左右子树。
区分左右子树：根据排序二叉树的定义，左子树的元素一定小于根节点，右子树的元素全部大于根节点。在LRN的遍历顺序下，应当先出现全部小于根节点的左子树子序列，后出现全部大于根节点的右子树子序列。我们找由小于变成大于的地方，便是左右子树分开的地方。
左右子树都满足上述两点，可以使用递归处理。
-------------------------------------------------------
由一下代码实现：
verifySequenceOfBST(int *sequence, int len)
& & if(sequence==null ||
& & & return
& &//first get the root node
root=sequence[len-1];
& &//divide the sequence into
left subtree and right subtree
& & for(int i=0;
sequence[i]& ++i) ; &// how
about the sequence[i]==root?
& &//now sequence[i] is the first
num of right subtree, we have to check out if all the num from i to
len-1 is&&& &
than the root.
& & for(j=i;
&j&len&&&&sequence[j]&root;
& & if(j&len)
& &// we check the left/right
sublist both &if they are BST
&bool&left
0)&&&&&&&left
= verifySquenceOfBST(squence, i);&
&&&bool&right
=&true;&&&&&&
& length - 1)&&&&&&&&&&&&
verifySquenceOfBST(squence + i, length - i - 1);
& & &return
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。一波C语言二元查找树算法题目解答实例汇总
作者：wuzhekai1985
字体：[ ] 类型：转载 时间：
这篇文章主要介绍了一波C语言二元查找树算法题目解答实例汇总,包括按层次遍历和转换为镜像等基本算法题目,需要的朋友可以参考下
按层次遍历二元树
问题描述：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。&
例如输入：
8 6 10 5 7 9 11
&&&&&&&&& 定义二元树（其实是二元搜索树，但并不遍历算法）的结点为：
struct BSTreeNode
BSTreeNode *
BSTreeNode *
&&&&& 思路：利用队列的先进先出，很容易实现。每次取出队列的首元素，然后将其左右子女放入队列中。直至队列为空即可。按这种方式进出队列，正好是按层遍历二元树。
&&&&& 参考代码：
//函数功能 ： 按层次遍历二元树
//函数参数 ： pRoot指向根结点
//返回值 ： 无
void LevelReverse(BSTreeNode *pRoot)
if(pRoot == NULL)
queue&BSTreeNode *& nodeQ
nodeQueue.push(pRoot);
while(nodeQueue.size())
BSTreeNode * pNode = nodeQueue.front(); //取队首元素
nodeQueue.pop(); //必须出队列
if(pNode-&left) //左子女
nodeQueue.push(pNode-&left);
if(pNode-&right) //右子女
nodeQueue.push(pNode-&right);
cout&&pNode-&value&&' ';
&&&&&& 扩展一：上文给出的代码，所有结点都输出在同一行。如果希望仅仅同层结点输出在同一行，该如何修改代码呢？
&&&&&& 思路：如果我们能知道每层的最后一个结点，那么就方便多了，输出每层最后一个结点的同时，输出一个换行符。因此，关键在于如何标记每层的结束。可以考虑在每层的最后一个点之后，插入一个空结点。比如队列中先放入根结点，由于第0层只有一个结点，因此放入一个空结点。然后依次取出队列中的结点，将其子女放入队列中，如果遇到空结点，表明当前层的结点已遍历完了，而队列中放的恰恰是下一层的所有结点。如果当前队列为空，表明下一层无结点，也就说是所有结点已遍历好了。如果不为空，那么插入一个空结点，用于标记下一层的结束。
&&&&& 参考代码：
void LevelReverse(BSTreeNode *pRoot)
if(pRoot == NULL)
queue&BSTreeNode *& nodeQ
nodeQueue.push(pRoot);
nodeQueue.push(NULL); //放入空结点，作为层的结束符
while(nodeQueue.size())
BSTreeNode * pNode = nodeQueue.front(); //取队首元素
nodeQueue.pop(); //必须出队列
if(pNode-&left) //左子女
nodeQueue.push(pNode-&left);
if(pNode-&right) //右子女
nodeQueue.push(pNode-&right);
cout&&pNode-&value&&' ';
else if(nodeQueue.size()) //如果结点为空并且队列也为空，那么所有结点都已访问
nodeQueue.push(NULL);
&&&&&& 扩展二：之前讨论的都是从上往下、从左往右遍历二叉树，那么如果希望自下往上、从左右往右遍历二叉树，该如何修改代码呢？
&&&&&& 思路：比较简单的方法，首先遍历二叉树，将所有结点保存在一个数组中，遍历的同时记录每一层在数组中的起止位置。然后根据起止位置，就可以自下往上的打印二叉树的结点。
//每层的起止位置
struct Pos
Pos(int b, int e): begin(b),end(e) {}
void LevelReverse(BSTreeNode *pRoot)
if(pRoot == NULL)
vector&BSTreeNode*& //用以存放所有结点
vector&Pos&
//用以记录每层的起止位置
vec.push_back(pRoot);
int level = 0; //树的层数
int cur = 0;
int last = 1;
while(cur & vec.size())
last = vec.size();
pos.push_back(Pos(cur, last)); //记录当前层的起止位置
while(cur & last) //遍历当前层的结点，将子女放入数组中
if(vec[cur]-&left) //先是左然后是右。如果希望自由向左，交换一下顺序即可
vec.push_back(vec[cur]-&left);
if(vec[cur]-&right)
vec.push_back(vec[cur]-&right);
level++; //层数加1
for(int i = level - 1; i &= 0; i--) //自下往上遍历
for(int j = pos[i]. j & pos[i]. j++)
cout&&vec[j]-&value&&' ';
输入一颗二元查找树，将该树转换为它的镜像
& 问题描述：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。&
&&&&&&& 例如输入：
&&&&& 定义二元查找树的结点为：
struct BSTreeNode
BSTreeNode *
BSTreeNode *
&&&&& 思路：题目要求用两种方法，递归和循环，其实质是一样的。
&&&&& 解法一：用递归。假设当前结点为pNode，只需交换该结点的左右子女，然后分别递归求解左子树和右子树即可。代码极为简单。
&&&&& 解法二：用循环，需要一个辅助栈完成，每次取栈顶元素交换左右子女，然后将左右子女分别压入辅助栈，当栈中元素为空时，结束循环。其实不论是递归也好，循环也好，都是利用栈的特性完成。
&&&&& 参考代码：
//函数功能 ： 输入一颗二元查找树，将该树转换为它的镜像
//函数参数 ： pRoot为根结点
//返回值 ： 根结点
BSTreeNode * Mirror_Solution1(BSTreeNode * pRoot)
if(pRoot != NULL)
BSTreeNode * pRight = pRoot-&
BSTreeNode * pLeft = pRoot-&
pRoot-&left = Mirror_Solution1(pRight); //转化右子树
pRoot-&right = Mirror_Solution1(pLeft); //转化左子树
BSTreeNode * Mirror_Solution2(BSTreeNode * pRoot)
if(pRoot != NULL)
stack&BSTreeNode *& //辅助栈
stk.push(pRoot);
//压入根结点
while(stk.size())
BSTreeNode *pNode = stk.top();
BSTreeNode *pLeft = pNode-&
BSTreeNode* pRight = pNode-&
stk.pop();
if(pLeft != NULL)
stk.push(pLeft);
if(pRight != NULL)
stk.push(pRight);
pNode-&left = pR //交换左右子女
pNode-&right = pL
判断整数序列是不是二元查找树的后序遍历结果
问题描述：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
&&&&&&&& 思路：分析后序遍历的特点，序列的最后一个数应该是根结点，剩余的节点分为两个连续的子序列，前一子序列的值小于最后一个数，后一子序列的值大于最后一个数。然后递归求解这两个子序列。
&&&&&&&& 如果是判断是前序遍历也很简单，只不过根节点变为了第一个数，剩余的节点也是分为两个连续的子序列。如果判断是中序遍历，更方便，只需扫描一遍，检查序列是不是排好序的，如果没有排好序，就不是中序遍历的结果。
把二元查找树转变成排序的双向链表
&&& 问题描述：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
&转换成双向链表
4=6=8=10=12=14=16
&& 思路：利用递归的思想求解，分别调整某结点的左右子树，调整完后，将该结点的左指针指向左子树的最大节点，右指针指向右子树的最小节点。
&& 代码如下：
BSTreeNode * Convert(BSTreeNode *node)
if(node == NULL)
return NULL;
BSTreeNode *leftMax,*rightM
leftMax = node-&
rightMin = node-&
//找到左子树的最大结点
while(leftMax != NULL && leftMax-&right != NULL)
leftMax = leftMax-&
//找到右子树的最小结点
while(rightMin != NULL && rightMin-&left != NULL)
rightMin = rightMin-&
//递归求解
Convert(node-&right);
Convert(node-&left);
//将左右子树同根结点连起来，只不过是以兄弟的关系
if(leftMax != NULL)
leftMax-&right =
if(rightMin != NULL)
rightMin-&left =
node-&left = leftM
node-&right = rightM
&& 测试当中，需要建立二叉搜索树，下面给出建立及遍历二叉树的代码。
struct BSTreeNode
BSTreeNode *
BSTreeNode *
BSTreeNode * Insert(BSTreeNode *p, int x)
if(p == NULL)
p = new BSTreeN
p-&value =
p-&left = NULL;
p-&right = NULL;
if(p-&value & x)
p-&left = Insert(p-&left, x);
if(p-&value & x)
p-&right = Insert(p-&right, x);
void Traverse(BSTreeNode *p) //中序遍历
if(p == NULL)
Traverse(p-&left);
cout&&p-&value&&' ';
Traverse(p-&right);
在二元树中找出和为某一值的所有路径（树）
&& 问题描述：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数22和如下二元树
则打印出两条路径：10, 12和10, 5, 7。
二元树节点的数据结构定义为：
struct BinaryTreeNode
BinaryTreeNode *pL
BinaryTreeNode *pR
&&& 思路：递归的思想。很多树的题目都是用递归解决的，例如把二元查找树转变成排序的双向链表（树）。递归的终止条件为当前为空结点或当前结点的值大于剩余和。如果当前结点的值等于剩余和，并且是叶结点，那么打印路径。否则，将剩余和减去当前结点的值，递归求解。至于路径的记录，可以利用栈的思想来实现。
&&&&&& 代码：
void FindPath(BinaryTreeNode *pNode,int sum,vector&int& &path)
//结点为空或值大于当前和
if(pNode == NULL || pNode-&data & sum)
path.push_back(pNode-&data);
//判断是不是叶结点
bool isLeaf = (pNode-&pLeft == NULL && pNode-&pRight == NULL)? true:
//找到一条路径，打印
if(pNode-&data == sum && isLeaf)
vector&int&::iterator iter = path.begin();
for(; iter != path.end(); iter++)
cout&&*iter&&' ';
//求剩余和
sum = sum - pNode-&
//递归求解
FindPath(pNode-&pLeft, sum, path);
FindPath(pNode-&pRight, sum, path);
path.pop_back();
判断二叉树是不是平衡的
问题描述：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。例如下图中的二叉树就是一棵平衡二叉树：
思路：对于树的题目，第一反应就是用递归。对于以某个结点为根的树，只需计算出它的左右子树的深度，如果深度相差小于等于1，则递归判断它的左右子树是不是平衡树；否则肯定不是平衡二叉树。这个问题的关键是要计算树的深度，如果是自顶向下，会有很多重复的计算。计算以1为根的树的深度，会牵涉到以2为根、以3为根的子树。计算以2为根的树的深度，会牵涉到以4为根、以5为根的子树。由于要遍历每个结点，判断以该结点为根的树是不是平衡二叉树。所以计算以1为根的树的深度，与计算以2为根的树的深度，会重复计算以4为根、以5为根的子树的深度。
消除重复办法，当时是能记录下之前计算过的子树的深度，下次使用就不用重新计算。这就需要自底向上的计算深度。庆幸的是递归解决树的问题，就是自底向上的过程。因为我们在递归求解中，先要得出子树的解，子树的解最终会转换为叶结点的解。可以利用后序遍历的方法，遍历每个结点时，先判断它的左右子树是不是平衡二叉树，同时记录下左右子树的深度，然后判断该结点为根的树是不是平衡二叉树，至于该树的深度计算很方便，取左右子树中较大的深度+1就可以了。这里左右子树的深度在递归求解中已经计算出来，不需要重复计算了。
参考代码：
struct BinaryTreeNode
BinaryTreeNode *pL
BinaryTreeNode *pR
//函数功能 ： 判断二叉树是不是平衡的
//函数参数 ： pRoot为根结点，pDepth为根结点的深度。
//返回值 ：
是否平衡的
bool IsBalanced(BinaryTreeNode *pRoot, int *pDepth)
if(pRoot == NULL)
*pDepth = 0;
int leftDepth, rightD //左右子树的深度
if(IsBalanced(pRoot-&pLeft, &leftDepth)&&
IsBalanced(pRoot-&pRight, &rightDepth))
int diff = leftDepth - rightD
if(diff == 0 || diff == 1 || diff == -1) //相差为0或1或-1
*pDepth = 1 + (leftDepth & rightDepth ? leftDepth: rightDepth);
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具java 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 - 史迪阳的博客 - CSDN博客
java 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
对于一个二叉树的后序遍历序列来说，最后一个数一定是根节点，然后前面的数中，从最开始到第一个大于根节点的数都是左子树中的数，而后面到倒数第二个数应该都是大于根节点的，是右子树，如果后面的数中有小于根节点的，那么说明这个序列不是二叉搜索树的后序遍历序列
import java.util.A
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null||sequence.length&=0){
int len=sequence.
int root=sequence[len-1];
for(;i&len-1;i++){
if(root&=sequence[i])
for(;j&len-1;j++){
if(root&sequence[j]){
boolean leftFlag=
if (i&0) {
leftFlag=VerifySquenceOfBST(Arrays.copyOfRange(sequence,0,i));
boolean rightFlag=
if (i&len-1) {
rightFlag=VerifySquenceOfBST(Arrays.copyOfRange(sequence,i,sequence.length-1));
return leftFlag&&rightF
我的热门文章剑指offer_输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果 - lingongheng - CSDN博客
剑指offer_输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
此前在苏宁笔试中遇到到这题，当时认为二叉搜索树均为满二叉树，故在递归过程中，对数组的划分是以满二叉树的特性进行划分。大错特错！
本题是利用递归思想，判断根节点的左子树元素是否小于根节点，右子树元素是否大于根节点。重点在于对左右子树的划分（因为传入的是个数组）
1.从第0位开始，找到第一位比根节点大的元素，记录此位置i。在此位置之前都属于左子树（此时已经断定左子树都小于根节点）
2.检查右子树是否都大于跟节点（从第i位开始，到根节点前）
3.判断左右子树是否都属于二叉搜索树。
代码如下：
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null||sequence.length==0){
return false;
boolean res =getRes(sequence,0,sequence.length-1);
public boolean getRes(int[] s,int start,int end){
if(end-start&=1){
return true;
for( i=i&i++){
if(s[i]&s[end]){
for(j=i;j&j++){
if(s[j]&s[end]){
return false;
boolean left=true;
boolean right=true;
left = getRes(s,start,i-1);
if(i&s.length-1){
right=getRes(s,i,end-1);
return left&&
我的热门文章}