編寫一個算法，判斷給定的二叉樹是否是二叉排序樹

keyType predt=-32767; int JudgeBst(BiTree bt) {int b1,b2;if(bt==null)return null;else{b1=JudegeBst(bt->lchild);if(bt==0||predt>=bt->data)return 0;predt=bt->data;b2=JudegeBst(bt->rchild);return b2;} }

設計一個算法，求出指定結點在給定二叉樹排序樹中的層次

算法思想
設二叉樹采用二叉鏈表存儲結構，在二叉排序樹中，查找一次就下降一層。因此查找該結點所用的次數就是該結點在二叉樹中的層次采用二叉排序樹非遞歸查找算法，用n保存查找層次，沒查找一次，n就+1，直到找到相應的結點。

int level(BiTree br,BSTNode *p) {int n=0;Bitree t=bt;if(bt!=null){n++;while(t->data!=p->data){if(t->data<p->data)t=t->rchild;elset=t->rchild;n++;}}return n; }

采用二叉樹遍歷的思維編寫一個判斷二叉樹是否是平衡二叉樹的算法

算法思想：
設置二叉樹的平衡標記balance，以標記返回二叉樹是否是平衡二叉樹，若為平衡二叉樹，返回1，否則返回0；h為二叉樹的高度，采用前序遍歷的遞歸算法。
①若bt=null 則h=0，balance=1
②bt只有根結點 h=1,balance=1;
③否則，對bt的左右子樹執行遞歸運算，返回左右子樹的高度和平衡標記，bt的高度為最高子樹的高度+1，若左右子樹的高度差大于1，則balance=0.若左右子樹的高度差小于1，則左右子樹都平衡，balance=1.否則balance=0

void Judege_AVL(BiTree bt, int &balance,int &h) {int b1,br,h1,hr;if(bt==null){h=0;balance=1;}else if(bt->lchild==null&&bt->rchild==null){h=1;balance=1;}else{Judege_AVL(bt->lchild,b1,h1);Judege_AVL(bt->rchild,b2,hr);h=(h1>hr?h1:hr)+1;if(abs(h1,hr)<2)balance=b1&&br;elsebalance=0;} }

設計一個算法，求出給定二叉排序樹中最小和最大的關鍵字

在一棵二叉排序樹中，最左下結點即為關鍵字最小的結點，最右下結點即為關鍵字最大的結點。

keyType Minkey(BSTNode *bt) { while(bt->lchild!=null)bt=bt->lchild;return bt->data; } keyType Maxkey(BSTNode *bt) {while(bt->rchild!=null)bt=bt->rchild;return bt->data; }

設計一個算法，從大到小輸出二叉排序樹中所有值不小于k的關鍵字

算法思想：
由二叉排序樹的性質可知，右子樹中所有結點值都大于根結點。左子樹中所有結點值均小于根結點值。為了從大到小輸出，縣遍歷右子樹，再訪問根結點，后遍歷左子樹

void OutPut(BSTNode *bt,keyType k) {if(bt==null)return ;if(bt->rchild!=null)OutPut(bt->rchild,k);if(bt-<data>=k)printf("%d",bt->data);if(bt->lchild!=null)OutPut(bt->lchild,k); }

編寫一個遞歸算法，在一棵有n個結點的隨機建立起來的二叉排序樹中查找第k（1≤k≤n）小的元素，并返回指向該結點的指針，要求算法的平均時間復雜度為O（logaN）a為2.二叉排序樹中的每個結點除data，lchild，rchild等數據成員外，增加一個count成員，保存以該結點為根的子樹上的結點個數

算法思想：
設二叉排序樹的根節點為*t，根據結點的存儲的信息，有一下幾種樹的情況
★⑴若t->lchild為空
①t->rchild非空且k==1，則*t為第k小的元素
②t->rchild非空且K!=1，則第K小的元素在*t的右子樹
★⑵若t->lchild非空
①t->lchild->count==k-1，則*t為第K小的元素
②t->lchild->count>k-1，則第k小的元素必在*t的左子樹，繼續在*t的左子樹中查找
③t->lchild->count

BSTNode *search_Small(BSTNode *t,int k) {if(k<1||k>t->data)return NULL;if(t->lchild==null){if(k==1)return 1;elsereturn search_Small(t->rchild,k-1);}else{if(t->lchild->count==k-1)return t;if(t->lchild->count>k-1)return search_Small(t->lchild,k);if(t->lchild->count<k-1)return search-Small(t->lchild->count+1);} }

求二叉樹中以值為X的結點為根的子樹深度

int Get_Sub_Depth(BiTree T,int x) { if(T->data==x){printf("%d",Get_Depth(T));exit 1;}else{if(T->lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)GEt_Sub_Depth(T->rchild,x);} }int GetDepth(BiTree T) {if(T==null)return 0;else if(T->lchild==null&&T->rchild==null)retunr 1;else{int dep1=GetDepth(T->lchild);int dep2=GetDepth(T->rchild);if(dep1>dep2)return dep1+1;elsereturn dep2+1;} }

設計一棵平衡二叉樹的每個結點都標明了平衡因子bf，試設計一個算法，求平衡二叉樹的高度

int Heigh_bf(BiTree T) {levle=-;P=T;while(P){level++;if(p->bf<0)p=p->rchild;elsep=p->lchild;}return level; }

設二叉樹的結點結構為二叉平衡樹結點結構，設計一個遞歸算法計算并填寫二叉樹中每個結點的平衡因子，同時返回二叉樹中不平衡結點個數

int GetDepth(BiTree T); int Get_bf(BiTree T,int &count) { if(T){Get_bf(T->lchild);Get_bf(T->rchild);m=GetDepth(T->lchild);n=GetDepth(T->rchild);T->bf=m-n;if(T->bf>1||T->bf<-1)count++;} }int GetDepth(BiTree T) {if(T==null)return 0;else if(T->lchild==null&&T->rchild==null)retunr 1;else{int dep1=GetDepth(T->lchild);int dep2=GetDepth(T->rchild);if(dep1>dep2)return dep1+1;elsereturn dep2+1;} }

已知二叉樹的順序存儲結構建立二叉鏈表結構

bool CreatrBiTree_SqlList(BiTree &T,SqList sa) {BiTree ptr[sa.last+1]; 該數組存儲于sa中各結點對應的樹指針if(!sa.last){T=null;return true;}ptr[1]=(BTNode *)malloc(sizeof(BTNode));ptr[1]->data=sa.elem[1]; 建立樹根T=Ptr[1];for(i=2;i<=sa.last;i++){if(!sa.elem[i])return false;ptr[i]=(BTNode *)malloc(sizeof(BTNode));Ptr[i]->data=sa.elem[i];j=i/2; 找到結點的雙親if(i-j*2) i是j的右孩子ptr[j]->lchild=ptr[i];}return true; }

假設一個僅包含二元運算符的算術表達式以二叉鏈表形式存放于二叉樹T中，設計算法后序遍歷計算表達是的值

float PostValue(BiTree T) {float lv,rv;if(T){lv=PostValue(T->lchild);rv=PostValue(T->rchild);seitch(T->optr){case '+': value=lv+rv;break;case '-': value=lv-rv;break;case '*': value=lv*rv;break;case '/': value=lv/rv;break;}return value;} }

設計算法利用葉子結點中空指針域將所有葉子結點鏈接為一個帶頭指針的雙鏈表，算法返回頭結點的地址

void CreateLeafList（BiTree T） {if(T){CreateLeafList(T->lchild);if(!T->lchild&&!T->rchild)if(!L){L=(BiTree)malloc(sizeof(BNode));L->lchild=null;L->rchild=T;T->lchild=L;pre=T;}else{Pre->rchild=T;T->lchild=Pre;Pre=T;}CreateLeafList(T->rchild);Pre->rchild=null;} }

給出中序線索二叉樹的結點結構，試編寫不使用棧或遞歸的情況下，先序遍歷中序線索二叉樹的算法（帶頭結點）

void PreOrder_InThread(BiThrTree T) {P=T->lchild;while(P){while(p->ltag=0){printf(p->data);p=p->lchild;}printf(p->data);while(p->rtag==1&&p->rchild!=T)p=p->rchild;if(p->rchild!=T)p=p->rchild;} }

非遞歸不用棧中序遍歷帶有雙親指針的三叉鏈表的二叉樹

三叉鏈表二叉樹是另一種主要的鏈式存儲結構。三叉鏈表的主要區別在于，它的結點比二叉鏈表的結點多一個指針域，該域用于存儲指向本結點雙親指針

typedef struct {int data;PBTNode *lchild;PBTNode *rchild;PBTNode *parent; }PBTNode,*PBiTree;void InOrder Norecurive(PBiTree T) {P=T;while(P->lchild)p=p->lchild;while(p){visit(p);if(p->rchild){p=p->rchild;while(p->lchild)p=p->lchild;}else if(p->parent->lchild==p){p=p->parent;}else{p=p->parent;while(p->parent=&&p->parent->rchild==p)p=p->parent;p=p->parent;}} }

總結

以上是生活随笔為你收集整理的【考研】东北大学二叉树相关算法(2)的全部內容，希望文章能夠幫你解決所遇到的問題。

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