一、二叉树节点
这里需要注意的是,如果以模板方法构造二叉树,推荐将内部节点类也声明一个模板,否则类外函数(声明在h文件,实现在cpp文件)的返回类型不能是Node*,使用模板后则可以使用BinaryTree\<elemTYpe>::Node\<elemType>*。
- 完整项目:pgExamBinaryTree
template<typename elemType>
class BinaryTree
{
private:
/* ===== Member 00 : 二叉树节点 ===== */
template<typename elemType>
class Node
{
public:
elemType element;
Node* left;
Node* right;
// 构造函数
Node(const elemType& p_ele, Node* p_lt, Node* p_rt)
: element(p_ele), left(p_lt), right(p_rt) { }
Node(elemType&& p_ele, Node* p_lt, Node* p_rt)
: element(p_ele), left(p_lt), right(p_rt) { }
};
/* ===== Member 01 : 根节点 ===== */
Node<elemType>* root;
}
二、查找
遍历在pgExam03中已经写过,这里不再赘述。
2.1 按值查找
template<typename elemType>
BinaryTree<elemType>::Node<elemType>* BinaryTree<elemType>::FindVal(const elemType& ele, Node<elemType>* node)
{
// 空节点
if (!node) return nullptr;
// 是当前节点
if (node->element == ele) return node;
// 查左子树
Node<elemType>* lt = nullptr;
lt = this->FindVal(ele, node->left);
if (lt) return lt;
// 查右子树
Node<elemType>* rt = nullptr;
rt = this->FindVal(ele, node->right);
if (rt) return rt;
// 无结果
return nullptr;
}
2.2 查找最值
/* ===== Function 08 : 查找最小值 ===== */
template<typename elemType>
BinaryTree<elemType>::Node<elemType>* BinaryTree<elemType>::FindMin(Node<elemType>* node)
{
if (!node) return nullptr;
if (!node->left) return node;
return FindMin(node->left);
}
/* ===== Function 09 : 查找最大值 ===== */
template<typename elemType>
BinaryTree<elemType>::Node<elemType>* BinaryTree<elemType>::FindMax(Node<elemType>* node)
{
if (!node) return nullptr;
if (!node->right) return node;
return FindMax(node->right);
}
三、插入与删除
3.1 插入
这里我们逐次比较,找到合适的位置就插入。
template<typename elemType>
void BinaryTree<elemType>::Insert(const elemType& ele, Node<elemType>*& node)
{
// 有空位插
if (!node)
{
node = new Node<elemType>(ele, nullptr, nullptr);
}
// 这个空位有人了,和他比较下,按一定排序准则选择左右,这里以 < 为排序准则。
else if (ele < node->element)
{
this->Insert(ele, node->left);
}
else if (node->element < ele)
{
this->Insert(ele, node->right);
}
}
3.2 删除
找到当前节点的大一值或小一值(中序遍历相邻的值)来替换这个节点
template<typename elemType>
void BinaryTree<elemType>::Remove_val(const elemType& ele, Node<elemType>*& node)
{
if (!node) return;
// 不是目标,比较
if (ele < node->element)
this->Remove_val(ele, node->left);
else if (ele > node->element)
this->Remove_val(ele, node->left);
// 找到目标
else if (node->left && node->right) // 被删除目标有两个节点
{
// 可替换左子树的最大值、右子树的最小值(中序向量的两个点,选一)
node->element = this->FindMin(node->right)->element;
// 更新删除目标
Remove_val(node->element, node->right);
}
else // 被删除目标只有一个节点或无节点
{
Node<elemType>* oldOne = node;
node = (node->left) ?
node->left :
node->right;
delete oldOne;
}
}
四、高度与宽度
4.1 高度
template<typename elemType>
int BinaryTree<elemType>::Height(Node<elemType>* node)
{
if (!node) return 0;
return std::max(this->Height(node->left), this->Height(node->right)) + 1;
}
4.2 宽度
宽度结合层次遍历来判断,完全二叉树的判断也用此种方法。
template<typename elemType>
int BinaryTree<elemType>::Width(Node<elemType>* node)
{
if (!node) return 0;
std::deque<Node<elemType>*> dq;
dq.push_back(node);
int maxWidth = 1;
int currentWidth = 1;
while (!dq.empty())
{
while (currentWidth > 0)
{
// 队首出队,将下一层压入队列
Node<elemType>* head = dq.front();
dq.pop_front();
if (head->left) dq.push_back(head->left);
if (head->right) dq.push_back(head->right);
currentWidth--;
}
// 下一层的节点数
currentWidth = dq.size();
maxWidth = (maxWidth < currentWidth) ?
currentWidth :
maxWidth;
}
return maxWidth;
}
五、完全、平衡与旋转
5.1 完全二叉树
template<typename elemType>
bool BinaryTree<elemType>::is_Complete(Node<elemType>* node)
{
if (!node) return false;
std::deque<Node<elemType>*> dq;
dq.push_back(node);
int currentWidth = 1;
int currentLevel = 0;
while (!dq.empty())
{
while (currentWidth > 0)
{
// 队首出队,将下一层压入队列
Node<elemType>* head = dq.front();
dq.pop_front();
if (head->left) dq.push_back(head->left);
if (head->right) dq.push_back(head->right);
currentWidth--;
}
// 下一层的节点数
currentWidth = dq.size();
currentLevel++;
if ((currentWidth != pow(2, currentLevel))&& (currentWidth != 0))
{
return false;
}
}
return true;
}
5.2 平衡二叉树
template<typename elemType>
bool BinaryTree<elemType>::is_Avl(Node<elemType>* node, int& height)
{
if (!node)
{
height = 0;
return true;
}
// left height
int lh(0);
// left flag
bool lf = this->is_Avl(node->left, lh);
// right
int rh(0);
bool rf = this->is_Avl(node->right, rh);
if (lf && rf && abs(lh - rh) <= 1)
{
height = std::max(lh, rh) + 1;
}
else
{
height = std::max(lh, rh) + 1;
return false;
}
return true;
}
5.3 旋转
template<typename elemType>
BinaryTree<elemType>::Node<elemType>* BinaryTree<elemType>::Mirror(Node<elemType>* node)
{
if (!node) return nullptr;
Node<elemType>* lt = this->Mirror(node->left);
Node<elemType>* rt = this->Mirror(node->right);
node->left = rt;
node->right = lt;
return node;
}
Comments | NOTHING