1.二叉树按层遍历
2.二叉树添加兄弟指针
3.在二叉树中查找LCA（最近公共祖先）
3.在排序二叉树中找到大于N且最接近N的数
// PrintByLevel.cpp : Defines the entry point for the console application.
// Author : yangyh
#include "stdafx.h"
#include <iostream>
#include <queue>
using namespace std;
typedef struct _node_st{
int value;
_node_st* pLeft;
_node_st* pRight;
_node_st* pNext;
_node_st(){
pLeft=NULL;
pRight=NULL;
pNext=NULL;
}
}Node,*NodePtr;
void visitNode(int level,NodePtr node){
printf("Level% d: %d\n",level,node->value);
}
//在二叉查找树中找到比n大的最接近n的数
int findNum(NodePtr root,int n){
if(!root)return -1;
if(n<root->value)
{
//如果左子树为空，则root->value即为返回值
if(!root->pLeft)return root->value;
//否则在左子树返回结果与root->value对比，取较小值
int left = findNum(root->pLeft,n);
if(left!=-1){
return left<root->value?(left):(root->value);
}
return root->value;
}
return findNum(root->pRight,n);
}
//寻找a b的最近公共祖先，LCA满足一个特征：a,b分别在它的左右子树
//求LCA的解法2：分别用栈保存遍历到a,b的路径，则问题转换为求两链表的交点，
//假设栈A长度为LA，栈B LB，如果LA>LB,则A指针先走LA-LB步，之后同时走，A=B时即为交点
NodePtr LCA(NodePtr root,NodePtr a,NodePtr b){
if(root==NULL)return NULL;
if(a == b)
return a;
if(a==root||b==root)return root;
NodePtr pleft = LCA(root->pLeft,a,b); //在左子树找到a或b
NodePtr pright = LCA(root->pRight,a,b);//在右子树找到a或b
//a,b分别分布在左右子树，则此根结点即LCA
if(pleft&&pright)
return root;
//右子树中找不到a,b，则在左子树中找到的LCA即是root下的LCA
if(pleft!=NULL)
return pleft;
//左子树中找不到a,b，则在右子树中找到的LCA即是root下的LCA
if(pright!=NULL)
return pright;
return NULL;
}
//给二叉树中的同层节点添加兄弟指针
int addSiblingPtr(NodePtr root,void (*visit)(int,NodePtr)){
if(root==NULL)
return 0;
queue<NodePtr> q;
q.push(root);
int level = 1;
while(!q.empty()){
int count = q.size();
NodePtr front=NULL;
NodePtr next=NULL,node;
while(count){
node = q.front();
if(node->pLeft)q.push(node->pLeft);
if(node->pRight)q.push(node->pRight);
q.pop();
visit(level,node);
if(front==NULL)
front = node;
else{
front->pNext=node;
front = node;
}
count--;
}
level++;
node->pNext=NULL;
}
return 1;
}
int main(int argc, char* argv[])
{
//初始二叉树
Node nodes[10];
for(int i=0;i<sizeof(nodes)/sizeof(Node);i++){
nodes[i].value = i;
}
//树结构 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
nodes[1].pLeft=&nodes[2];
nodes[1].pRight=&nodes[3];
nodes[2].pLeft=&nodes[4];
nodes[3].pLeft=&nodes[6];
nodes[2].pRight=&nodes[5];
nodes[3].pRight=&nodes[7];
addSiblingPtr(&nodes[1],visitNode);
printf("%d\n",nodes[2].pNext->value);
printf("%d\n",nodes[4].pNext->value);
printf("%d\n",nodes[5].pNext->value);
printf("%d\n",nodes[6].pNext->value);
printf("%d\n",LCA(&nodes[1],&nodes[7],&nodes[4])->value);
printf("%d\n",LCA(&nodes[1],&nodes[6],&nodes[4])->value);
printf("%d\n",LCA(&nodes[1],&nodes[7],&nodes[6])->value);
//树结构 8
// / \
// 5 13
// / \ / \
// 4 7 11 17
nodes[1].value = 8;
nodes[2].value = 5;nodes[3].value =13;
nodes[4].value = 4;nodes[5].value = 7;
nodes[6].value = 11;nodes[7].value = 17;
printf("%d\n",findNum(&nodes[1],12));
printf("%d\n",findNum(&nodes[1],-2));
printf("%d\n",findNum(&nodes[1],6));
printf("%d\n",findNum(&nodes[1],8));
printf("%d\n",findNum(&nodes[1],10));
return 0;
}