推荐星级:
  • 1
  • 2
  • 3
  • 4
  • 5

二叉搜索树的中序遍历与应用.docx

更新时间:2026-10-16 13:11:21 大小:38K 上传用户:潇潇江南查看TA发布的资源 标签:二叉搜索树中序遍历递增有序验证BST第k小元素 下载积分:2分 评价赚积分 (如何评价?) 打赏 收藏 评论(0) 举报

资料介绍

二叉搜索树的中序遍历与应用

一、中序遍历的性质

二叉搜索树(BST)的中序遍历结果一定是递增有序序列。这是BST最重要的性质之一。

// BST
       5
      / \
     3   8
    / \ / \
   2  4 6  9

中序遍历:2 3 4 5 6 8 9(递增有序)

应用:中序遍历是验证BST正确性、实现BST的迭代器、求第k小元素的基础。

二、验证BST

2.1 利用中序遍历有序

int *inorderList;
int count;

void inorderCollect(TreeNode *root) {
    if (root == NULL) return;
    inorderCollect(root->left);
    inorderList[count++] = root->val;
    inorderCollect(root->right);
}

int isValidBST(TreeNode *root) {
    inorderList = (int *)malloc(10005 * sizeof(int));


部分文件列表

文件名 大小
二叉搜索树的中序遍历与应用.docx 38K

全部评论(0)

暂无评论

上传资源 上传优质资源有赏金

  • 打赏
  • 30日榜单

推荐下载