一波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<<' '; 
 } 
} 

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; 
}; 

//函数功能 ： 输入一颗二元查找树，将该树转换为它的镜像 
//函数参数 ： 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; 
} 

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

 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); 
} 

 10 
 / / 
 5 12 
 / / 
4  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(); 
} 

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; 
}