从下往上开始计算每个结点的深度及平衡因子。
#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 typedef int Status; typedef struct Node { int data; int bf; int depth; struct Node *llink,*rlink; }Node,*Tree; Status SearchBST(Tree T,int key,Tree f,Tree *p); Status InsertBST(Tree *T,int e); int Factor_Depth_Make(Tree T); int main() { Tree T; T=(Tree)malloc(sizeof(Node)); T=NULL; int e; printf("What number you want to search--0 to quit:"); scanf("%d",&e); while(e) { if(!InsertBST(&T,e)) printf("Done!"); else printf("It`s been inserted for the first time."); printf("\nWhat number you want to search--0 to quit:"); scanf("%d",&e); } int h; h=0; h=Factor_Depth_Make(T); printf("树的高度为:%d.\n",h); return 0; } Status SearchBST(Tree T,int key,Tree f,Tree *p) { if(!T) { *p=f; return FALSE; } else if(key==T->data) { *p=T; return TRUE; } else if(key<T->data) { return SearchBST(T->llink,key,T,p); } else return SearchBST(T->rlink,key,T,p); } Status InsertBST(Tree *T,int e) { Tree p; p=(Tree)malloc(sizeof(Node)); if(!SearchBST(*T,e,NULL,&p)) { Tree s; s=(Tree)malloc(sizeof(Node)); s->data=e; s->llink=s->rlink=NULL; s->bf=0; s->depth=1; if(!p) (*T)=s; else if(e<p->data) p->llink=s; else p->rlink=s; return TRUE; } else return FALSE; } int Factor_Depth_Make(Tree T) { if(T) { int left,right; left=right=0; if(T->llink) left=Factor_Depth_Make(T->llink); if(T->rlink) right=Factor_Depth_Make(T->rlink); T->bf=left-right; T->depth+=(left>right?left:right); return T->depth; } }