笔试题:二叉树按层遍历添加兄弟指针求LCA排序二叉树的查找

二叉树按层遍历添加兄弟指针求LCA排序二叉树的查找"/>

笔试题:二叉树按层遍历添加兄弟指针求LCA排序二叉树的查找

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或bNodePtr pright = LCA(root->pRight,a,b);//在右子树找到a或b//a,b分别分布在左右子树，则此根结点即LCAif(pleft&&pright)return root;//右子树中找不到a,b，则在左子树中找到的LCA即是root下的LCAif(pleft!=NULL)return pleft;//左子树中找不到a,b，则在右子树中找到的LCA即是root下的LCAif(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 7nodes[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 17nodes[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;
}

转载于:.html