1：判断是否为平衡二叉树
int depth(bitTree T) { if(!T) return 0; else return max(depth(T->lchild),depth(T->rchild))+1; //这有个缺点，空树会返回深度1 } //判断平衡二叉树 int balance(bitTree t) { int left,right; int cha; if(t!=NULL) { left=depth(t->lchild); right=depth(t->rchild); cha=left-right; if(cha>1||cha<-1) { return false; } return balance(t->lchild)&&balance((t->rchild)); } }
2：判断是否为完全二叉树
/**层次遍历，根入队入队 1: 若队列当前节点左右节点均存在 存入队列 2：若队列当前节点的左节点存在，右节点不存在 设置bj=0 其之后的节点不能有左右节点 3：若队列当前节点不存在左节点，存在右节点，设置cm=1 4：若当前节点不存在左右节点，设置bj=0，之后节点不能存在左右节点 */ int wanquan(bitTree t) { if(t==NULL)return 0; QueuePtr q; InitQue(q); bitTree p=t; int cm=1; //用cm变量值表示迄今为止二叉树为完全二叉树 //（其初值为1，一旦发现不满足上述条件之一，则置cm为0 //结束后返回cm的值 int bj=1; //bj变量值表示迄今为止所有节点均有左右孩子（其初值为1）， //一旦发现一个节点没有左孩子或没有右孩子时置bj为0 if(!p->lchild&&p->rchild)return 0;//如果根只有右子树，没有左子树，肯定就不是 EnQue(q,p); /** 1 2 3 4 5 6 7 目前队列: 7 出队元素:1 2 3 4 5 6 cm:1 1 1 1 1 1 1 1 bj:1 1 1 1 0 0 0 0 1 2 3 4 5 目前队列: 5 出队元素:1 2 3 4 5 cm:1 1 1 0 0 0 bj:1 1 0 0 0 0 1 2 3 4 目前队列: 出队元素:1 2 3 4 cm:1 1 1 1 1 bj:1 1 0 0 0 1 2 3 4 5 6 目前队列: 出队元素:1 2 3 4 5 6 cm:1 1 1 1 1 1 1 bj:1 1 1 0 0 0 0 */ while(DeQue(q,p)&&cm) { if(p->lchild&&p->rchild)//左右节点存在 { if(bj==0)cm=0;break;//bj为0说明上一颗树没有右孩子或者说两个孩子都没，所以这棵树不能有孩子 EnQue(q,p->lchild); EnQue(q,p->rchild); } if(p->lchild&&!p->rchild)//左节点存在，右节点不存在 { if(bj==0)cm==0;break;//bj为0说明上一颗树没有右孩子或者说两个孩子都没，所以这棵树不能有孩子 EnQue(q,p->lchild); bj=0; } if(!p->lchild&&p->rchild) //左节点不存在，右节点存在，没有左孩子直接判死刑 { cm=0， } if(!p->lchild&&!p->rchild)//两个孩子都没有，则队列中的下一个元素不能有孩子 { bj=0; } } return cm; }
3：求双节点个数
int sum=0; int twoSon(bitTree t) { if(!t)return 0; if(t->lchild!=NULL&&t->rchild!=NULL) { sum++; twoSon(t->lchild); twoSon(t->rchild); } else { twoSon(t->lchild); twoSon(t->rchild); } return sum; }
4：将左右节点交换
第一种（书上）：
void swap(bitTree b) { if(b) { swab(b->lchild); swap(b->rchild); temp=b->lchild; b->lchild=b->rchild; b->rchild=temp; } }
第二种：
int changeson(bitTree t) { if(!t)return 0; LinkQueue q; InitQue(q); EnQue(&q,t); bitTree p; bitTree temp; while(QueEmpty(q))//队列不为空 { DeQue(&q,&p);//出队 if(p->lchild!=NULL&&p->rchild!=NULL)//左右节点存在，交换 { temp=p->lchild; p->lchild=p->rchild; p->rchild=temp; EnQue(&q,p->lchild); EnQue(&q,p->rchild); } if(p->lchild!=NULL&&p->rchild==NULL)//左节点存在右节点不存在 左节点变成右节点 { p->rchild=p->lchild; EnQue(&q,p->lchild); } if(p->lchild!=NULL&&p->rchild==NULL)//左节点不存在右节点存在 由节点变成左节点 { p->lchild=p->rchild; EnQue(&q,p->rchild); } } return 1; }
5：root指向根节点，p，q指向二叉树任意两个节点的指针，找到p，q公共祖先节点
第一种：
//辅助函数 T若为空返回，否则若等于要找得数返回真， //或者有孩子节点等于要找得数返回真，且t为e status Search(bitTree T,bitTree e) { if(!T) return FALSE; if(T==e||Search(T->lchild,e)==TRUE||Search(T->rchild,e)==TRUE) return TRUE; else return FALSE; } //若e是T中某个非根结点，则返回它的双亲，否则返回NULL，前提T存在 bitTree Parent(bitTree T,bitTree e) { if(T==e)//没有双亲 return NULL; if(T->lchild==e||T->rchild==e)//根节点是双亲 return T; else if(Search(T->lchild,e)==TRUE)//根节点的左子树有要找得数 执行完search t指向e这个值的双亲，t->lchild指向e return Parent(T->lchild,e);//返回父母节点 else if(Search(T->rchild,e)==TRUE)//根节点的右子树有要找得数t指向e这个值的双亲，t->lchild指向e return Parent(T->rchild,e);//返回父母节点 else return NULL; } void searchParent(bitTree root,bitTree p,bitTree q,bitTree r) { if(!root||!p||!q)return 0; bitTree pp; pp=p; while(pp!=NULL) { //以pp为根节点,第一次以p为根节点,在子树找q，找到说明pp是公共祖先节点 if(Search(pp,q)==TRUE){ r=pp; break; } pp=Parent(root,pp);//在树中找到pp的双亲，返回双亲节点 } }
第二种（书上）：
stack s[],s1[]; bitTree ancestor(bitTree root,bitNode *p,bitNode *q) { top=0;bt=root; while(bt!=NULL||top>0) { while(bt!=NULL) { s[++top].t=bt; s[top].tag=0; bt=bt->lchild;//沿左分支向下 } while(top!=0&&s[top].tag==1) { //假设p在q的左侧，遇到p栈中元素均为p祖先 if(s[top].t==p) { for(i=1;i<=top;i++) { s1[i]=s[i]; top1=top; } } if(s[top].t==q) { for(i=top;i>0;i--)//将栈中元素的树节点到s1中去匹配 { for(j=top1;j>0;j--) { if(s1[j].t==s[i].t)return s[i].t;//p和q的最近公共祖先已找到 } } top--; } } if(top!=0) { s[top].tag=1; bt=s[top].t->rchild; } } return NULL: }
6：二叉树的带权路径长度WPL所有叶节点的带权路径之和
/** 1 2 3 4 5 6 7 基于先序遍历，用一个静态变量保存WPL把每个节点的深度作为参数传递 若为叶子结点，WPL=该节点深度*权值，若非叶子节点则递归调用 */ int wpl=0; void preOrderRoad(bitTree t,int dept) { if(t==NULL) { return 0; } if(t->lchild==NULL&&t->rchild==NULL) { wpl=wpl+t->data*dept; return; } else { preOrderRoad(t->lchild,dept+1); preOrderRoad(t->rchild,dept+1); } }
7：对树中每个元素值为X的节点，删去以他为根的子树，并释放相应空间
第一种（书上）：
void deleteXtree(bitTree &bt) { if(bt) { deleteXtree(bt->lchild); deleteXtree(bt->rchild); free(bt); } } void search(bitTree bt,int x) { bitTree Q[];//存放二叉树队列节点指针 if(bt) { if(bt->data==x) { deleteXtree(bt); exit(0); } InitQueue(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->rchild) { if(p->rchild->data==x) { deleteXtree(p->rchild); p->rchild=NULL; } else EnQueue(Q,p->rchild); } } } }
第二种：
//层次遍历找到元素值为x的节点，递归删除子树，释放空间 int delectX(bitTree &t,int x) { if(!t)return 0; QueuePtr q; InitQue(q); EnQue(&q,t); bitTree bnode; while(DeQue(&q,bnode)) { if(bnode->data==k) { if(t->rchild!=NULL)del(t->rchild); if(t->lchild!=NULL)del(t->lchild); continue; } if(bnode->rchild!=NULL) { EnQue(&q,*(bnode->rchild)); } if(bnode->lchild!=NULL) { EnQue(&q,*(bnode->lchild)); } } } int del(bitTree t) { if(!t)return 0; if(t->rchild==NULL&&t->lchild==NULL) { free(t); } if(t->rchild!=NULL)del(t->rchild); if(t->lchild!=NULL)del(t->lchild); }
8：求先序遍历第k个节点的值
第一种：
//非递归先序遍历计数，每遍历一个数加一到k,输出当前值的结果 int searchK(bitTree *t,int k) { Stack st; if(!st)return 0; if(!t)return 0; push(st,*t); bitTree tno; int i=0 while(pop(st,tno)) { i++; if(i==k) { printf("%d",tno->data); break; } if(tno.rchild!=NULL) { push(st,*(tno.rchild)); } if(tno.lchild!=NULL) { push(st,*(tno.lchild)); } } }
第二种（书上）：
int i=1; int preNode(bitTree b,int k) { if(b==NULL)return '#'; if(i==k)return b->data; i++; ch=preNode(b->lchild,k); if(ch!='#')return ch; ch=preNode(b->rchild,k);return ch; }
9：二叉树各节点值互不相同，先序遍历A[1...n]和中序遍历B[1...n] 编写算法建立二叉链表
/** 1 2 3 4 5 6 7 先序遍历： 1 2 4 5 3 6 7 中序遍历： 4 2 5 1 6 3 7 */ bitTree preINCreat(int a[],int b[],int l1,int h1,int l2,int h2) { //l1,h1为先序的第一和最后一个节点下标，l2，h2位中序的第一和最后一个下标 l1=l2=1,h1=h2=n; root=(bitTree)malloc(sizeof(bitTree)); 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->rchild=NULL;//右子树为空 return root }
10：打印数值为x的节点的祖先
第一种：
int prPar(bitTree T,int x) { bitTree tnode; // tnode=Parent(T,x); // if(tnode!=NULL) // { // printf("%d",tnode->data); // } if(T==x)return NULL; if(T->lchild==x||T->rchild==x) { tnode=T; return tnode;//找到双亲节点 } else if(Search(T->lchild,x)==TRUE) { prPar(T->lchild,x); } else if(Search(T->rchild,x)==TRUE) { prPar(T->rchild,x); } else return NULL; }
第二种（书上）：
typedef struct { bitTree t; int tag;//0:左子女被访问，1右子女被访问 }stack; void Search(bitTree bt,int x) { stack s[]; top=0; while(bt!=NULL||top>0) { while(bt!=NULL&&bt->data!=x) { a[++top].t=bt; s[top].tag=0; bt=bt->lchild;//沿左分支向下 } if(bt->data==x) { printf("所查节点的所有祖先节点的值"); for(i=1;i<=top;i++) { printf("%d",s[i].t->data); } exit(0); } while(top!=0&&s[top].tag==1)//退栈 { top--; } if(top!=0) { s[top].tag=1; bt=s[top].t->rchild;//沿着右分支向下遍历 } } }
11：求非空二叉树宽度
/** 求非空二叉树宽度 设置宽度初值num0 1 2 3 4 5 6 7 设计结构为 队列，顺序遍历二叉树，一层遍历完之后，剩下的都是下一层 第一层 cur=1 cur--直到cur=0，计算当前队列长赋值于cur=2 第二层 cur=2 cur--直到cur=0，计算当前队列长赋值于cur=4 */ int treeWid(bitTree t) { if(!t)return 0; QueuePtr q; InitQue(q); EnQue(&q,t); bitTree bnode; int width=1; int curwidth=1; while(QueEmpty(q)) { while(curwidth!=0) { DeQue(&q,bnode); if(bnode->lchild!=NULL) EnQue(&q,bnode->lchild); if(bnode->rchild!=NULL) EnQue(&q,bnode->rchild); curwidth--; } curwidth=QueueLength(q);//求队列的长度 width=curwidth>width?curwidth:width; } return width; }
12：设有满二叉树，已知先序遍历，求后序遍历
/** 1 2 3 4 5 6 7 先序遍历：1 2 4 5 3 6 7 后序遍历：4 5 2 6 7 3 1 } **/ void preToPost(char *arrPre,char *arrPost,int L1,int h1,int L2,int h2) { int half; if(l1<h1) { half=(h1-L1)/2; *(arrPost+h2)=*(arrPre+L1); preToPost(arrPre,arrPost,L1+1,L1+half,L2,L2+half-1);//左边 preToPost(arrPre,arrPost,L1+half+1,h1,L2+half,h2-1);//右边 } } int main() { char arrPre[]={'a','b','d','y','j','i','d'}; char arrPost[7]; preToPost(arrPre,arrPost,0,6,0,6); for(int i=0;i<7;i++) { printf("%c",*(arrPost+i)); } }
12（1）用先序序列和中序序列建立二叉树
// 用先序序列和中序序列建立二叉树 struct node *create_by_pre_and_mid(int n, char *pre, char *mid) { struct node *root; int i; if(n==0) return NULL; root=(struct node *)malloc(sizeof(struct node)); root->data=pre[0]; for(i=0;i<n;i++) // 寻找左右子树的元素 if(pre[0]==mid[i]) break; root->lt = create_by_pre_and_mid(i, pre+1, mid); // 建立左子树 root->rt = create_by_pre_and_mid(n-i-1, pre+i+1, mid+i+1); // 建立右子树 return root; }
12（2）用后序序列和中序序列建立二叉树
// 用后序序列和中序序列建立二叉树 struct node *create_by_post_and_mid(int n, char *post, char *mid) { struct node *root; int i; if(n==0) return NULL; root=(struct node *)malloc(sizeof(struct node)); root->data=post[n-1]; for(i=0;i<n;i++) // 寻找左右子树的元素 if(post[n-1]==mid[i]) break; root->lt = create_by_post_and_mid(i, post, mid); // 建立左子树 root->rt = create_by_post_and_mid(n-i-1, post+i, mid+i+1); // 建立右子树 return root; }
13：将二叉树叶节点从左到右顺序连成一个单链表，表头指针head，二叉树按二叉链表方式存储，链接时用叶节点的右指针来存放单链表指针
LinkList head,pre=NULL; LinkList Inorder(bitTree bt) { if(bt) { Inorder(bt->lchild);//中序遍历子树 if(bt->lchild==NULL&&bt->rchild==NULL)//叶节点 { if(pre==NULL)//处理第一个叶节点 { head=bt; pre=bt; } else { pre->rchild=bt; pre=bt; } Inorder(bt->rchild);//中序遍历右子树 } pre->rchild=NULL;//设置链表尾 } return head; }
14：判断两个二叉树是否相似
/** t1，t2都是空的或者只有一个根节点，t1.t2左右子树相似 f(t1,t2)=1; t1=t2=NULL f(t1,t2)=0;t1与t2其中一个为空 f(t1,t2)=f(t1->lchild,t2->lchild)&&f(t1->rchild,t2->rchild);t1.t2均不为空 */ int similar(bitTree t1,bitTree t2) { int lefts,rights; if(t1==NULL&&t2==NULL) { return 1; } else if((t1==NULL&&t2!=NULL)||(t2==NULL&&t1!=NULL)) { return 0; } else { lefts=similar(t1->lchild,t2->lchild); rights=similar(t1->rchild,t2->rchild); return lefts&&rights; } }
15：将给定的表达式树转换为等价的中缀表达式（通过括号反映操作符计算顺序）
/** * + * a bc d 表达式树的中序序列加上必要的括号即为等价的中缀表达式，基于二叉树的中序遍历得到所需表达式 除根节点和叶节点之外，遍历到其他节点时在遍历其左子树之前加上左括号，遍历完右子树加上右括号 */ void btreetoE(bitTree *root) { btreetoEXP(root,1); } void btreetoEXP(bitTree *root,int deep) { if(root==NULL)return ; else if(root->left==NULL&&root->right==NULL)//若为叶节点输出 { printf("%s",root->data); } else { if(deep>1)printf("(");//有子表达式加一层括号 btreetoEXP(root->left,deep+1); printf("%s",root->data); // (a+b) * (c*d) btreetoEXP(root->right,deep+1); if(deep>1)printf(")"); } }