1…什么是二叉搜索树

二叉搜索树就是左子树所有结点都小于根结点，右子树所有结点都打于根节点。当然这个定义递归的，它的左右子树也满足这个特点 例如：

2. 定义结构

typedef int BSTDataType; //定义二叉搜索树结点类型 typedef struct BSTreeNode { BSTDataType _data; struct BSTreeNode* _left; struct BSTreeNode* _right; }BSTreeNode

3. 在搜索二叉树中插入节点

思路：遇到插入结点这种题目，就大致分为两个步骤。

1.找到合适的插入位置 2.修改指针指向，将给定结点插入 那么在一棵二叉搜索树中要怎么找到合适的插入位置呢？其实也很简单，就是根据二叉搜索树的性质，既二叉搜索树的根节点大于二叉树左子树中的所有结点，小于右子树中的所有结点。将给定值按照这个性质和根节点比较，确定左右子树，在左右子树里继续查找插入的位置，当这个位置为空时，它的前面那个结点必然是它的母亲。

//创建一个新的二叉搜索树结点 BSTreeNode* BuyBSTreeNode(BSTDataType x) { BSTreeNode* ret = (BSTreeNode*)malloc(sizeof(BSTreeNode)); if (ret != NULL) { ret->_data = x; ret->_left = NULL; ret->_right = NULL; } else { perror("use malloc"); } return ret; } //插入结点 int BSTreeInsert(BSTreeNode** root, BSTDataType x) { assert(root); BSTreeNode* cur = *root; BSTreeNode* parent = NULL;//记录要插入位置的母亲 //当二叉搜索树没有结点时，必须要改变指针的指向，让它指向第一个结点，所有要传地址(二级指针) //插入成功返回1 if (*root == NULL) { *root = BuyBSTreeNode(x); return 1; } else//二叉搜索树中有结点 { //1.寻找插入位置 while (cur != NULL) { if (cur->_data > x) { parent = cur; cur = cur->_left; } else if (cur->_data < x) { parent = cur; cur = cur->_right; } else { //如果二叉搜索树中有和要插入结点一样的数据，则插入失败，返回0 return 0; } } //parent为插入结点的母亲，比较确定插入位置在左还是右最后插入 if (parent->_data > x) { parent->_left = BuyBSTreeNode(x); return 1; } else { parent->_right = BuyBSTreeNode(x); return 1; } } }

4. 在二叉搜索树中查找一个结点

思路：根据二叉搜索树根节点大于左子树结点，但是小于右子树结点的特点，和给定值比较，如果根结点的值小于给定值，必然在右子树，然后在在右子树里继续比较查找；如果根结点的值大于给定值，必然在左子树中，然后在左子树里继续比较查找。

//查找一个结点 //根据二叉搜索树的特点，左树都小于根节点，右树都大于根节点的特点和已知值相比遍历二叉搜索树来查找 //这里直接给一级指针也可以，为了和上边操作统一才弄得二级指针 BSTreeNode* BSTreeFind(BSTreeNode** root, BSTDataType x) { assert(root); BSTreeNode* cur = *root; while (cur) { //x大于当前结点，必然在右树 if (cur->_data < x) { cur = cur->_right; } //x小于当前结点，必然在左树 else if (cur->_data>x) { cur = cur->_left; } else { //相等则返回它的指针 return cur; } } //遍历结束则没有找到，返回NULL return NULL; }

5. 中序遍历二叉搜索树(遍历出来的序列递增，方便测试)

思路：递归遍历，先递归遍历左子树，在访问根结点，最后递归遍历右子树。

//中序遍历二叉搜索树(递归) void BSTreeInOrder(BSTreeNode** root) { assert(root); //根为空，直接返回 if ((*root) == NULL) { return; } //递归遍历左子树 BSTreeInOrder(&(*root)->_left); //访问根结点 printf("%d ", (*root)->_data); //递归遍历右子树 BSTreeInOrder(&(*root)->_right); }

6. 二叉搜索树的第K大节点

思路：二叉搜索树中序遍历的结果是递增序列。中序遍历的逆序的第k个元素就是本题的解。 中序遍历的逆序遍历方法： 每个节点都先访问右子树，再访问左子树。 按这种方法，最先访问的一定是第1大的节点。 第k个访问的一定是第k大的节点。 因此，每访问一个节点，k减一。 当k==1时，就是第k大的节点。 当k<=0时，就不再访问节点及其子树。

class Solution { public: //方法1 递归 int res=0; int n=0; int kthLargest(TreeNode* root, int k) { dfs(root,k); return res; } void dfs(TreeNode* root,int k){ if(root==NULL)return ; if(root->right)dfs(root->right,k); n++; if(n==k)res=root->val; if(root->left)dfs(root->left,k); return ; } };