考研数据结构与算法（六）树与二叉树

考研数据结构与算法（六）树与二叉树

一、树的概念和基础术语 1.1 定义

树是 n ( n > = 0 ) n ( n >= 0 ) n(n>=0) 个节点的有限集。当 n = 0 n = 0 n=0 时，称为空树。 在任意－非空树中应满足：

• ①有且仅有一个特定的称为根的结点
• ②当 n > 1 n > 1 n>1 时， 其余节点可分为 m ( m > 0 ) m (m > 0) m(m>0)个互不相交的 有限集 T 1 , T 2 , T 3 … … , T m T_1,T_2,T_3……,T_m T1​,T2​,T3​……,Tm​ ， 其中每个集合本身又是一颗树，并且称为根的子树。

显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。 树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

• 树的根结点没有前驱， 除根结点外的所有结点有且只有一个前驱
• 树中所有结点可以有零个或多个后继

从这个结构上来看的话，树是一个层级的结构，对于每一个非根节点而言，和上层只有一个结点关联，我们称这个上层结点为父节点 ，又由于根节点没有上层结点，那么我们会发现在 n n n 个结点的树有且仅有 n − 1 n-1 n−1 条边

1.2 基础术语

对于一颗这样的树而言：

• 考虑结点 K K K 。根 A A A 到结点 K K K 的唯一路径上的任意结点，称为结点 K K K 的 祖先。 如结点 B B B 是 结点 K K K 的祖先，而结点 K K K 是结点 B B B 的子孙。路径上最接近结点 K K K 的结点 E E E 称为 K K K 的双亲， 而 K K K 为结点 E E E 的孩子。根 A A A 是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点 K K K 和结点 L L L 有相同的双亲 E E E ， 即 K K K 和 L L L 为兄弟。
• 树中一个结点的孩子个数称为该结点的度， 树中结点的最大度数称为树的度。 如结点 B B B 的 度为 2 2 2 ，结点 D D D 的度为 3 3 3 ，树的度为 3 3 3 。
• 度大于 0 0 0 的结点称为 分支结点（又称非终端结点)； 度为 0 0 0 （没有子女结点）的结点称为 叶子结点（又称终端结点)。
• 结点的深度是从根结点开始自顶向下逐层累加的，结点的高度是从叶结点开始自底向上逐层累加的。树的高度（或深度）是树中结点的最大层数。 上图中树的高度为 4 4 4 。
• 有序树和无序树。树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树 。
• 路径和路径长度。 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成 ，而路径长度是路径上所经过的边的个数。（注意：由于树中的分支是有向的，即从1又亲指向孩子，所以树中的路径是从上向下的， 同一双亲的两个孩子之间不存在路径）
• 森林是 m ( m > = 0 ) m (m>=0) m(m>=0)棵互不相交的树的集合。 森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。

1.3 树的性质

• 树中的结点数等于所有结点的度数加一
• 度为 m m m 的树中第 i i i 层上至多有 m i − 1 m^{i-1} mi−1 个结点 ( i > = 1 ) (i>=1) (i>=1)
• 高度为 h h h 的 m m m 叉树至多有 ( m h − 1 ) / ( m 一 1 ) (m^h - 1 )/(m 一 1) (mh−1)/(m一1)个结点。
• 具有 n n n 个结点的 m m m 叉树的最小高度为 ⌈ l o g m ( n ( m − 1 ) + 1 ) ⌉ \left \lceil log_m(n(m-1)+1) \right \rceil ⌈logm​(n(m−1)+1)⌉

小结：这一部分的考点应该会着重于围绕树的性质，比如第一条，给你某些度的结点数和总结点数，问你叶子节点的个数，类似，以及围绕其他性质可以衍生处更多问题

二、二叉树 2.1 二叉树定义

每一个结点至多只有两棵子树（即度小于等于 2 2 2 ），并且二叉树是一颗有序树，其子树有左右之分 ，同样的，节点数为 0 0 0 的树为空树

二叉树的基本五种形态如下：

这里需要注意二叉树和度为 2 2 2 的树的区别：

• ①度为 2 2 2 的树至少有 3 3 3 个结点，而二叉树可以为空
• ②度为 2 2 2 的树没有左右次序的区分，而二叉树是一颗有序树有左右子树的区分

2.2 二叉树性质

在提性质前，先介绍两种特殊的二叉树：

2.2.1 满二叉树

简单理解一下，对于每一层的结点都塞满的树就是二叉树，比如说下图的就是高度为 2 、 3 2、3 2、3 的满二叉树

不难发现一个点，一颗深度为 k k k 且有 2 k − 1 2^k - 1 2k−1 个结点的二叉树为满二叉树

2.2.2 完全二叉树

对于一颗高度为 k   ( k > 1 ) k \ (k>1) k (k>1) 的二叉树其 k − 1 k-1 k−1 层是一颗满二叉树，并且第 k k k 层是按照从左到右依次插入的结点就为完全二叉树，很显然一颗满二叉树也是一颗完全二叉树，而一颗完全二叉树不一定是满二叉树，我们看几个完全二叉树的例子：

2.2.3 二叉排序树

递归定义：

• 左子树上所有结点的关键字均小于根结点的关键字；
• 右子树上的所有结点的关键宇均大于根结点的关键宇；
• 左子树和右子树又各是一棵二叉排序树。

2.2.4 平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过 1 1 1 的二叉树即为平衡二叉树

2.2.5 性质

• 非空二叉树上的叶子结点数等于度为 2 2 2 的结点数加 1 1 1, 即 n 0 = n 2 + 1 n_0 = n_2 + 1 n0​=n2​+1
• 非空二叉树上第 k k k 层上至多有 2 k − 1 2^{k-1} 2k−1 个结点
• 高度为 h h h 的二叉树至多有 2 n − 1 2^n - 1 2n−1 个结点
• 对于完全二叉树而言，如果根节点是从 1 1 1 开始计算的话，我们能得到一个有用的信息，即如果通过顺序存储二叉树，那么对于某一个分支节点假设为第 k k k 个元素，那么其左儿子结点位置为： 2 k 2k 2k 其右儿子结点位置为： 2 k + 1 2k+1 2k+1 的

2.3 二叉树存储结构 2.3.1 顺序存储

通过一组连续的地址进行存储每个结点（就是数组存储），我们按照从上到下，从左到右的次序依次将对应的结点放在对应的位置，显然根节点放在第一个位置（假设从 1 1 1 开始计算），那么他的左儿子就是第二个位置，右儿子就是第三个位置，那么是一颗完全二叉树的话，就可以直接使用顺序存储，通过结点的位置我们也能很快的定位到

2.3.2 链式存储

因为树的结构不确定，不一定会是完全二叉树那样，所以使用顺序存储可能会造成大量的空间浪费，比如最极端的情况就是二叉树退化成链，那么这个时候，每增加一层，都会浪费 2 i − 1 2^i - 1 2i−1 个空间，于是为了提高空间利用率，我们还可以通过链式存储二叉树的每个结点，对于每新增一个结点我们只需要申请对于的空间，然后将他的父结点指向它即可。

很显然就能得到这个链式的结点形式：

struct Node {
    ElemType data;
    struct Node *lchild,*rchild;
};

2.4 遍历二叉树

对于一个二叉树而言，是由三个部分组成：根结点（ N N N ），左子树（ L L L ），右子树（ R R R ），那么我们对这三部分的访问顺序进行变化就得到了最基础的三种序列访问方式，即先序遍历（ N L R NLR NLR ），中序遍历（ L N R LNR LNR ），后序遍历（ L R N LRN LRN ）

2.4.1 先序遍历

字面意思，遍历方式：

1. 遍历根节点
2. 遍历左子树
3. 遍历右子树

不难得出递归代码：

void PreOrder(Node *root) {
    if(root) {
        visit(root);//访问根节点
        PreOrder(root->lchild);//访问左子树
        PreOrder(root->rchild);//访问右子树
    }
}

2.4.2 中序遍历

字面意思，遍历方式：

1. 遍历左子树
2. 遍历根节点
3. 遍历右子树

不难得出递归代码：

void InOrder(Node *root) {
    if(root) {
        InOrder(root->lchild);//访问左子树
        visit(root);//访问根节点
        InOrder(root->rchild);//访问右子树
    }
}

2.4.3 后序遍历

字面意思，遍历方式：

1. 遍历左子树
2. 遍历右子树
3. 遍历根节点

不难得出递归代码：

void PostOrder(Node *root) {
    if(root) {
        PostOrder(root->lchild);//访问左子树
        PostOrder(root->rchild);//访问右子树
        visit(root);//访问根节点
    }
}

2.4.4 递归转非递归

假设有这样的一颗二叉树：

递归其实也就是利用了栈，我们分析用栈模拟的中序遍历的过程：

• ①沿着根的左孩子，依次入栈，直到左孩子为空，说明己找到可以输出的结点，此时栈内元素依次为 A 、 B 、 D A、B、D A、B、D
• ②栈顶元索出栈并访问：若其右孩子为空，继续执行操作②，若其右孩子不空，将右子树转执行操作①

以上面的二叉树为例，我们可以得到栈的空间使用过程如下：

操作次序栈内空间下一步进行的操作1NULL①2 A A A①3 A 、 B A、B A、B①4 A 、 B 、 D A、B、D A、B、D②5 A 、 B A、B A、B②6 A A A①7 A 、 E A、E A、E②8 A A A②9NULL①10 C C C②11NULL

模拟上述步骤即可得到非递归写法：

void InOrder_With_No_Deep(Node *root) {
    stack S;
    Node *p = root;
    while(p || !S.empty()) {
        if(p){
            S.push(p);
            p = p->lchild;
        } else {
            p = S.top();
            S.pop();
            visit(p);
            p = p->rchild;
        }
    }
}

先序遍历其实和中序遍历的递归方式是相似的，只需要将 visit() 函数放在前面即可，于是不难得到如下代码：

void PreOrder_With_No_Deep(Node *root) {
    stack S;
    Node *p = root;
    while(p || !S.empty()) {
        if(p){
            visit(p);
            S.push(p);
            p = p->lchild;
        } else {
            p = S.top();
            S.pop();
            p = p->rchild;
        }
    }
}

对于后序遍历的递归写法要麻烦得多，还是结合上面的二叉树图来分析

• ①沿着根的左孩子，依次入栈， 直到左孩子为空。 此时栈内元素依次为 A 、 B 、 D A 、B 、D A、B、D
• ②读取栈顶元素： 若其右孩子不空且未被访问过，将右子树转执行①；否则，栈顶元素出栈并访问。

接下来的时间线如下：

栈顶 D D D 的右孩子为空，出栈并访问 ，它是后序序列的第一个结点

栈顶 B B B 的右孩子不空且未被访问过， E E E 入栈

栈顶 E E E 的左右孩子均为空， 出栈并访问

栈顶 B B B 的右孩子不空但己被访问， B B B 出栈并访问

栈顶 A A A 的右孩子不为空且未被访问过， C C C 入栈

栈顶 C C C 的左右孩子均为空，出栈并访问

栈顶 A A A 的右孩子不空但己被访问， A A A 出栈并访问

由此得到后序序列 D E B C A DEBCA DEBCA

我们会发现和上面的先序、中序相比，多了一个是否被访问，这里只会发生在再次回到根节点，查看和右子树的关系的时候，也就是上一个访问的结点

所以我们可以有两种方式进行存储是否被访问

• 第一种使用哈希存储每一个被访问过的结点
• 第二种只需要记录上一个访问的结点

显然，第二种效率会更高，而且占用的资源更少，于是哦我们能得到如下代码：

void PostOrder_With_No_Deep(Node * root) {
    stack S;
    Node *p = root;
    Node *last = NULL;
    while(p | !S.empty()) {
        if(p) {//一直往左下走
           	S.push(p);
            p = p->lchild;
        } else {
            p = S.top();
            if(p->rchild && p->rchild != last) {
                p = rchild;//处理没访问过的右子树
            } else {
                visit(p);//访问结点
                last = p;//上一个访问的结点更新
                S.pop();//将当前访问的结点从栈中删除
                p = NULL;//重置P指针
            }
        }
    }
}

关于代码中第 17 17 17 行重置P指针：每次出栈访问完一个结点就相当于遍历完以该结点为根的子树

2.4.5 层序遍历

层序遍历依靠队列的数据结构，不断从上往下将结点加入队列，操作流程如下：

• ①将根节点加入队列
• ②将队首元素出队，并且将队首结点的左右儿子（结点不为空的话）加入队列
• ③重复①、②的操作直到队列为空

这个出队的序列就是我们层序遍历的结果

void Level_Order(Node *root) {
    queue que;
    que.push(root);
    while(!que.empty()) {
        Node *p = que.front();
        visit(p);
        que.pop();
        if(p->lchild) que.push(p->lchild);
        if(p->rchild) que.push(p->rchild);
    }
}

2.5 通过遍历序列构造二叉树

有的时候会给你两种不同遍历方式，然后让你构造出指定的二叉树

2.5.1 先序序列和中序序列构造二叉树

因为先序遍历的特点，序列中第一个元素一定是整个二叉树的根，那么我们在中序遍历中找到这个二叉树的根的位置，然后在中序遍历中二叉树的左边就是左子树，而右边就是右子树，然后我们在先序遍历中第二个位置就是左子树的根，于是我们在中序遍历中找到了左子树的根，然后由于我们知道了左子树大概占了多少位置，于是我们直接往后移动相同的位置就找了右子树的根，然后递归的重复上面的操作就能构建出整个二叉树的结构

参考例题：

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Solution ：

class Solution {
private:
    unordered_map index;

public:
    TreeNode* myBuildTree(const vector& preorder, const vector& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = index[preorder[preorder_root]];
        
        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    TreeNode* buildTree(vector& preorder, vector& inorder) {
        int n = preorder.size();
        // 构造哈希映射，帮助我们快速定位根节点
        for (int i = 0; i  in_right) {
            return nullptr;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];

        // 下标减一
        post_idx--;
        // 构造右子树
        root->right = helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left = helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size() - 1;

        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (auto& val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/cong-zhong-xu-yu-hou-xu-bian-li-xu-lie-gou-zao-14/

2.5.3 先序序列和后序序列构造二叉树

先序遍历和后序遍历在有的时候不能唯一的确定一颗二叉树，因为先序和后续没有明确的规定左右子树和根节点的关系，所以你可以说这是左子树，你也可以说这是右子树，所以通过这两种遍历方式进行构造的话，需要人为的拟定左右子树的分界点

参考例题：

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

三、线索二叉树 3.1 概念

前面的遍历二叉树让树形结构变成了链式结构，在链式结构中，对于出了第一个和最后一个结点外的其他结点而言，每一个结点都有一个前驱和后继，又由于我们之前提到，在一个 n n n 个结点的二叉树上有 n + 1 n+1 n+1 个空指针，那么我们通过这些空指针来存储链式结构中的前驱和后继的关系这就是线索二叉树，能加快查找结点的前驱和后继。

我们对之前定义的结点结构做出一点改变：

若结点有左子树，则其 l c h i l d lchild lchild 指向的是左儿子结点，否则 l c h i l d lchild lchild 指向的是其前驱结点，若结点有有儿子，则其 r c h i l d rchild rchild 指向的是其有儿子结点，否则指向的是其后继结点，为了避免混淆，我们新增两个标志域来区分，于是新的结点结构如下：

struct Node {
    ElemType data;
    struct Node *lchild, *rchild;
    int ltag,rtag;
};

3.2 中序线索二叉树构造

假设指针 pre 是上一次访问的结点，而指针 p 为当前访问的结点，即 pre 指针是 p 的前驱，在中序遍历过程中

• 检查 p 的左指针是否为空，若为空，则将 p 的左指针指向 pre
• 检查 pre 的右指针是否为空，若为空，则将 pre 的右指针指向 p

如下图所示：

于是得到递归代码：

void InThread(Node *p,Node *pre) {
    if(p) {
        InThread(p->lchild,p);
        if(!p->lchild) {//检查p指针
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre && pre->rchild == NULL) {//检查pre指针
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        InThread(p->rchild,pre);
    }
}

3.3 先序线索二叉树构造

假设给定如下二叉树：

先序序列为 A 、 B 、 C 、 D 、 F A、B 、C 、D 、F A、B、C、D、F，然后依次判断每个结点的左右链域， 如果为空则将其改造为线索。

• 结点 A 、 B A、 B A、B 均有左右孩子

• 结点 C C C 无左孩子，将左链域指向前驱 B B B ，无右孩子，将右链域指向后继 D D D

• 结点 D D D 无左孩子，将左链域指 向前驱 C C C，无右孩子，将右链域指向后继 F F F

• 结点 F F F 无左孩子，将左链域指向前驱 D， 无右孩子， 也无后继故置空

• 得到的先序线索二叉树如下图

如何在先序线索二叉树中找结点的后继？

• 如果有左孩子，则左孩子就是其后继
• 如果无左孩子但有右孩子，则右孩子就是其后继
• 如果为叶结点，则右链域直接指示了结点的后继。

3.4 后序线索二叉树构造

还是使用上面先序线索二叉树的图

后序序列 为 C D B F A CDBFA CDBFA

• 结点 A 、 B A、B A、B 都有左右儿子

• 结点 C C C 无左孩子，也无前驱故置空，无右孩子，将右链域指向后继 D

• 结点 D D D 无左孩子，将左链域指向前驱 C C C ，无右孩子，将右链域指向后继 B B B

• 结点 F F F 无左孩子，将左链域指向前驱 B B B ，无右孩子，将右链域指向后继 A A A

• 得到的后序线索二叉树如下图

如何在后序线索二叉树中找结点的后继？

在后序线索二叉树中找结点的后继较为复杂，可分 3 种情况：

• ①若结点 X X X 是二叉树的根， 则其后继为空
• ②若结点 X X X 是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点
• ③若结点 X X X 是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。

四、树和森林 4.1 树的存储结构 4.1.1 双亲表示法

使用一组连续的空间来存储每个结点，对于每一个结点除了要保存的元素值外还有一个 parent 伪指针指向该结点的父结点，结构如下图：

代码结构：

struct Node {
    ElemType data;
    int parent;
};

使用这个方式存储优点显然是方便找到每个元素的父结点，缺点就是要求一个结点的孩子结点的时候，需要遍历整个树形结构，这个存储方式其实就是我们后面的 并查集

4.1.2 孩子表示法

将每个结点的子节点用单链表链接起来，比如一个 n n n 个结点的树形结构就有 n n n 个单链表，很显然这种方式寻找子结点很容易，而寻找双亲的操作需要遍历 n n n 个结点中孩子链表指针域所指向的 n n n 个孩子链表，结构如下图：

4.1.3 孩子兄弟表示法

孩子兄弟表示法又称 二又树表示法 ，即以二叉链表作为树的存储结构。

孩子兄弟表示法使每个结点包括三部分内容： 结点值、 指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）

存储结构描述如下：

struct Node {
    ElemType data;
    struct Node *firstchild,*nextsibling;
};

4.2 树、森林与二叉树互相转换 4.2.1 树转化为二叉树

规则：每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟 ， 所以对应的二叉树没有右子树,，如下图所示

树转换成二叉树的画法：

• ①在兄弟结点之间加一连线
• ②对每个结点，只保留它与第一个 孩子的连线，而与其他孩子的连线全部抹掉
• ③以树根为轴心，顺时针旋转 45°

4.2.2 森林转化为二叉树

森林转化为二叉树和树转化二叉树类似

我们先将森林中每一颗树转化为二叉树

因为一颗从树转化为二叉树的根的右子树为空，所以我们把第一个二叉树的根当作整个森林的根，然后把第二颗二叉树的根当作第一颗树的右儿子，然后把第三颗二叉树的根当作第二颗的右儿子，然后以此类推，这样就将一个森林转化为一颗二叉树

森林转换成二叉树的画法：

• ①将森林中的每棵树转换成相应的二叉树
• ②每棵树的根也可视为兄弟关系，在每颗树的根之间加一根连线
• ③以第一棵树的根为轴心顺时针旋转 45°

4.2.3 二叉树转化为森林

规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，故将根的右链断开。 二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树， 应用同样的方法，直到最后只剩一颗没有右子树的二叉树为止，最后再将每颗二叉树依次转换成树，就得到了原森林，如下图所示，二叉树转化为森林是唯一的

4.3 树和森林的遍历 4.3.1 树的先根遍历

若树非空 ，先的问根结点，再依次遍历根结点的每颗子树，遍历子树时仍遵循先根后子树的规则。其遍历序列与这颗树相应二叉树的先序序列相同。

4.3.2 树的后根遍历

若树非空，先依次遍历根结点的每颗子树，再出问根结点，遍历子树时仍遵循先子树后根的规则。其遍历序列与这颗树相应二叉树的中序序列相同

4.3.3 森林的先序遍历

若森林为非空，则按如下规则进行遍历 ：

• 询问森林中第一棵树的根结点
• 先序遍历第一棵树中根结点的子树森林
• 先序遍历除去第一棵树之后剩余的树构成的森林

4.3.4 森林的中序遍历

森林为非空时，技如下规则进行遍历

• 中序遍历森林中第一棵树的根结点的子树森林
• 出问第一棵树的根结点
• 中序遍历除去第一棵树之后剩余的树构成的森林

五、二叉排序树 5.1 定义

二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树：

• 若左子树非空，则左子树上所有结点的值均小于根结点的值。
• 若右子树非空， 则右子树上所有结点的值均大于根结点的值
• 左、右子树也分别是一棵二叉排序树。

5.2 查找操作

如果我们想查找某个值的元素是否存在在树中，我们可以从根节点的元素进行比较，然后我们将查找元素和根节点进行比较，如果根节点和查找元相等的话那么就找到了，如果查找元素比根节点大的话我们就往右子树走，否则往左子树走，直到找到了就返回找到的结点

Node *BST_Search(Node *root,ElemType key) {
    while(root != NULL && root->data != key) {
        if(root->data rchild;
        else root = root->lchild;
    }
    return root;
}

5.3 插入操作

插入操作其实和查找类似，我们从根节点开始不断与之比较，最后找到一个空结点的位置，当然如果在查找的过程中找到了这个元素，那么说明插入失败，因为已经存在了

Node * Create_Node(ElemType key) {
    Node *p = (Node)malloc(sizeof(Node));
    p->data = key;
    p->lchild = p->rchild = NULL;
}

int BST_insert(Node *root,ElemType key) {
    if(!root) {//如果是根节点元素为空的话
        root = Create_Node(key);
        return 1;
    }
    if(root->data == key)
        return 0;//已经存在，插入失败
    else if(root->data rchild == NULL) {
            Node *p = Create_Node(key);
            root->rchild = p;
            return 1;//成功插入
        } else {
            return BST_insert(root->rchild,key);
        }
    }
    else {//插入到左子树
    	if(root->lchild == NULL) {
            Node *p = Create_Node(key);
            root->lchild = p;
            return 1;//成功插入
        } else {
            return BST_insert(root->lchild,key);
        }
    }
}

5.4 构造操作

不断将序列中的元素加入到二叉树即可

Node *Create_BST(Node *root,ElemType vec[],int n) {
    root = NULL;
    for(int i = 0;i