二叉排序树BST

二叉排序树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; // int maxVal=getLeftMax(target.left); // target.data=maxVal; } 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); // situation 1 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); } } // situation 3 else if (target->getLeft() && target->getRight()) { int tmp = getRightMin(target); target->setData(tmp); } // situation 2 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; }