二叉排序树Java实现plusC++完整测试代码
定义 对于BST中的任何一个非叶子节点,要求左子节点的值比当前结点的值要小,右子节点的值比当前结点大,且不存在相同的值
二叉排序树的创建
有用到递归的思想 若要插入结点的值小于当前结点的值,则在左子树中插入 若要插入结点的值大于当前结点的值,则在右子树中插入 核心代码
public void add(Node node
) {
if(node
==null
)return;
if(node
.data
<this.data
) {
if(this.left
==null
) {
this.left
=node
;
}else {
this.left
.add(node
);
}
}else {
if(this.right
==null
) {
this.right
=node
;
}else {
this.right
.add(node
);
}
}
}
中序遍历后结果为从小到大依次排列
BST的删除
删除要复杂一些,主要分为三类 ①若要删除结点为叶子结点 这种情况比较简单,直接置空就OK ②若要删除结点为带有一个子结点的结点 若要删除的结点有左子结点
判断该结点是父结点的左子结点还是右子结点 若为左子节点,则将父结点的左子结点指向该结点的左子结点
若为右子结点,则将父结点的右子结点指向该结点的左子结点
若要删除的结点有右子结点
判断该节点是父结点的左子节点还是右子结点 若为左子结点,则将父结点的左子结点指向该结点的右子结点
若为右子结点,则将父结点的右子结点指向该结点的右子结点
当然,在这个删除函数中,穿插了一些函数 比如 search 找到当前传进参数val所对应的Node; findParent 找到当前结点的父结点 ③若要删除结点为带有两个结点的结点
核心:找到该结点的右子树中最小值的结点or该结点的左子树中最大值的结点,将这个找到的值存进tmp中,并将tmp赋值给当前结点 附加函数 getRightMin 获取右子树中最小值结点 or getLeftMax 获取左子树中最大值结点 核心代码
public void deleNode(int val
) {
if(this.root
==null
)return;
else {
if(this.root
.data
==val
) {
this.root
=null
;
return;
}else {
Node target
=Search(val
);
if(target
==null
) {
System
.out
.println("Value not Found.");
}else {
Node parent
=findParent(val
);
if(target
.right
==null
&&target
.left
==null
) {
System
.out
.println("leaf node");
if(parent
.left
!=null
&&parent
.left
.data
==val
) {
parent
.left
=null
;
}
else{
parent
.right
=null
;
}
}
else if(target
.right
!=null
&&target
.left
!=null
) {
int minVal
=getRightMin(target
.right
);
target
.data
=minVal
;
}
else {
if(parent
.left
!=null
&&parent
.left
.data
==val
) {
if(target
.left
!=null
&&target
.left
.data
==val
) {
parent
.left
=target
.left
;
}
else if(target
.right
!=null
&&target
.right
.data
==val
) {
parent
.right
=target
.right
;
}
}
else if(parent
.right
!=null
&&parent
.right
.data
==val
) {
if(target
.left
!=null
&&target
.left
.data
==val
) {
parent
.right
=target
.right
;
}
else if(target
.right
!=null
&&target
.right
.data
==val
) {
parent
.right
=target
.right
;
}
}
}
}
}
}
}
最后
C++完整测试代码
#include<bits/stdc++.h>
using namespace std
;
class Node {
private:
int data
;
Node
* left
;
Node
* right
;
public:
Node(int d
= 0) {
data
= d
;
left
= NULL;
right
= NULL;
}
int getData()const {
return data
;
}
Node
* getLeft()const {
return left
;
}
Node
* getRight()const {
return right
;
}
void setLeft(Node
* left
) {
this->left
= left
;
}
void setData(int data
) {
this->data
= data
;
}
void setRight(Node
* right
) {
this->right
= right
;
}
void insertNode(Node
* node
) {
if (node
== NULL) {
return;
}
if (node
->data
< this->data
) {
if (this->left
== NULL) {
this->left
= node
;
}
else {
this->left
->insertNode(node
);
}
}
else {
if (this->right
== NULL) {
this->right
= node
;
}
else {
this->right
->insertNode(node
);
}
}
}
Node
* search(int val
) {
if (this == NULL)return NULL;
if (this->data
== val
)return this;
else if (this->data
> val
) {
return this->left
->search(val
);
}
else return this->right
->search(val
);
}
Node
* findParent(int val
) {
if ((this->left
&& this->left
->data
== val
) || (this->right
&& this->right
->data
== val
)) {
return this;
}
if (val
> this->data
) {
if (this->right
) {
return this->right
->findParent(val
);
}
else return NULL;
}
if (val
< this->data
) {
if (this->left
) {
return this->left
->findParent(val
);
}
else return NULL;
}
return NULL;
}
void infixOrder() {
if (this == NULL)return;
if (this->left
!=NULL) {
this->left
->infixOrder();
}
cout
<< this->data
<< " ";
if (this->right
!=NULL) {
this->right
->infixOrder();
}
}
};
class BST {
private:
Node
* root
;
public:
BST() { this->root
= NULL; }
void setRoot(Node
* root
) {
this->root
= root
;
}
void insertNode(Node
* node
) {
if (this->root
== NULL) {
this->root
= node
;
}
else {
this->root
->insertNode(node
);
}
}
Node
* search(int val
) {
if (root
== NULL)return NULL;
else return root
->search(val
);
}
Node
* findParent(int val
) {
if (root
== NULL)return NULL;
else return root
->findParent(val
);
}
int getRightMin(Node
* node
) {
if (node
== NULL)return 0;
Node
* tmp
= node
;
while (tmp
->getLeft()) {
tmp
= tmp
->getLeft();
}
int res
= tmp
->getData();
delete tmp
;
return res
;
}
int getLeftMax(Node
* node
) {
if (node
== NULL)return 0;
Node
* tmp
= node
;
while (tmp
->getRight()) {
tmp
= tmp
->getRight();
}
int res
= tmp
->getData();
delete tmp
;
return res
;
}
void deleNode(int val
) {
if (this == NULL)return;
if (val
== root
->getData()) {
root
= NULL;
return;
}
Node
* target
= search(val
);
if (target
== NULL) {
cout
<< "Value Not Found." << endl
;
return;
}
Node
* parent
= findParent(val
);
if (target
->getLeft() == NULL && target
->getRight() == NULL) {
if (parent
->getLeft() && parent
->getLeft()->getData() == val
) {
parent
->setLeft(NULL);
}
else if (parent
->getRight() && parent
->getRight()->getData() == val
) {
cout
<< "Already In" << endl
;
parent
->setRight(NULL);
}
}
else if (target
->getLeft() && target
->getRight()) {
int tmp
= getRightMin(target
);
target
->setData(tmp
);
}
else {
if (target
->getLeft()) {
if (parent
->getLeft() && parent
->getLeft()->getData() == val
) {
parent
->setLeft(target
->getLeft());
}
else if (parent
->getRight() && parent
->getRight()->getData() == val
) {
parent
->setRight(target
->getLeft());
}
}
else if (target
->getRight()) {
if (parent
->getLeft() && parent
->getLeft()->getData() == val
) {
parent
->setLeft(target
->getRight());
}
else if (parent
->getRight() && parent
->getRight()->getData() == val
) {
parent
->setRight(target
->getRight());
}
}
}
}
void infixOrder() {
if (this->root
== NULL)return;
this->root
->infixOrder();
}
};
int main() {
int arr
[] = { 7,3,10,12,5,1,9,2 };
BST bst
;
for (int i
= 0; i
< 8; i
++) {
bst
.insertNode(new Node(arr
[i
]));
}
bst
.infixOrder();
cout
<< endl
;
bst
.deleNode(12);
bst
.infixOrder();
return 0;
}
有看到一种写法 来源于一道题对于我这种代码的优化
BinTree
Insert(BinTree BST
, ElementType X
) {
if (BST
== NULL) {
BinTree add
=(BinTree
)malloc(sizeof(BinTree
));
add
->Data
=X
;
add
->Left
=add
->Right
=NULL;
BST
=add
;
return BST
;
}
if (X
< BST
->Data
)Insert(BST
->Left
, X
);
else Insert(BST
->Right
, X
);
return BST
;
}
BinTree
Delete(BinTree BST
, ElementType X
) {
if (!BST
) {
printf("Not Found\n");
return BST
;
}
else {
if (X
< BST
->Data
)BST
->Left
= Delete(BST
->Left
, X
);
else if (X
> BST
->Data
)BST
->Right
= Delete(BST
->Right
, X
);
else {
if (BST
->Left
&& BST
->Right
) {
BinTree t
= FindMin(BST
->Right
);
BST
->Data
= t
->Data
;
BST
->Right
= Delete(BST
->Right
, BST
->Data
);
}
else {
if (!BST
->Left
)BST
= BST
->Right
;
else if (!BST
->Right
)BST
= BST
->Left
;
}
}
}
return BST
;
}
Position
Find(BinTree BST
, ElementType X
) {
if (!BST
)return NULL;
if (X
== BST
->Data
)return BST
;
else if (X
> BST
->Data
)return Find(BST
->Right
, X
);
else return Find(BST
->Left
, X
);
}
Position
FindMin(BinTree BST
) {
if (!BST
)return NULL;
if (BST
->Left
)return FindMin(BST
->Left
);
else return BST
;
}
Position
FindMax(BinTree BST
) {
if (!BST
)return NULL;
if (BST
->Right
)return FindMax(BST
->Right
);
else return BST
;
}