1.设计一个非递归算法，求二叉树的高度
思路：采用层序遍历，设置一个last指针指向所在层的最右节点，每次出队时与last指针比较
如果相等则层数+1
int Btdepth(BiTree T){
//采用层序遍历
if(!T) return 0;
int front=-1,rear=-1;
int last=0,level=0; //last指向当前层的最右节点
BiTree Q[MaxSize]; //创建队列Q
Q[++rear] = T; //根节点入队
Bitree p;
while(front < rear){ //队列不空
p = Q[++front];
if(p->lchild){
Q[++rear] = p->lchild; //左孩子入队
}
if(p->rchild){
Q[++rear] = p->rchild; //右孩子入队
}
if(front = last){ //处理该层的最右节点
level++; //层数+1
}
last = rear; //last指向下层
}
return level;
}
/*
递归写法
*/
int Btdepth2(BiTree T){
if(T ==NULL) return 0;
ldep = Btdepth2(T->lchild); //左子树高度
rdep = Btdepth2(T->rchild); //右子树高度
return ldep>rdep: ldep+1 ? rdep+1;
}
2.根据先序和中序遍历创建二叉树链表
思路：中序遍历可以划分左右子树，而先序遍历可以确定根节点
BiTree PreInCreat(int A[],int B[],int l1,int h1,int l2,int h2){
//l1,h1为先序的第一个和最后一个节点的下标
//l2,h2为中序的第一个和最后一个节点的下标
//初始调用时，l1=l2=1,h1=h2=n
root = (BiTNode*)malloc(sizeof(BiTNode)); //建根节点
root->data = A[l1]; //根节点
for(i=l2; B[i]!=root->data; i++); //根节点在中序中的划分
llen = i-l2; //左子树长度
rlen = h2-i; //右子树长度
if(llen){
//递归建立左子树
root->lchild = PreInCreat(A,B,l1+1,l1+llen,l2,l2+llen-1);
}else{ //左子树为空
root->lchild = NULL;
}
if(rlen){
//递归建立右子树
root->rchild = PreInCreat(A,B,h1-rlen+1,h1,h2-rlen+1,h2);
}else{ //右子树为空
root->lchild = NULL;
}
return root; //返回根节点指针
}
3.判二叉树是否为一个完全二叉树
思路：使用层次遍历，当遇到空节点时，则查看其后是否有非空节点，
若有则不是完全二叉树
bool IsComplete(BiTree T){
InitQueue(Q);
if (!T) return 1;
EnQueue(Q,T); //入队根节点
while(!IsEmpty(Q)){
DeQueue(Q,p);
if(p){
//节点非空,将其左右子树入列
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild);
}else{
while (！IsEmpty(Q)){
/* 节点为空，检查其后是否有非空节点 */
DeQueue(Q,p);
if(p){ //节点非空，不是完全二叉树
return 0;
}
}
}
}
return 1;
}
4.计算二叉树中所有的双分支节点个数
思路：普通的中序遍历，将访问变为判断是否有两个孩子
int c=0;
void Judge(BiTree T){
Judge(T->lchild);
if(T->lchild && t->rchild) c++;
Judge(T->rchild);
}
5.将一个二叉树的所有节点的左右子树进行交换
思路：先交换左孩子，后交换右孩子
void Swap(BiTree b){
Swap(T->lchild); //递归交换左子树
Swap(T->rchild);
//交换左右孩子节点
temp = b->lchild;
b->lchild = b->rchild;
b->rchild = temp;
}
6.求先序遍历的序列中，第K个节点的值
思路：设置一个全局遍历用来计数
int i = 1;
ElemType PreNode(BiTree b,int k){
if(b == NULL) return '#'; //空节点
if(i == k) return b->data; //当前节点为第K哥节点
i++; //下一个节点
ch = PreNode(b->lchild,k); //左子树中递归寻找
if(ch != '#'){
return ch;
}
ch = PreNode(b->rchild,k); //右子树中递归寻找
return ch;
}
7.找出每个值为x的节点，删除以它为根的子树，并释放空间
先层次遍历(层次遍历 便于找父节点)，再删除子树
void DeleteXTree (BiTree bt){ //删除以bt为根的子树
if(bt){
DeleteXTree(bt->lchild);
DeleteXTree(bt->rchild);
free(bt);
}
}
void Search (BiTree bt , ElemType x){
BiTree Q[]; //Q是存放二叉树节点指针的队列
if(bt){
if(bt->data==x) { //若根节点就是x，则删除整个树
DeleteXTree(bt);
exit(0);
}
Queue(Q);
EnQueue(Q,bt);
while (!IsEmpty(Q)){ //若左子树非空
DeQueue (Q,p);
if(p->lchild){
if(p->lchild->data == x){
DeleteXTree(p->lchild);
p->lchild=NULL;
}else{
EnQueue(Q,p->lchild); //左子树入列
}
}
if(p->lchild){
if(p->rchild->data == x){
DeleteXTree(p->rchild);
p->rchild=NULL;
}else{
EnQueue(Q,p->rchild); //右子树入列
}
}
}
}
}
8.二叉树中找到值为x的节点，并打印出他的所有祖先
思路：判断一个节点的左右孩子是否为x，如果是，则入栈。
//非递归
typedef struct {
//tag=0表示左子女被访问，tag=1表示右子女被访问
BiTree t;
int tag;
}stack;
void Serch(BiTree bt,ElemType x){
stack s[];
while (bt!=NULL && bt->data!=x){ //节点入栈
s[++top].t = bt;
s[top].tag = 0;
bt = bt->lchild; //沿左分支向下
}
if(bt->data == x){
for (i = 0; i <= top; i++){
printf("%d",s[i].t->data); //输出祖先值后 结束
exit(1);
}
}
while(top!=0 && s[top].tag==1){
top--;
}
if(top != 0){
s[top].tag = 1;
bt = s[top].t->rchild; //沿右分支向下
}
}
//递归算法
initial stack;
bool Ancestors(Node* root,int x){
if(!root) return false;
if(root->data == x)return true;
if(Ancestors(root->lchild,x) || Ancestors(root->rchild,x)){
stack.push(root->data);
return true;
}
return false;
}
9.二叉树中p和q任意指向两个节点，找出他们最近的公共祖先节点
占位
10.求二叉树的宽度
思路：采用层次遍历求出所有节点的层次，并将所有的节点和对应的层次放在一个队列中，
然后通过扫描队列求出各层的节点总数，最大的层节点的总数即为二叉树的宽度。
//非递归
typedef struct {
//tag=0表示左子女被访问，tag=1表示右子女被访问
BiTree data[MaxSize]; //保存队列中的指针节点
int level[MaxSize]; //保存data中的相同下标节点的层次
int front,rear;
}Qu;
int BTWidth(BiTree b){
BiTree p;
int k,max,i,n;
Qu.front = Qu.rear = -1; //队列为空
Qu.rear++;
Qu.data[Qu.rear] = b; //根节点指针入队
Qu.level[Qu.rear] = 1; //根节点层次为1
while(Qu.front <Qu.rear){
Qu.front++; //出队
p = Qu.data[Qu.front]; //出队节点
k = Qu.level[Qu.front]; //出队节点的层次
if(p->lchlid != NULL){
//左孩子进队列
Qu.rear++;
Qu.data[Qu.rear] = p->lchild;
Qu.levek[Qu.rear] = k+1;
}
if(p->rchlid != NULL){
//右孩子进队列
Qu.rear++;
Qu.data[Qu.rear] = p->rchild;
Qu.levek[Qu.rear] = k+1;
}
}
max = 0; //max保存同一层最多的节点个数
i=0,k=1; //k表示从第一层开始查找
while(i < Qu.rear){ //i扫描队中的所有元素
n = 0;
while(i<=Qu.rear && Qu.level[i]==k){
n++;
i++;
}
k = Qu.level[i];
if(n > max) max = n; //保存最大的n
}
return max;
}
11.将二叉树的叶子结点串成一个单链表
思路：采用中序遍历，设置前驱指针pre，第一个叶节点由指针head指向，
遍历到叶节点时，就将它的前驱rchlid指针指向它，最后一个叶节点的rchild为空.
LinkedList head,pre=NULL;
LinkedList InOrder(BiTree bt){
if(bt){
InOrder(bt->lchild); //中序遍历左子树
if(bt->lchlid==NULL && bt->rchlid==NULL){ //此节点为叶节点
if(pre == NULL){ //处理第一个叶节点
head = bt;
pre = bt;
}else{ //将叶节点链接到链表
pre->rchild = bt;
pre = bt;
}
InOrder(bt->rchild); //中序遍历右子树
pre->rchild = NULL;
}
}
return head;
}
12.判断两个子树是否相似
题目中相似的概念为：两棵子树都是空的或都只有一个根节点；或左右子树都相似
思路：递归比较左右子树是否相似
int Similar(BiTree T1,BiTree T2){
int lefts,rigths;
if(T1==NULL && T2==NULL) return 1; //全空
else if(T1==NULL || T2==NULL){ //其中一个为空
return 0;
}else{
lefts = Similar(T1->lchild,T2->lchlid);
rigths = Similar(T1->lchild,T2->rchlid);
return lefts&&rigths;
}
}