上机8_查找

题目

假设一棵平衡二叉树的每个结点都标明了平衡因子b，试设计一个算法，利用平衡因子求平衡二叉树的高度。

实现代码

#include<iostream>
using namespace std;

typedef struct node{
   
    int data;
    int b;
    node *lchild,*rchild;
};
typedef node * AVLBtree;
int high = 0;
int depth(AVLBtree T)
{
   
    
    if(T==NULL)return 0;
    else{
   
        if(T->b>=0){
   
            high=depth(T->lchild);
            }
        if(T->b<0){
   
            high=depth(T->rchild);
            } 
    
    return high+1;
}
}

同学代码

#include<iostream>
using namespace std;
struct Tree {
   
	Tree* right;
	Tree* left;
	int b;
};
int getHeight(Tree* T) {
   
	int i = 1;
	while (T != NULL) {
   
		if (T->b >= 0) {
   
			T = T->right;
		}
		else {
   
			T = T->left;
		}
		i++;
	}
	return i;
}
int main() {
   
	Tree* head = new Tree();
	Tree* son1 = new Tree();
	Tree* son2 = new Tree();
	Tree* son3 = new Tree();
	Tree* son4 = new Tree();
	Tree* son5 = new Tree();
	Tree* son6 = new Tree();
	Tree* son7 = new Tree();
	Tree* son8 = new Tree();
	head->b = -1;
	head->left = son1;
	head->right = son2;
	son1->b = 0;
	son1->left = son3;
	son1->right = son4;
	son2->b = 1;
	son2->left = son5;
	son2->right = son6;
	son3->b = 0;
	son3->left = NULL;
	son3->right = NULL;
	son4->b = 0;
	son4->left = NULL;
	son4->right = NULL;
	son5->b = 0;
	son5->left = son7;
	son5->right = son8;
	son6->b = 0;
	son6->left = NULL;
	son6->right = NULL;
	son7->b = 0;
	son7->left = NULL;
	son7->right = NULL;
	son8->b = 0;
	son8->left = NULL;
	son8->right = NULL;
	cout << "这棵平衡二叉树的高度为:" << getHeight(head) << endl;
}

示例二

#include <iostream>
using namespace std;
struct AVLNode
{
   
    int b, data;
    AVLNode* lChild, * rChild;
    AVLNode(int a)
    {
   
        data = a;
        lChild = NULL;
        rChild = NULL;
    }
};
typedef struct AVLTree
{
   
    AVLNode* root = NULL;
};

int Height(AVLNode* p)
{
   
    if (!p)
        return 0;
    return (p->b > 0 ? Height(p->lChild) : Height(p->rChild)) + 1;
}

int BalanceFactor(AVLNode* p)  // 返回平衡因子
{
   
    int ret = Height(p->lChild) - Height(p->rChild);
    p->b = ret;
    return ret;
}

AVLNode* LL_Rotation(AVLNode* subRoot)  // LL 旋转
{
   
    AVLNode* temp = subRoot->lChild;
    subRoot->lChild = temp->rChild;
    temp->rChild = subRoot;
    return temp;
}

AVLNode* RR_Rotation(AVLNode* subRoot)  // RR 旋转
{
   
    AVLNode* temp = subRoot->rChild;
    subRoot->rChild = temp->lChild;
    temp->lChild = subRoot;
    return temp;
}

AVLNode* LR_Rotation(AVLNode* subRoot)  // LR 旋转
{
   
    subRoot->lChild = RR_Rotation(subRoot->lChild);
    return LL_Rotation(subRoot);
}

AVLNode* RL_Rotation(AVLNode* subRoot)  // RL 旋转
{
   
    subRoot->rChild = LL_Rotation(subRoot->rChild);
    return RR_Rotation(subRoot);
}


AVLNode* Balancee(AVLNode* subRoot)  // 进行平衡操作
{
   
    int bf = BalanceFactor(subRoot);
    if (bf > 1)  // 左子树更高
    {
   
        if (BalanceFactor(subRoot->lChild) > 0)
        {
   
            subRoot = LL_Rotation(subRoot);
        }
        else
        {
   
            subRoot = LR_Rotation(subRoot);
        }
    }
    else if (bf < -1) //右子树更高
    {
   
        if (BalanceFactor(subRoot->rChild) > 0)
        {
   
            subRoot = RL_Rotation(subRoot);
        }
        else
        {
   
            subRoot = RR_Rotation(subRoot);
        }
    }
    return subRoot;
}

void Insert(AVLNode*& subRoot, int x)
{
   
    if (subRoot == NULL)
    {
   
        subRoot = new AVLNode(x);
    }
    else if (x > subRoot->data)
    {
   
        Insert(subRoot->rChild, x);
        subRoot = Balancee(subRoot);
    }
    else if (x < subRoot->data)
    {
   
        Insert(subRoot->lChild, x);
        subRoot = Balancee(subRoot);
    }
    BalanceFactor(subRoot);
}

int main()
{
   
    AVLTree tree{
   };
    Insert(tree.root, 16);
    Insert(tree.root, 3);
    Insert(tree.root, 7);
    Insert(tree.root, 11);
    Insert(tree.root, 9);
    Insert(tree.root, 26);
    Insert(tree.root, 18);
    Insert(tree.root, 14);
    Insert(tree.root, 15);
    cout << Height(tree.root);
}