球平衡二叉树高函数int height(Node* root);

5.已知平衡二叉树节点的定义为

Struct Node{double value_; Node* lc_; Node* rc_;int bf_;}

其中bf_为节点的平衡因子（左子高减去右子高）。完成下面算法，它求平衡二叉树的高度。

int height(Node* root);

要求其复杂度为O（㏒n），其中n为二叉树节点的个数。

/*****************************************************************************/

/*===================================================================*/

/*****************************************************************************/

#include<iostream>

using namespace std;

 

#define SIZE 6

struct Node{

       double value_;

       Node* lc_;

       Node* rc_;

       int bf_;

};

 

int height(Node* root)                        //题目中要求设计的函数；

{

       int floor=0;

       while(root->lc_!=NULL||root->rc_!=NULL){

              floor++;

              if(root->bf_>=0){

                     root=root->lc_;

              }

              else{

                     root=root->rc_;

              }

       }

       return floor+1;

}

 

 

int main()

{

       int hight=0;

       Node tree[SIZE];

 

       for(int i=0;i<SIZE;i++){                   //构造二叉树；

              tree[SIZE].value_=i;

       }

       tree[0].bf_=1;   tree[1].bf_=0;

       tree[2].bf_=1;   tree[3].bf_=0;

       tree[4].bf_=0;   tree[5].bf_=0;

       tree[0].lc_=&(tree[1]);

       tree[0].rc_=&(tree[2]);

       tree[1].lc_=&(tree[3]);

       tree[1].rc_=&(tree[4]);

       tree[2].lc_=&(tree[5]);

       tree[2].rc_=NULL;

       tree[3].lc_=NULL;

       tree[3].rc_=NULL;

       tree[4].lc_=NULL;

       tree[4].rc_=NULL;

       tree[5].lc_=NULL;

       tree[5].rc_=NULL;

 

    hight=height(tree);                         //题中函数的运用； 

       cout<<"默认二叉树的高度为："<<hight<<endl<<endl;

    system("pause");

       return 0;

}

 

 程序中构造的二叉树如下：

/*****************************************************************************/

/*===================================================================*/

/*****************************************************************************/