【C语言数据结构】树之二叉搜索树

• 前言
• 一、二叉搜索树

从二分查找的顺序与二分搜索树（判定树）比较可以看出：
1、每次的mid取值相当于搜索树每个节点。
2、每个值的查找次数相当于该值在搜索书所在节点的层数。
3、查找成功时查找次数不会超过判断数的深度[logn] +1。
4、平均查找次数 = 累加(层节点数 * 层数) / 总节点数 = ASL。

#include 
#include 
#include 

typedef char TreeElem;
typedef TreeElem ElemType;

typedef struct BSTNode{
	TreeElem data;
	struct BSTNode * lchild;
	struct BSTNode * rchild;
}BSTNode, *BiTree;

BSTNode * BST_Search(BiTree T, ElemType key); // 二插排序树的查找
int BST_Insert(BiTree &T, ElemType key); // 二插排序树的插入 
void Create_BST(BiTree &T, ElemType str[], int n); // 二插排序树的构建 
void PreOrder(BiTree T); // 先序遍历
void InOrder(BiTree T); // 中序遍历
void PostOrder(BiTree T); // 后续遍历
void visit(BiTree T); // 访问树的节点 

void visit(BiTree T) {
	printf("%c ", T->data);
}

// 根左右。 
void PreOrder(BiTree T) {
	if (T != NULL) {
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

// 左根右边 
void InOrder(BiTree T) {
	if (T != NULL) {
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}

// 左右根 
void PostOrder(BiTree T) {
	if (T != NULL) {
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}
 
BSTNode * BST_search(BiTree T, ElemType key) {
	while(T != NULL && key != T->data) {
		if (key < T->data) T = T->lchild;
		else T = T->rchild;
	}
	return T;
}

int BST_Insert(BiTree &T, ElemType key) {
	if (T == NULL) {
		T = (BiTree)malloc(sizeof(BSTNode));
		T->data = key;
		T->lchild = T->rchild = NULL;
		return 1; // 插入成功 
	} else if(T->data == key) {
		return 0;
	} else if(T->data < key) {
		return BST_Insert(T->rchild, key);
	} else {
		return BST_Insert(T->lchild, key);
	}
}

void Create_BST(BiTree &T, ElemType str[], int n) {
	T == NULL;
	int i = 0;
	while (i < n) {
		BST_Insert(T, str[i]);
		i++;
	}
}

int main() {
	BiTree T = NULL, result;
	char str[10] = {'5', '3', '7', '2', '4', '6','8', ''};
	Create_BST(T, str, strlen(str));
	printf("先序遍历："); 
	PreOrder(T);
	putchar('n'); 
	printf("中序遍历：");
	InOrder(T);  // 中序输出就是有顺序的字符串
	putchar('n'); 
	printf("后序遍历：");
	PostOrder(T);  // 中序输出就是有顺序的字符串
	putchar('n'); 
	return 0;
}