【数据结构】树——二叉搜索树(C++)

@TOC

树概念树状图是一种数据结构，它是由 n(n =1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除 了根结点外，每个子结点可以分为多个不相交的子树。

二叉树同线性表，一个没有限制条件的线性表就是一个数组，但是加以限制条件就得到了非常有用的栈、队列、优先队列等。

引出二叉树

树也是一样，一个没有限制的树由于太灵活，控制起来比较复杂。如果对普通的树加上一些人为的限制，比如 结点只允许有两个子结点，这就是二叉树。

二叉树是一个每个结点最多只能有两个分支的树，左边的分支称之为左子树，右边的分支称之为右子树。

如下图所示：

(1).在非空二叉树中，第 i-1 层的结点总数不超过 , i =1；

(2).深度为 h-1 的二叉树最多有 2的h次方个结点(h =1)，最少有 h 个结点；

(3).对于任意一棵二叉树，如果其叶结点数为 N0，而度数为 2 的结点总数为 N2，则 N0=N2+1；(叶子结点的个数=度为2的结点个数+1)

常见二叉树分类完全二叉树(1)完全二叉树—— 若设二叉树的高度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶 子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树（堆就是完全二叉树）

满二叉树(2)满二叉树——除了叶结点外每一个结点都有左右子结点且叶子结点都处在最底层的二叉树。

平衡二叉树(3)平衡二叉树:又被称为 AVL 树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。（高度从0开始数）

二叉搜索树(4)二叉搜索树——又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一棵空树或是满足下列性质的二叉树：

1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

3）左、右子树也分别为二叉搜索树。

(查找的效率非常高(类似于二分查找，每次对比几乎能去掉一半数据(理想情况下)))

红黑树红黑树 — 是每个结点都带有颜色属性（颜色为红色或黑色）的平衡二叉查找树，满足下列性质：

1）结点是红色或黑色；

2）根结点是黑色；

3）所有叶子结点都是黑色；

4）每个红色结点必须有两个黑色的子结点。(从每个叶子到根的所有路径上不能有两个连续的红色结点。)

5）从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。

二叉树搜索树实现

如果在一组有序的数组中插入一个数字，插入后仍保证这组数是有序的。

如果采用顺序表的形式，会涉及到大量数据的移动。

不移动大量数据可以用链表实现，但是寻找合适的位置还得遍历每个结点的data。如何高效的进行此操纵呢。

那么我们可以用二叉树的形式，以数据集第一个元素为根节点，之后将比根节点小的元素放在左子树中，将比根节点大的元素放在右子树中，在左右子树中同样采取此规则。那么在查找 x 时，若 x 比根节点小可以排除右子树所有元素， 去左子树中查找（类似二分查找），这样查找的效率非常好，而且插入的时间复杂度为 O（h），h 为树的高度，较 O（n）来说效率提高不少。故二叉搜索树用作一些查找和插入使用频率比较高的场景。

二叉搜索树一般采用链式存储方式，每个结点包含两个指针域和一个数据域，存储结点信息。

(能不用递归的地方尽量不用递归，因为如果递归的层级太深的话，容易导致栈溢出。)

Mystack.h

#include iostream 

using namespace std;

#define MAX_SIZE 128


//插入元素-构建树

//为什么要传二级指针(指针引用)？因为根据大小排布，根节点是会发生变化的。

//传1级指针(引用)，修改对应东西里面的内容

//传2级指针(指针+ 引用)，修改这个东西

bool insertBtree(BTree* root, BNode* node)

 BNode* tmp = NULL;

 BNode* parent = NULL;

 if (!node)

 return false;

 else//置空新结点的左右子树

 node- lchild = NULL;

 node- rchild = NULL;

 if (root)//存在根节点，那就准备对比大小为新的结点寻找合适的插入位置

 tmp = root;//拿到根结点

 else//如果第一次构建树，没有根结点，那就创建一个

 root = node;

 return true;

 while (tmp)

 parent = tmp;//保存一个父结点

 if (isLess(node- data, tmp- data))//如果当前插入结点数值小于父结点数值

 tmp = tmp- lchild;

 else//大于等于

 tmp = tmp- rchild;

 if (isLess(node- data, parent- data))//小于

 parent- lchild = node;

 else

 parent- rchild = node;

 return true;

//找到当前结点中左子树中最大的值

int findMax(BTree* root)

 assert(root);

 //方式一,使用递归

 //只要当前结点有右子树就进去,直到没有右子树,当前结点的data就是最大的

 if (root- rchild == NULL)

 return root- data;

 return findMax(root- rchild);

 //方式二，使用循环方式

 因为传进来的不是二级指针，我们能对root的值进行成功修改

 但是不能改变root指向的地址，也就是说root = root- rchild

 没有改变原来传进来的root指向

 也就是说，指针存的是地址，要修改指针的地址，需要指针的指针。(传参时)

 /*while (root- rchild)

 root = root- rchild;

 return root- data;*/


 1.要删除的结点为叶子结点，直接删除即可

 2.要删除的结点存在左子结点不存在右子结点，用左子结点代替删除结点即可

 3.要删除的结点存在右子结点，不存在左子结点，直接用右子结点代替删除结点即可

 4.要删除的结点左右子树都有，则取左子树上最大结点或右子树上最小结点代替删除结点


//成功找到，根据情况进行删除操作，然后逐层返回

BTree* deleteNode(BTree* root, int key, BNode* DeleteNode)

 //为空

 if (!root)

 return NULL;

 //下面这两个if确定key的位置，找到它这个结点

 if (root- data key)

 root- lchild = deleteNode(root- lchild, key, DeleteNode);

 return root;

 if (root- data key)

 root- rchild = deleteNode(root- rchild, key, DeleteNode);

 return root;

 //找到要删除的结点,存进DeleteNode（指针的引用 or 二级指针 可以改变地址）

 DeleteNode = root;


 //成功找到，根据条件进行返回

 if ((!root- lchild) (!root- rchild))//要删除的结点为root结点

 delete root;

 return NULL;

 if ((root- lchild) (!root- rchild))//要删除的结点有左孩子，没有右孩子

 return root- lchild;

 if ((!root- lchild) (root- rchild))//要删除的结点有右孩子，没有左孩子

 return root- rchild;

 //要删除的结点左右孩子都有

 //先找到当前要删除的结点左子树中最大的值(右子树最小的值同理)

 int val = findMax(root- lchild);

 root- data = val;//代替要删除的key值

 //将找到的ket = val的那个结点删除

 root- lchild = deleteNode(root- lchild, val, DeleteNode);

 //这里最后delete的那个结点就并不是和具有val值的那个结点，而是要删除结点中左子树中最大data的那个。

 //将最大data覆盖上val值对应结点的那个data

 //删除的方式不同是因为对应的父子结点情况不同

 return root;

//前序遍历(中左右)——递归实现

void FrontPrint(BTree* root)

 //到哪个结点， 哪个结点就是中，因为都可以有自己的子结点

 if (!root)

 return;

 cout root- data " ";

 FrontPrint(root- lchild);

 FrontPrint(root- rchild);

//注意返回调用的位置，从哪调用return回哪,多层中的语句执行结束也会返回到调用处

//中序遍历(左中右)——递归实现

void MidPrint(BTree* root)

 if (!root)

 return;

 MidPrint(root- lchild);

 cout root- data " ";

 MidPrint(root- rchild);

//后序遍历(左右中)——递归实现

void BehindPrint(BTree* root)

 if (!root)

 return;

 BehindPrint(root- lchild);

 BehindPrint(root- rchild);

 cout root- data " ";

//递归方式查找

//注意返回指针类型

//找到返回的就是指向那个结点的一个指针

//没找到返回的就是NULL

BNode* Find1(BTree* root, int key)

 //由此我们可以知道 || 运算符是从左往有进行执行的，左边一旦成立，那么根本就不看后面的运算结果

 //这里的root为空，说明没查到，为空执行root- data越界访问，所以要把!root条件放到前面

 if (!root || isEqual(root- data, key))

 return root;

 else if (isLess(key, root- data))

 return Find1(root- lchild, key);

 else

 return Find1(root- rchild, key);

//非递归方式查找1

void Find2(BTree* root, int key)

 while (root)

 if (isLess(root- data, key))

 root = root- rchild;

 else if (isLess(key, root- data))

 root = root- lchild;

 else

 cout "找到了" endl;

 break;

 if (!root)

 cout "没找到" endl;

//非递归方式查找2

BNode* Find3(BTree* root, int key)

 while (root !isEqual(root- data, key))

 if (isLess(root- data, key))

 root = root- rchild;

 else

 root = root- lchild;

 return root;

//借助栈实现前序遍历

//谁的优先级最低谁就先被压进栈

void PrintFrontWithStack(BTree* root)

 BNode cur;

 if (!root)

 return;

 Stack Tstack;

 initStack(Tstack);

 pushStack(Tstack, *root);

 while (!isEmpty(Tstack))

 popStack(Tstack, cur);

 cout cur.data " ";


  数据结构和算法(二叉搜索树) 

二叉搜索树是二叉树的一种特殊形式。 二叉搜索树具有以下性质：每个节点中的值必须大于（或等于）其左侧子树中的任何值，但小于（或等于）其右侧子树中的任何值。

二叉搜索树（BST）是二叉树的一种特殊表示形式，它满足如下特性：

每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。

每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

在二叉搜索树中实现搜索操作 - 介绍

二叉搜索树主要支持三个操作：搜索、插入和删除。 在本章中，我们将讨论如何在二叉搜索树中搜索特定的值。

根据BST的特性，对于每个节点：

如果目标值等于节点的值，则返回节点；

如果目标值小于节点的值，则继续在左子树