二叉查找树的定义、构造及其遍历

定义

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
image.png

构造

假设我们要为数组 a[] = {10 ， 5 ， 15 ， 6 ， 4 ， 16 }构建一个二叉排序树，我们按顺序逐个插入元素
image.png
image.png

前驱节点val值小于该节点val值并且值最大的节点
后继节点val值大于该节点val值并且值最小的节点

遍历

查找指定元素的节点（While循环)：

  1. 判断当前结点是否为空指针，不是空指针进入
  3. key直接和当前结点value相等，return当前结点
  5. key大于当前结点value，将右子节点赋予当前结点
  7. key小于当前结点value，将左子节点赋予当前结点
  9. 直到key等于当前结点或者当前结点为空停止while循环
  1. // NOIP2013普及组初赛
  3. #include <iostream> 
  5. using namespace std; 
  7. const int SIZE = 100;
  8. const int INFINITE = 1000000;
  10. struct node{
  11.     int left_child, right_child, value;
  12. }a[SIZE];
  14. int is_bst( int root, int lower_bound, int upper_bound ){
  15.     int cur;
  16.     if (root == 0) return 1;
  18.     cur = a[root].value;
  19.     if ((cur > lower_bound) && (cur < upper_bound) && 
  20.         (is_bst(a[root].left_child, lower_bound, cur) == 1) && 
  21.         (is_bst(a[root].right_child, cur, upper_bound) == 1) )
  22.         return 1;
  24.     return 0;
  25. }
  27. int main()
  28. {
  29.     int i, n; 
  30.     cin >> n;
  31.     for (i = 1; i <= n; i++)
  32.         cin >> a[i].value >> a[i].left_child >> a[i].right_child;
  34.     cout << is_bst(1, -INFINITE, INFINITE) << endl;
  36.     return 0;
  37. }

例题

例题，FBI树(fbi)

  1. void dfs(int l, int r)
  2. {
  3.     //边界
  5.     //子问题
  6.     int len = (r - l) / 2;
  7.     dfs(l, l + len);
  8.     dfs(l + len + 1, r);
  10.     //按题意模拟操作
  11. }

例题，对称二叉树(tree_c)

  1. //思路1，从s[1]开始，两两为一单位，要么都是#，要么都不是#
  2. //思路2，根据左儿子和右儿子的位置，去判断左右儿子要么同时为#，要么同时不是#
  3. //两个思路，都需要在读入的字符串后面加上一个#，避免最后一个叶子结点没有兄弟的情况