数据结构-BST树

二叉查找树：BST树（Binary Search Tree），二叉查找树的结点是有键值key的；左子树的结点的键值key要小于左子树的根结点的键值key，右子树的结点的键值key要大于右子树的根结点的键值key，左子树和右子树也分别是二叉查找树，二叉查找树的结点的键值key是不重复的。
1.结构体

typedef int DataType_t;
typedef struct BSTreeNode
{DataType_t  		 data; 		//节点的键值struct BSTreeNode	*lchild; 	//左子树的指针域struct BSTreeNode	*rchild; 	//右子树的指针域}BSTnode_t;

2.新建一颗BST树

BSTnode_t* CreateBtree_Node(DataType_t value)
{BSTnode_t* root = (BSTnode_t*)malloc(sizeof(BSTnode_t));if(root == NULL){printf("内存分配失败\n");exit(-1);}root->lchild = NULL;root->rchild = NULL;root->data = value;return root;
}

3.插入新的键值

• 利用循环插入

bool EnBstTree(BSTnode_t *root,DataType_t value)
{BSTnode_t* newNode = CreateBtree_Node(value);if(newNode == NULL){return false;}BSTnode_t* current = root;while (current){if(value == current->data){printf("BST树中已存在值为%d的节点，无法插入重复节点\n", value);free(newNode);return false;}if(value < current->data){    //新键值小于根节点进入左子树if(current->lchild == NULL){current->lchild = newNode;return true;}current = current->lchild;}else{                        //新键值大于根节点进入右子树if(current->rchild == NULL){current->rchild = newNode;return true;}current = current->rchild;}}return true;
}

• 利用递归插入

BSTnode_t* En_BstTree(BSTnode_t *root,DataType_t value)
{if(root == NULL){return CreateBtree_Node(value);}if(root->data > value){           //相等的情况不做处理root->lchild=En_BstTree(root->lchild,value);}else{root->rchild=En_BstTree(root->rchild,value);}return root; //让插入动作只发生在那个空指针位置，其它部分保持原状
}

4.遍历BST树

• 前序遍历

bool PreOrder(BSTnode_t* root) //根左右
{if(root ==NULL){return false;}printf("%d ",root->data);PreOrder(root->lchild);PreOrder(root->rchild);return true;
}

• 中序遍历

bool InOrder(BSTnode_t* root) //左根右
{if(root ==NULL){return false;}InOrder(root->lchild);printf("%d ",root->data);InOrder(root->rchild);return true;
}

• 后序遍历

bool PostOrder(BSTnode_t* root) //左右根
{if(root ==NULL){return true;}PostOrder(root->lchild);PostOrder(root->rchild);printf("%d ",root->data);return true;
}