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));
}
} View Code
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;
} View Code
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;
} View Code
4：将左右節點交換
第一種（書上）：
void swap(bitTree b)
{
if(b)
{
swab(b->lchild);
swap(b->rchild);
temp=b->lchild;
b->lchild=b->rchild;
b->rchild=temp;
}
} View Code
第二種：
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;
} View Code
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的雙親，傳回雙親節點
}
} View Code
第二種（書上）：
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:
} View Code
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);
}
} View Code
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);
}
}
}
} View Code
第二種：
//層次周遊找到元素值為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);
} View Code
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));
}
}
} View Code
第二種（書上）：
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;
} View Code
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
} View Code
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;
} View Code
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;//沿着右分支向下周遊
}
}
} View Code
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;
} View Code
12：設有滿二叉樹，已知先序周遊，求後序周遊
/**
1
2 3
4 5 6 7
先序周遊：1 2 4 5 3 6 7
後序周遊：4 5 2 6 7 3 1
化分函數(樹先序序列 ){
if（序列數量大于一個）{
化分函數(左子樹先序序列)；
化分函數(右子樹先序序列)；
}
輸出根（頭部序列）；
}
*/
void preTopostAction(char a[],int begin,int end)
{
char root=a[begin];//暫存根，子樹周遊完後最後輸出
if(begin+1<=end)
{
begin=begin+1;//左端+1（把根節點獨立出來）
//此時左子樹從begin+1位開始，到(begin+end)/2)結束
preToPost(a, begin,((begin+end)/2)); //左子樹
//此時右子樹從((begin+end)/2) + 1)位開始，到end結束
preToPost(a, (((begin+end)/2) + 1), end); //右子樹
}
printf("%c",root);
}
void preTopost(char a[],int len)//先序周遊數組和數組長度
{
preTopostAction(a,0,len-1);
} View Code
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;
} View Code
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(")");
}
}