【数据结构】二叉搜索树：查找最小值/最大值

2024-07-17 14:36| 来源: 网络整理| 查看: 265

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 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{ (datadata)?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); coutleft=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 Q; Q.push(root);//先把根节点放到队列里 while(!Q.empty()) { Node* current=Q.front();//存储当前队列中的第一个元素 coutright!=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 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 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

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章