【数据结构】二叉搜索树：查找最小值/最大值 | 二叉树：求二叉树的高度、二叉树的遍历--深度优先/广度优先(c++代码/递归的图像展示/深度理解递归过程)

P29是讲解二叉搜索树的实现中内存里发生的事情，详细讲了内存中堆栈的分配什么的。老师讲的非常清晰，并且每一步都对应图像，我这里就不再文字呈现了，直接看视频吧。P30-P34笔记，视频地址👇。

爱写文章的汉堡包

1787人浏览 · 2023-11-15 23:32:41

爱写文章的汉堡包 · 2023-11-15 23:32:41 发布

P29是讲解二叉搜索树的实现中内存里发生的事情，详细讲了内存中堆栈的分配什么的。老师讲的非常清晰，并且每一步都对应图像，我这里就不再文字呈现了，直接看视频吧。

P30-P34笔记，视频地址👇

http://www.bilibili.com/video/BV1Fv4y1f7T1?p=35&vd_source=02dfd57080e8f31bc9c4a323c13dd49c

二叉搜索树：寻找最小值和最大值

我们再来回顾一下二叉搜索树的定义(不要和二叉树混为一谈哦):

二叉搜索树是二叉树的一种，其左子树上的所有节点的值都比该节点值要小，其右子树上所有节点都比该节点值大

基于二叉搜索树所具有的独特的性质，我们寻找最大值和最小值是很容易实现的，在我们手动寻找的时候，是怎么实现的呢？

我们找最小值的话，就要不停的向左边寻找，看一个节点的左边，向左一直索引，直到到达叶子节点，已经没有左孩子了，那么就找到了他的最小值；同样最大值类似。

那么我们如何用代码实现呢？

其实我最先想到的是使用while循环，因为对于索引这个词，想找到最后一个左边的节点，那我就一直判断 root->left != NULL，来作为while循环的条件，循环内容自然是不断对root进行赋值，循环结束的那一刻就是找到答案的时候，直接return root->data即可。还是比较容易实现的。记住刚开始要判断树是否为空，如果为空直接返回-1(这里节点值不考虑负数)

int Findmin(Node *root)
{
    if (root == NULL)
        return -1;
    while (root->left != NULL)
    {
        root = root->left;
    }
    return root->data;
}

还是很好理解的。

当然还有递归的形式。由于我们的树本身就可以看作一个根节点和其左右子树，所以我们想要找到最值，也就是分别找到对应子树的最值即可。

第一步写树为空的情况；接着就是不断寻找子树的最值，这里以找最大值为例。递归有两个条件：递归内容和递归出口。首先内容很容易想到，就是不断调用自身找子树的最大值；出口就是我们在while循环中想找到的值的条件：找到最后一个右边的节点，而最后一个右边的节点也就是其右孩为空的节点。ok思路结束了。其实在我印象里对递归是有点头大的(😂)莫名发怵，不过写完感觉主要找到递归的两个条件之后也没那么难想了。

int Findmax(Node* root)
{
    if(root==NULL)return -1;
    else if(root->right==NULL)return root->data;//右子树为空 作为递归出口
    return Findmax(root->right);
}

具体完整的代码就不展示了。插入函数之前都写过。

这里附上递归过程图方便理解

二叉树

二叉树对左右两边数据大小没有要求。

求高度

回顾一下定义：二叉树的高度是从根节点到叶子节点的最长路径

我们这里以计算箭头数得高度为准，只有根节点的二叉树的高度为0

这里我们使用递归来求。首先考虑，树为空的情况，只有根节点高度为0，树为空的话return -1

递归内容：由于我们每次递归求的都是子树的高度，所以每次都应该是调用自身来计算左右子树的高度，但是整棵树的高度是取最高的那个，并且由于我们计算的是子树的高度，并没有把根节点与子树之间的链接计算进去，所以最终的返回结果应该是用max函数取二者之间最大然后再+1

递归出口：就是当递归到树为空的时候，返回-1即可。

代码如下

#include<iostream>
using namespace std;
struct Node{
    int data;
    Node* left;
    Node* right;
};
Node* GetNode(int x)
{
    Node* temp=new Node();
    temp->data=x;
    temp->left=temp->right=NULL;
    return temp;
};
void Insert(Node* &root,int data)
{
    if(root==NULL)
    {
        root=GetNode(data);
    }
    else{
        (data<=root->data)?Insert(root->left,data):Insert(root->right,data);
    }
}
int Findheight(Node* root)
{
    if(root==NULL)return -1;//空树的高度为-1
    int leftheight=Findheight(root->left);
    int rightheight=Findheight(root->right);
    return max(leftheight,rightheight)+1;//由于这里递归之后max函数只计算到子树的高度，需要加上根节点到子树的这个链接
}
int main()
{
    Node* root=NULL;
    Insert(root,20);
    Insert(root,2);
    Insert(root,17);
    Insert(root,21);
    int height=Findheight(root);
    cout<<height;
    return 0;
}

这张图画的有点乱哈，把递归的过程展示出来方便理解。

二叉树遍历

二叉树的遍历分为两种思路：深度优先和广度优先。

广度优先--层次遍历

广度优先就是从根节点开始，一层一层，从左至右进行遍历。如下图

感觉这种还是比较容易理解的。

那么我们如何用代码实现咧？我没想到，，。我试着来解释他的思路哈。

这种遍历方式其实我刚看到是感觉比较顺眼的(莫名的啊哈哈)

我们只知道根节点的地址，只能通过它来实现树的遍历和打印，我们能够索引到它的左孩子有孩子，两者之间是没有直接联系的，一旦指向其中一个就没办法再回溯到根节点再找到另一个。可是按照我们层次遍历的方式来说，需要链接如图中的D、J这样的兄弟节点。只能通过根节点以一种巧妙地方式来实现。于是通过队列(FIFO)这种方式来实现。

进入队列一个节点就可以链接到他的孩子们，我们将根节点放进队列，此时知道根节点的地址，通过根节点我们可以找到他的孩子节点，只是我们此时并没有访问他们。

当我们从队列中取出一个节点并访问它时，我们实际上是在访问当前层级的节点。然后，当我们将一个节点的所有子节点添加到队列的末尾时，我们实际上是在准备访问下一层级的节点。这样，我们就可以确保总是先访问当前层级的节点，再访问下一层级的节点，这正是广度优先遍历的顺序。

当队列非空的时候，我们记录下当前队列的第一个节点，打印该节点同时将其孩子们从左至右入队，之后完成了他的使命，就将其出队。继续循环往复，直到树遍历完也就是队列为空了

一些思考(这点还是要好好揣摩的)

奥我想起来了为什么这种比较遍历方式比较亲切，还有我刚开始其实在想解释为什么一定要使用队列的问题上想过如果使用数组实现为什么不可以？我是想通过根节点的索引，我们直接把每个结点的数据内容作为一个连续的数组，因为我们已经知道了应该先访问根节点，然后访问孩子从左至右，那么既然已经确定了读取方式，为什么不能使用数组实现呢？结果bing告诉我数组是实现完全二叉树的特殊方式，一瞬间终于想起来，原来是这样啊，感觉亲切是因为之前学过(我真。。。)

如果不是完全二叉树，也就是树并不是很整齐，缺左少右的那种，那我们使用数组存储的时候就会有空位，但我就又想了[笑]也可以通过提前判断来确定是否有孩子再存入数组啊，只是

取自bing: (划重点！！！)

虽然在某些情况下使用数组是可行的，但在大多数情况下，使用队列来实现广度优先遍历会更加方便和高效。队列的出队操作能够确保我们总是在处理当前层级的节点，而且一旦处理完毕，就可以立即从内存中删除，这在处理大型数据结构时非常有用。所以，队列是实现广度优先遍历的最佳选择。这并不是说数组不能用，只是在这种情况下，队列可能会更加适合。当然，具体选择哪种数据结构，还需要根据实际的需求和场景来决定。每种数据结构都有其优点和适用场景，理解它们的特性和适用性，可以帮助我们更好地解决问题。

代码如下

//广度优先--树的层次遍历
#include<iostream>
#include<queue>
using namespace std;
struct Node
{
    int data;
    Node* left;
    Node* right;
};
Node* GetNewNode(int data)
{
    Node* newNode=new Node();
    newNode->data=data;
    newNode->left=newNode->right=NULL;
    return newNode;
}
Node* Insert(Node* root,int data)
{
    if(root==NULL)
    {
        root=GetNewNode(data);
    }
    else if(data>root->data)
    {
        root->right=Insert(root->right,data);
    }
    else{
        root->left=Insert(root->left,data);
    }
    return root;
}
void breadthprint(Node* root)
{
    if(root==NULL)return;
    queue<Node*> Q;
    Q.push(root);//先把根节点放到队列里
    while(!Q.empty())
    {
        Node* current=Q.front();//存储当前队列中的第一个元素
        cout<<current->data<<" ";
        if(current->left!=NULL)Q.push(current->left);
        if(current->right!=NULL)Q.push(current->right);
        Q.pop();//队首元素已经打印过了出队
    }
}
int main()
{
    Node* root = NULL;
	root = Insert(root,15);	
	root = Insert(root,10);	
	root = Insert(root,20);
	root = Insert(root,25);
	root = Insert(root,8);
	root = Insert(root,12);
    breadthprint(root);
    return 0;
}

深度优先--先序/中序/后序

我理解的深度优先的这些遍历方式都是根据树的结构进行遍历的方式。

先序：根左右

中序：左根右

后序：左右根

这个我感觉是多试着写写就会明白的，这里就不再多说啦。

关于代码实现，这里采用递归的方式书写。深度优先侧重对树结构特点的应用，对于每一棵子树和整棵树的写法是一致的，所以主要区别是打印语句的先后位置。注意不要忘了树为空的情况哦。

具体的递归思路画在图里啦，帮助大家深度理解递归是如何实现对每个子树排好序的。

写这两个是想让大家体会对于先/中/后只是打印语句位置的区别这一结论。下面的中序没写完整，相信大家已经明白啦。

代码如下

//深度优先
#include <iostream>
using namespace std;
struct bstNode
{
    int data;
    bstNode *left;
    bstNode *right;
};
bstNode *Getnode(int data)
{
    bstNode *temp = new bstNode();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
void Insert(bstNode *&root, int data)
{
    if (root == NULL)
    {
        root = Getnode(data);
    }
    else
    {
        (data <= root->data) ? Insert(root->left, data) : Insert(root->right, data);
    }
}
//先序
void Preorder(bstNode *root)
{
    if (root == NULL)
        return;
    printf("%d ", root->data);
    Preorder(root->left);
    Preorder(root->right);
}
//中序
void Inorder(bstNode *root)
{
    if (root == NULL)
        return;
    Inorder(root->left);
    printf("%d ", root->data);
    Inorder(root->right);
}
//后序
void Postorder(bstNode *root)
{
    if (root == NULL)
        return;
    Postorder(root->left);
    Postorder(root->right);
    printf("%d ", root->data);
}
int main()
{
    bstNode *root = NULL; // 起始为空树
    Insert(root, 5);
    Insert(root, 15);
    Insert(root, 50);
    Insert(root, 2);
    Insert(root, 6);
    Insert(root, 10);
    Preorder(root);
    cout << endl;
    Inorder(root);
    cout << endl;
    Postorder(root);
    return 0;
}

好啦这部分内容感觉还是比较好理解的。

争取数据结构这两周更完(💪)

本人还是小白，仅靠网课资源学习记录笔记，如果有哪里出现错误的说法欢迎指出，非常感谢。

也欢迎交流建议奥。