为叶子结点
? ? if (node->lChild == nullptr && node->rChild == nullptr){
? ? ? ? if (node->parent == nullptr){
? ? ? ? ? ? root = nullptr;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? if (node->parent->lChild == node)
? ? ? ? ? ? ? ? node->parent->lChild = nullptr;
? ? ? ? ? ? else
? ? ? ? ? ? ? ? node->parent->rChild = nullptr;
? ? ? ? }
? ? ? ? delete node;
? ? }
? ? //被删节点只有左子树
? ? else if (node->lChild != nullptr && node->rChild == nullptr){
? ? ? ? //将左孩子的父亲指向被删节点的父亲
? ? ? ? node->lChild->parent = node->parent;
? ? ? ? //被删节点为根，修改根节点
? ? ? ? if (node->parent == nullptr)
? ? ? ? ? ? root = node->lChild;
? ? ? ? else if(node->parent->lChild == node)
? ? ? ? ? ? node->parent->lChild = node->lChild;
? ? ? ? else
? ? ? ? ? ? node->parent->rChild = node->lChild;
? ? ? ? delete node;
? ? }
? ? //被删节点只有右子树
? ? else if (node->lChild == nullptr && node->rChild != nullptr){
? ? ? ? //将右孩子的父亲指向被删节点的父亲
? ? ? ? node->rChild->parent = node->parent;
? ? ? ? //被删节点为根，修改根节点
? ? ? ? if (node->parent == nullptr)
? ? ? ? ? ? root = node->rChild;
? ? ? ? else if (node->parent->lChild == node)
? ? ? ? ? ? node->parent->lChild = node->rChild;
? ? ? ? else
? ? ? ? ? ? node->parent->rChild = node->rChild;
? ? ? ? delete node;
? ? }
? ? //被删节点左、右子树都有
? ? else {? //用后继节点取代删除节点，并删除后继
? ? ? ? pNode successor = SearchSuccessor(node);
? ? ? ? int temp = successor->data;
? ? ? ? DeleteNode(temp);
? ? ? ? node->data = temp;
? ? }
}
?
柝构函数
函数超出作用域范围时，清理占用内存。
?
BinaryTree::~BinaryTree()
{
? ? _delAllNode(root);
}
void BinaryTree::_delAllNode(pNode root){
? ? if (root != nullptr && root!=NULL){
? ? ? ? _delAllNode(root->lChild);
? ? ? ? _delAllNode(root->rChild);? ? ?
? ? ? ? DeleteNode(root->data);
? ? }
}
?
类的定义（头文件）
?
#pragma once
#include?
#include
class BinaryTree
{
private:
? ? typedef struct Node{
? ? ? ? struct Node * parent;
? ? ? ? struct Node * lChild;
? ? ? ? struct Node * rChild;
? ? ? ? int data;
? ? }*pNode;
? ? pNode root;
? ? void _visitMiddle(pNode root);
? ? pNode _searchKey(pNode root, int key);
? ? void _delAllNode(pNode root);
public:
? ? BinaryTree();
? ? BinaryTree(int * datum, int len);
? ? pNode SearchMaxNode(pNode node);
? ? pNode SearchMinNode(pNode node);
? ? pNode GetRoot();
? ? pNode SearchKey(int key);
? ? bool DeleteNode(int key);
? ? pNode SearchPredecessor(pNode node);
? ? pNode SearchSuccessor(pNode node);
? ? void VisitMiddle();
? ? bool InsertNode(pNode * cuRoot, int data, pNode self);
? ? ~BinaryTree();
};
调用示例
#include
#include "BinaryTree.h"
int main()
{
? ? int arrs[] = { 23, 65, 12, 3, 8, 76,? 90, 21, 75, 34,345, 61 };
? ? int len = sizeof(arrs) / sizeof(arrs[0]);
? ? BinaryTree bTree(arrs,len);
? ? bTree.DeleteNode(90);
? ? bTree.VisitMiddle();
? ? getch();
? ? return 0;
}