一波C语言二元查找树算法题目解答实例汇总

按层次遍历二元树
问题描述：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。 
例如输入：

 8
 / /
 6 10
/ / / /
5 7 9 11

输出

8 6 10 5 7 9 11

定义二元树（其实是二元搜索树，但并不遍历算法）的结点为：

struct BSTreeNode
{
 int value;
 BSTreeNode *left;
 BSTreeNode *right;
};

思路：利用队列的先进先出，很容易实现。每次取出队列的首元素，然后将其左右子女放入队列中。直至队列为空即可。按这种方式进出队列，正好是按层遍历二元树。
      参考代码：

//函数功能 ： 按层次遍历二元树
//函数参数 ： pRoot指向根结点
//返回值 ： 无
void LevelReverse(BSTreeNode *pRoot)
{
 if(pRoot == NULL)
  return; 

 queue<BSTreeNode *> nodeQueue;
 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)
  return;
 queue<BSTreeNode *> nodeQueue;
 nodeQueue.push(pRoot);
 nodeQueue.push(NULL); //放入空结点，作为层的结束符
 while(nodeQueue.size())
 {
  BSTreeNode * pNode = nodeQueue.front(); //取队首元素
  nodeQueue.pop(); //必须出队列
  if(pNode)
  {
   if(pNode->left) //左子女
    nodeQueue.push(pNode->left);
   if(pNode->right) //右子女
    nodeQueue.push(pNode->right);
   cout<<pNode->value<<' ';
  }
  else if(nodeQueue.size()) //如果结点为空并且队列也为空，那么所有结点都已访问
  {
   nodeQueue.push(NULL);
   cout<<endl;
  }
 }
}

扩展二：之前讨论的都是从上往下、从左往右遍历二叉树，那么如果希望自下往上、从左右往右遍历二叉树，该如何修改代码呢？
       思路：比较简单的方法，首先遍历二叉树，将所有结点保存在一个数组中，遍历的同时记录每一层在数组中的起止位置。然后根据起止位置，就可以自下往上的打印二叉树的结点。

//每层的起止位置
struct Pos
{
 int begin;
 int end;
 Pos(int b, int e): begin(b),end(e) {}
};
void LevelReverse(BSTreeNode *pRoot)
{
 if(pRoot == NULL)
  return; 

 vector<BSTreeNode*> vec; //用以存放所有结点
 vector<Pos> 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);
   cur++;
  }
  level++; //层数加1
 } 

 for(int i = level - 1; i >= 0; i--) //自下往上遍历
 {
  for(int j = pos[i].begin; j < pos[i].end; j++)
   cout<<vec[j]->value<<' ';
  cout<<endl;
 }
}

输入一颗二元查找树，将该树转换为它的镜像
  问题描述：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 
        例如输入：

 8
 / /
 6 10
 // //
5 7 9 11

输出：

 8
 / /
 10 6
 // //
11 9 7 5

定义二元查找树的结点为：

struct BSTreeNode
{
 int value;
 BSTreeNode *left;
 BSTreeNode *right;
};

思路：题目要求用两种方法，递归和循环，其实质是一样的。
      解法一：用递归。假设当前结点为pNode，只需交换该结点的左右子女，然后分别递归求解左子树和右子树即可。代码极为简单。
      解法二：用循环，需要一个辅助栈完成，每次取栈顶元素交换左右子女，然后将左右子女分别压入辅助栈，当栈中元素为空时，结束循环。其实不论是递归也好，循环也好，都是利用栈的特性完成。
      参考代码：

//函数功能 ： 输入一颗二元查找树，将该树转换为它的镜像
//函数参数 ： pRoot为根结点
//返回值 ： 根结点
BSTreeNode * Mirror_Solution1(BSTreeNode * pRoot)
{
 if(pRoot != NULL)
 {
  BSTreeNode * pRight = pRoot->right;
  BSTreeNode * pLeft = pRoot->left;
  pRoot->left = Mirror_Solution1(pRight); //转化右子树
  pRoot->right = Mirror_Solution1(pLeft); //转化左子树
 }
 return pRoot;
}
BSTreeNode * Mirror_Solution2(BSTreeNode * pRoot)
{
 if(pRoot != NULL)
 {
  stack<BSTreeNode *> stk; //辅助栈
  stk.push(pRoot);   //压入根结点
  while(stk.size())
  {
   BSTreeNode *pNode = stk.top();
   BSTreeNode *pLeft = pNode->left;
   BSTreeNode* pRight = pNode->right;
   stk.pop(); 

   if(pLeft != NULL)
    stk.push(pLeft);
   if(pRight != NULL)
    stk.push(pRight);
   pNode->left = pRight; //交换左右子女
   pNode->right = pLeft;
  }
 }
 return pRoot;
}

判断整数序列是不是二元查找树的后序遍历结果
问题描述：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

   8
  / /
  6 10
 / / / /
 5 7 9 11

因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
         思路：分析后序遍历的特点，序列的最后一个数应该是根结点，剩余的节点分为两个连续的子序列，前一子序列的值小于最后一个数，后一子序列的值大于最后一个数。然后递归求解这两个子序列。
         如果是判断是前序遍历也很简单，只不过根节点变为了第一个数，剩余的节点也是分为两个连续的子序列。如果判断是中序遍历，更方便，只需扫描一遍，检查序列是不是排好序的，如果没有排好序，就不是中序遍历的结果。

把二元查找树转变成排序的双向链表
    问题描述：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

 10
 / /
 6 14
 / / / /
4 8 12 16

转换成双向链表

4=6=8=10=12=14=16

思路：利用递归的思想求解，分别调整某结点的左右子树，调整完后，将该结点的左指针指向左子树的最大节点，右指针指向右子树的最小节点。
   代码如下：

BSTreeNode * Convert(BSTreeNode *node)
{
 if(node == NULL)
  return NULL;
 BSTreeNode *leftMax,*rightMin;
 leftMax = node->left;
 rightMin = node->right;
 //找到左子树的最大结点
 while(leftMax != NULL && leftMax->right != NULL)
  leftMax = leftMax->right;
 //找到右子树的最小结点
 while(rightMin != NULL && rightMin->left != NULL)
  rightMin = rightMin->left;
 //递归求解
 Convert(node->right);
 Convert(node->left);
 //将左右子树同根结点连起来，只不过是以兄弟的关系
 if(leftMax != NULL)
  leftMax->right = node;
 if(rightMin != NULL)
  rightMin->left = node;
 node->left = leftMax;
 node->right = rightMin;
 return node;
}

测试当中，需要建立二叉搜索树，下面给出建立及遍历二叉树的代码。

struct BSTreeNode
{
 int value;
 BSTreeNode *left;
 BSTreeNode *right;
};
BSTreeNode * Insert(BSTreeNode *p, int x)
{
 if(p == NULL)
 {
  p = new BSTreeNode;
  p->value = x;
  p->left = NULL;
  p->right = NULL;
 }
 else
 {
  if(p->value > x)
   p->left = Insert(p->left, x);
  if(p->value < x)
   p->right = Insert(p->right, x);
 }
 return p;
}
void Traverse(BSTreeNode *p) //中序遍历
{
 if(p == NULL)
  return;
 Traverse(p->left);
 cout<<p->value<<' ';
 Traverse(p->right);
}

在二元树中找出和为某一值的所有路径（树）
   问题描述：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。
例如输入整数22和如下二元树

 10
 / /
 5 12
 / /
4  7

则打印出两条路径：10, 12和10, 5, 7。
二元树节点的数据结构定义为：

struct BinaryTreeNode
{
int data;
BinaryTreeNode *pLeft;
BinaryTreeNode *pRight;
};

思路：递归的思想。很多树的题目都是用递归解决的，例如把二元查找树转变成排序的双向链表（树）。递归的终止条件为当前为空结点或当前结点的值大于剩余和。如果当前结点的值等于剩余和，并且是叶结点，那么打印路径。否则，将剩余和减去当前结点的值，递归求解。至于路径的记录，可以利用栈的思想来实现。
       代码：

void FindPath(BinaryTreeNode *pNode,int sum,vector<int> &path)
{
 //结点为空或值大于当前和
 if(pNode == NULL || pNode->data > sum)
  return;
 path.push_back(pNode->data);
 //判断是不是叶结点
 bool isLeaf = (pNode->pLeft == NULL && pNode->pRight == NULL)? true: false;
 //找到一条路径，打印
 if(pNode->data == sum && isLeaf)
 {
  vector<int>::iterator iter = path.begin();
  for(; iter != path.end(); iter++)
   cout<<*iter<<' ';
  cout<<endl;
 }
 else
 {
  //求剩余和
  sum = sum - pNode->data;
  //递归求解
  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
{
  int data;
  BinaryTreeNode *pLeft;
  BinaryTreeNode *pRight;
};
//函数功能 ： 判断二叉树是不是平衡的
//函数参数 ： pRoot为根结点，pDepth为根结点的深度。
//返回值 ：  是否平衡的
bool IsBalanced(BinaryTreeNode *pRoot, int *pDepth)
{
  if(pRoot == NULL)
  {
    *pDepth = 0;
    return true;
  }
  int leftDepth, rightDepth; //左右子树的深度
  if(IsBalanced(pRoot->pLeft, &leftDepth)&&
    IsBalanced(pRoot->pRight, &rightDepth))
  {
    int diff = leftDepth - rightDepth;
    if(diff == 0 || diff == 1 || diff == -1) //相差为0或1或-1
    {
      *pDepth = 1 + (leftDepth > rightDepth ? leftDepth: rightDepth);
      return true;
    }
    else
      return false;
  }
  return false;
}