二叉排序樹實現（C++封裝）

設計思路

設計一個類，根結點只可讀取，具備構造二叉樹、插入結點、刪除結點、查找、 查找最大值、查找最小值、查找指定結點的前驅和後繼等功能接口。

二叉排序樹概念

它或者是一棵空樹；或者是具有下列性質的二叉樹：
（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;
}

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm