1.復制一顆二叉樹的算法

樹的存儲結構如下： typedef int ElemType; typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 復制一顆樹 bool CopyTreeIsOK(BiTree p){if(CopyTree(p)==NULL)return false;return true; } BiTree CopyTree(BiTree p){if(!p) return NULL;BiTree q=new BiTNode;q->data=p->data;q->lchild=CopyTree(p->lchild);q->rchild=CopyTree(p->rchild);return q; }

2.設二叉樹以鏈式表示，輸出二叉樹中各節點的數據以及所在層數

void PrintTreeHeighValue(BiTree p){PrintValue(p,0); } void PrintValue(BiTree p,int h){if(!p) return;printf(“The BiTNode data equal %d, The heigh is %d”,p->data,h);PrintValue(p->lchild,h+1);PrintValue(p->rchild,h+1); }

3.判斷一顆樹是否為二叉排序樹

bool isBSTree(BiTree p){if(!p) return true;else if(p->lchild&&p->data<p->lchild->data) return false;else if(p->rchild&&p->data>p->rchild->data) return false;else if(!p->lchild&&!p->rchild) return true;return isBSTree(p->lchild)&&isBSTree(p->rchild); }

4.設計一個算法返回二叉樹T的先序序列的最后一個節點的指針，要求采用非遞歸形式，且不允許用棧。

BiTNode* FindProPointer(BiTree T){BiTNode *p=T;while(1){if(p->rchild) p=p->rchild;else if(p->lchild) p=p->lchild;else if(!p->lchild&&!p->rchild) break;}return p; }

5.在二叉樹中查找值為x的結點，要求打印x結點的所有祖先，假設值為x的結點不多于一個。

typedef int Elemtype; void PrintAncestors(BiTree T,const Elemtype x){printf(“The ancestors :”)Ancestors(T,x); } bool Ancestors(BiTree T,const Elemtype x){if(!T) return false;else if(T->data==x) return true; else{bool left=Ancestor(T->lchild,x);bool right=Ancestor(T->rchild,x);if(left||right) printf(“%d\n”,T->data);return (left||right);} }

6.求元素為x節點的子二叉樹高度
typedef int ElemType; void FindValue(BiTree T,const ElemType x){if(T){if(T->data==x){printf(“In this BiTree the height is %d when the data equals %d”,GetHeight(T),x);return;}FindValue(T->lchild,x);FindValue(T->rchild,x);} } int GetHeight(BiTree T){if(!T) return;int l= GetHeight(p->lchild);int r=GetHeight(p->rchld);return r>l?(r+1):(l+1) }

7.分別寫出下面算法：在中序線索二叉樹T中查找給定的結點*p在中序列中序列的前驅和后繼。

(1)???中序線索二叉樹中查找p的中序前驅結點，并用pre指針返回結果

ThreadNode * InPre(ThreadNode *q){ThreadNode *pre;if(p->ltag==1) //無左孩子pre=p->lchild;else{for(q=p->lchild;q->rtag==0;q=q->rchild); //左子樹最右邊pre=q;}return pre; }

(2)???在中序線索二叉樹T中找結點的中序后繼結點

ThreadNode *InSucc(ThreadNode *p){ThreadNode *succ;if(p->rtag==1)succ=p->rchild;else{for(q=p->rchild;q->ltag==0;q=q->lchild); //右子樹最左邊succ=q;}return succ; }

8.設計一個算法求二叉樹的內路徑長度和外路徑長度。（擴展：求內外路徑長度只差的絕對值）

void PathLength(BiTree T){int Ipath=0,Epath=0;PL(t,&Ipath,Epath,0);printf(“%d\t%d”,Ipath,Epath); } void PL(BiTree T, int *Ipath,int *epath,int h){if(!T) return;else if(!T->lchild&&!T->rchild) Epath+=h;else Ipath+=h;PL(T->lchild,Ipath,Epath,h+1);PL(T->rchild,Ipath,Epath,h+1); }

9.設將二叉樹的寬度定義為具有結點數量最多的某一層中包含的結點個數。設計一個算法求二叉樹的寬度。

#define MaxSize 1024 typedef struct SqQueue{ElemType data[MaxSize];int front,rear; }SqQueue; int WeightOfTree(BiTree T){sqQueue Q; //這個隊列用來存樹的結點BiTNode *p; int maxWeight=0;int curWeight=0;EnQueue(Q,T);for(!IsEmpty(Q)){curWeight=(Q.rear+MaxSize-Q.front)%MaxSize; //隊列的寬度if(curWeight>maxWeight) maxWeight=curWeight;for(int i=0;i<curWeight;i++){p=DeQueue(Q);if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) EnQueue(Q,p->rchild);}}return maxWeight; }

10.設計一個算法判斷二叉樹是否是完全二叉樹（遞歸和非遞歸）

非遞歸：

bool IsComplete(BiTree T){SqQueue Q;BiTNode *p;EnQueue(Q,p);while(!IsEmpty(Q)){p=DeQueue(Q);if(p){EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);}else{while(!IsEmpty(Q)){p=DeQueue(Q);if(!p) return false;}return true;}} }

遞歸：

bool IsComplete(BiTree T){int h=GetHeight(T);int num=1;for(int i=0;i<h;i++) num=num*2;num--; //滿二叉樹總結點數BiTNode *A=new BiTNode*[num];for(int i=0;i<num;i++)A[i]=NULL;Map(T,A,0);bool flag=false;for(int i=0;i<num;i++){if(!flag&&A[i]==NULL) flag=true;if(flag&&A[i]!=NULL) return false;}return true; } void Map(BiTree T,BiTNode *A[],int index){if(!T) return;A[index]=T;Map(T->lchild,A,2*index+1);Map(T->rchild,A,2*index+2); } int GetHeight(BiTree T){if(!T) return;int l= GetHeight(p->lchild);int r=GetHeight(p->rchld);return r>l?(r+1):(l+1) }

11.設計一個盡可能快的算法，求出在一顆二叉排序樹種關鍵字大于K的結點的數量。

int Count(BiTree T,int K){if(!T) return 0;if(T->data<=k) return Count(T->rchild);else return Count(T->lchild)+1+Count(T->lchild)+1; }

12.在一棵二叉樹中，設p和q分別為二叉樹中任意兩個結點，編寫算法找到p和q的最近公共祖先結點。

bool IsAncestor(BiTree T,BiTNode *x,Stack *S){if(!T) return false;if(T==x||IsAncestor(T->lchild,x,S)||IsAncestor(T->rchild,x,S)){Push(S,T);return true;}return false; } BiTNode *FindNearesAncestor(BiTree T,BiTNode *p,BiTNode *q){BiTNode *tp=NULL,*tq=NULL;Stack Sp,Sq;if(!IsAncestor(T,p,Sp)) return NULL;if(!IsAncestor(T,q,Sq)) return NULL;while(!IsEmpty(Sp)||!IsEmpty(Sq)){if(tp==tq&&top(Sp)!=top(Sq))return tp;tp=Pop(Sp);tq=Pop(Sq);} }

總結

以上是生活随笔為你收集整理的数据结构-树的进阶代码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。