模板类二叉搜索树的高度修正function
问题遇到的现象和发生背景
我现在遇到一个问题是关于二叉搜索树的高度修正， 不是AVL就是正常的二叉搜索树。
问题是当插入、删除运行的时候，二叉搜索树的高度会发生变化(下图可看） 那么这个fix_height的意义就在于，如何在这些一系列操作完成之后，依然维持住树的正确高度。
问题相关代码，请勿粘贴截图
// This assumes that the subtrees rooted at node's children have // 这里假设根节点
// correct heights and then walks up the tree from node to the root
// correcting the heights.
// You can imlement this, or correct the heights another way
void fix_height(Node* node);
template <typename T>
int BST<T>:: getHieght(Node * node)
{
node = root_;
if(node==nullptr)
{
return 0;
}
else
{
return node->height;
// int left_height = getHieght(node->left);
// int right_height = getHieght(node->right);
// return max(left_height, right_height) + 1;
}
}
template <typename T>
void BST<T>:: fix_height(Node* node){
//int height = 0;
if(node==nullptr)
{
node->height=-1;
}
else if(node->left==nullptr && node->right==nullptr)
{
node->height=0;
}
else
{
node->height=max(getHieght(node->left),getHieght(node->right))+1;
}
运行结果及报错内容
运行结果就是Test没有通过，因为需要修正高度的function有插入，删除最小值，和右旋，这三个都没有过高度修正的测试
插入：a.out: unit_tests.hpp:101: void Tester::test_insert_heights(): Assertion `your_heights == real_heights' failed.
删除最小值：a.out: unit_tests.hpp:137: void Tester::test_delete_min_heights(): Assertion `your_heights == real_heights' failed.
右旋： a.out: unit_tests.hpp:342: void Tester::test_rotate_heights(): Assertion `your_heights == real_heights' failed.
删除 ：a.out: unit_tests.hpp:218: void Tester::test_erase_heights(): Assertion `your_heights == real_heights' failed.
我的解答思路和尝试过的方法
我试图通过不同的情况来更新node的高度，像是如果node是root那么高度就会是-1，当node是leaf node(也就是没有子嗣的node)的时候就设高度为0，但结果都是错误的
我想要达到的结果
希望有哪位能解决我这个问题，如果不会这个function也没问题，另一种方法则是在插入function最后自己更新高度，其他function也是同理，但该如何更新我也不清楚，所以只能跟着这个例子走。
template <typename T>
int BST<T>::update_height(Node* node){
if(node==nullptr)
{
return -1;
}
else if(node->left==nullptr && node->right==nullptr)
{
node->height=0;
return 0;
}
else
{
node->height=max(update_height(node->left),update_height(node->right))+1;
return node->height;
}
}
你看一下，是不是你要的二叉查找树的模板。采用的不是 AVL就是正常的二叉搜索树。
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
#include<iostream>
using namespace std;
template <typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree() :m_root(nullptr){}
BinarySearchTree(const BinarySearchTree &rhs)
{
m_root = clone(rhs.m_root);
}
~BinarySearchTree()
{
makeEmpty();
}
/**
* 找到树中的最小值，通过调用private的findMin实现递归
*/
const Comparable & findMin() const
{
return findMin(m_root)->element;
}
/**
* 找到树中的最大值，通过调用private的findMax实现递归
*/
const Comparable & findMax() const
{
return findMax(m_root)->element;
}
/**
* 当x找到时返回真，否则返回假
* 调用了private的那个同名函数，这个是为了递归实现
*（因为private中包含了一个BinaryNode的指针t）
*/
bool contains(const Comparable &x) const
{
return contains(x, m_root);
}
/**
* 判断树是否为空
*/
bool isEmpty() const
{
return m_root == nullptr;
}
/**
* 把树遍历一遍（中序,因为中序可以保证顺序输出）
*/
void printTree(ostream & out= cout) const
{
if (isEmpty())
out << "Empty tree!" << endl;
else
printTree(m_root, out);
}
/**
* 清空树
*/
void makeEmpty()
{
makeEmpty(m_root);
}
/**
* 把x插入树中，如果重复了就忽略
*/
void insert(const Comparable &x)
{
insert(x, m_root);
}
/**
* 把x从树中删除。如果x不在树中就什么都不做。
*/
void remove(const Comparable &x)
{
remove(x, m_root);
}
/**
* 深拷贝
*/
const BinarySearchTree & operator= (const BinarySearchTree &rhs)
{
if (this != &rhs)
{
BinaryNode *tmp = clone(rhs.m_root);
makeEmpty();
m_root = tmp;
}
return *this;
}
private:
struct BinaryNode{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(const Comparable &theElement,
BinaryNode *lt,
BinaryNode *rt)
: element(theElement), left(lt), right(rt) {}
};
BinaryNode *m_root;
/**
* 在树t中插入元素x，如果重复则什么也不做
*/
void insert(const Comparable &x, BinaryNode * &t) const
{
if (t == nullptr)
t = new BinaryNode(x, nullptr, nullptr);
else if (x < t->element)
insert(x, t->left);
else if (t->element < x)
insert(x, t->right);
else
; // 表示在树中找到了x，则什么也不做
}
/**
* 在树t中删除元素x
*/
void remove(const Comparable &x, BinaryNode * &t) const
{
if (t == nullptr)
return; // 没有找要删除的节点x
if (x < t->element)
remove(x, t->left);
else if (t->element < x)
remove(x, t->right);
else if (t->left != nullptr &&
t->right != nullptr)
{
t->element = findMin(t->right)->element;
remove(t->element, t->right);
}
else
{
BinaryNode * oldNode = t;
t = (t->left != nullptr) ? t->left : t->right;
delete oldNode;
}
}
/**
* 查找最小的元素, 通过递归的方法
*/
BinaryNode * findMin(BinaryNode *t) const
{
if (t == nullptr)
return nullptr;
if (t->left == nullptr)
return t;
return findMin(t->left);
}
/**
* 查找最大的元素, 通过循环的方法
*/
BinaryNode * findMax(BinaryNode *t) const
{
if (t != nullptr)
while (t->right != nullptr)
t = t->right;
return t;
}
/**
* 通过遍历的方法查找x是否在树（或子树）t中
*/
bool contains(const Comparable &x, BinaryNode * t) const
{
if (t == nullptr) // 遍历中未找到元素的中止条件
return false;
else if (x < t->element)
return contains(x, t->left);
else if (t->element < x)
return contains(x, t->right);
else // 如果 x 不大于 也 不小于t所指的节点中的元素，则x==t->element
return true;
}
/**
* 清空树
*/
void makeEmpty(BinaryNode * &t)
{
if (t != nullptr)
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = nullptr;
}
/**
* 打印子树
*/
void printTree(BinaryNode *t, ostream & out) const
{
if (nullptr != t)
{
printTree(t->left, out);
out << t->element << endl;
printTree(t->right, out);
}
}
/**
* 复制子树
*/
BinaryNode * clone(BinaryNode *t) const
{
if (t == nullptr)
return nullptr;
return new BinaryNode(t->element, clone(t->left), clone(t->right));
}
};
#endif
#include<iostream>
#include<random>
#include<ctime>
using namespace std;
#include"BinarySearchTree.h"
int main()
{
BinarySearchTree<int> t; // 创建一个二叉搜索树
uniform_int_distribution<unsigned int> u(0,200); // 设置随机数分布
default_random_engine e(time(0)); // 设置随机数引擎（通过时间作为种子）
cout << "==== 测试插入：" << endl;
for (size_t i = 0; i < 8; ++i)
{
t.insert(u(e));
}
cout << "==== 测试打印："<< endl;
t.printTree();
cout << "==== 测设删除（删除小于100的数）：" << endl;
for (size_t i = 0; i < 100; ++i)
{
t.remove(i);
}
t.printTree();
cout << "==== 测试拷贝构造函数：" << endl;
BinarySearchTree<int> t2(t);
t2.printTree();
cout << "==== 测试赋值操作：" << endl;
BinarySearchTree<int> t3;
t3 = t;
t.printTree();
cout << "==== 测试最大最小值：" << endl;
cout << "最大值：" << t.findMax() << endl;
cout << "最小值：" << t.findMin() << endl;
return 0;
}