二叉排序树实现（C++封装）
浏览数：15 /
时间：2015年06月08日
设计思路
设计一个类，根结点只可读取，具备构造二叉树、插入结点、删除结点、查找、 查找最大值、查找最小值、查找指定结点的前驱和后继等功能接口。
二叉排序树概念
它或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树。
二叉排序树的各种操作
插入新节点
这是一个递归操作，递归设计时要找到最源头，才能得到最简设计。一种设计是判断叶子节点，把新节点作为叶子节点的孩子插入；一种是永远当作根进行插入，插入节点永远是当前子树的根！看代码：
//root为二级指针的原因是，如果树为空，需要将根修改反馈回来 bool BinaryTree::InsertNode(pNode * cuRoot, int data, pNode self) { //递归设计时找到最源头，才能得到最简设计 if (*cuRoot == nullptr){ pNode node = new Node; if (node == nullptr) return false; node->data = data; node->lChild = node->rChild = node->parent = nullptr; (*cuRoot) = node; node->parent = self; return true; } if (data > (*cuRoot)->data) InsertNode(&(*cuRoot)->rChild, data, *cuRoot); else InsertNode(&(*cuRoot)->lChild, data, *cuRoot); return true; }
构造函数
一共两个重载函数：一个无参，一个接受数组利用插入函数直接构造二叉排序树。
BinaryTree::BinaryTree(int * datum, int len) { root = nullptr; for (int i = 0; i < len; i++) InsertNode(&root, datum[i], root); } BinaryTree::BinaryTree() { root = nullptr; }
查找函数
这也是一个递归操作，为了对外隐藏root（根节点），因此编写了一个私有函数，进行真正的查找操作。
//真正的查找函数 BinaryTree::pNode BinaryTree::_searchKey(pNode root, int key){ if (root == nullptr) return nullptr; if (root->data == key) //找到了 return root; else if (root->data > key)//值偏小，到左子树找 return _searchKey(root->lChild, key); else //值偏大，到右子树找 return _searchKey(root->rChild, key); } //对外接口 BinaryTree::pNode BinaryTree::SearchKey(int key){ return _searchKey(root, key); }
找前驱节点
要么为左子树中最大者，要么一直追溯其父节点链，第一个是其父节点的右孩子的父节点，即为所求。
BinaryTree::pNode BinaryTree::SearchPredecessor(pNode node){ if (node == nullptr) return nullptr; else if (node->lChild != nullptr) return SearchMaxNode(node->lChild); else { if (node->parent == nullptr) return nullptr; while (node) { if (node->parent->rChild == node) break; node = node->parent; } return node->parent; } }
找后继节点
与找前驱节点基本相似。 要么为右子树中最小者，要么一直追溯其父节点链，第一个是其父节点的左孩子的父节点，即为所求。
BinaryTree::pNode BinaryTree::SearchSuccessor(pNode node){ if (node == nullptr) return nullptr; else if (node->rChild != nullptr) return SearchMinNode(node->rChild); else { if (node->parent == nullptr) return nullptr; while (node) { if (node->parent->lChild == node) break; node = node->parent; } return node->parent; } }
找最小值
BinaryTree::pNode BinaryTree::SearchMinNode(pNode curNode){ if (curNode == nullptr) return nullptr; //一直找到左子树为空的节点，即为最小值 while (curNode->lChild != nullptr) curNode = curNode->lChild; return curNode; }
找最大值
BinaryTree::pNode BinaryTree::SearchMaxNode(pNode curNode){ if (curNode == nullptr) return nullptr; //一直找到右子树为空的节点，即为最大值 while (curNode->rChild != nullptr) curNode = curNode->rChild; return curNode; }
中序遍历
void BinaryTree::_visitMiddle(pNode root){ if (root != nullptr){ _visitMiddle(root->lChild); printf("%d;", root->data); _visitMiddle(root->rChild); } } void BinaryTree::VisitMiddle(){ _visitMiddle(root); }
删除节点
这个是最麻烦的操作，分四种情况分别处理，最麻烦的是被删节点左右子树都存在的情况，这时将被删节点内容换成其后继内容，删除其后继（递归）。
bool BinaryTree::DeleteNode(int key){ //return _deleteNode(root, key); pNode node = SearchKey(key); if (!node) return false; //被删节点为叶子结点 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<stdio.h> #include<stdlib.h> 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 <conio.h> #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; }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
