#基于C实现数据结构之二叉排序树
###树表查找
树表查找是对树形存储结构所做的查找。树形存储结构是一种多链表，表中每个节点包含有一个数据域和多个指针域。每个指针指向一个后继节点，树形存储结构和树形结构时完全对应的，都表示一个树形图，只是用存储结构中的链指针代替逻辑结构中的抽象指针罢了，因此，往往把树形存储结构和树形逻辑结构统称为树结构或树。
BinTree* InsertBST(BinTree* T,BinTree* S) {
BinTree* f = NULL, *p = T;
while (p) {
f = p;
if (S->key < p->key)p = p->leftNode;
else p = p->rightNode;
}
if (T == NULL)T = S;
else if (S->key < f->key)
f->leftNode = S;
else f->rightNode = S;
return T;
}
void CreateBST() {
for (int i = 0; i < 10; i++) {
BinTree* S = (BinTree*)malloc(sizeof(BinTree));
S->key = arr[i];
S->leftNode = S->rightNode = NULL;
BSTree = InsertBST(BSTree, S);
}
}
###平衡二叉树的查找
BinTree* SearchBST(BinTree* T,int data) {
if (T == NULL || T->key == data) { return T; }
else if (data < T->key) { SearchBST(T->leftNode, data); }
else SearchBST(T->rightNode, data);
}
###二叉排序树的删除要满足删除节点后的二叉树仍是平衡二叉树。
-
- 若P时叶子节点，则直接删除。
- 若p只有一棵子树，则直接用子树替代原来的节点
- 既有左子树又有右子树，则用P的前驱节点来替换原节点，或后继节点替换原节点。
##二叉排序树完整代码
#include <iostream>
using namespace std;
int arr[10] = { 11,20,39,48,9,7,5,49,1,44 };
struct BinTree {
int key;
BinTree* leftNode;
BinTree* rightNode;
};
BinTree* BSTree = NULL;
BinTree* InsertBST(BinTree* T,BinTree* S) {
BinTree* f = NULL, *p = T;
while (p) {
f = p;
if (S->key < p->key)p = p->leftNode;
else p = p->rightNode;
}
if (T == NULL)T = S;
else if (S->key < f->key)
f->leftNode = S;
else f->rightNode = S;
return T;
}
void CreateBST() {
for (int i = 0; i < 10; i++) {
BinTree* S = (BinTree*)malloc(sizeof(BinTree));
S->key = arr[i];
S->leftNode = S->rightNode = NULL;
BSTree = InsertBST(BSTree, S);
}
}
BinTree* SearchBST(BinTree* T,int data) {
if (T == NULL || T->key == data) { return T; }
else if (data < T->key) { SearchBST(T->leftNode, data); }
else SearchBST(T->rightNode, data);
}
void Mid_Print(BinTree* Head) {
if (Head->leftNode != NULL)Mid_Print(Head->leftNode);
if (Head!=NULL)printf("%d\t", Head->key);
if (Head->rightNode != NULL)Mid_Print(Head->rightNode);
}
int main()
{
BinTree** one = &BSTree;
CreateBST();
Mid_Print(*one);
BinTree* two = SearchBST(*one, 1);
printf("%d", two->key);
return 0;
}
