二叉搜索树 今天药忘吃喽~ 2021-12-14 08:47 231阅读 0赞 ## 二叉搜索树 ## **C++实现**![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70] #include<queue> #include<iostream> #include<vector> using namespace std; const int arrrlens = 8; int arr[arrrlens] = { 10, 5, 4, 9, 11, 20, 8, 15 }; /*二叉搜索树满足:一个节点的左节点值小于这个节点的,右节点值大于这个节点*/ class Node { public: Node(int el = 0, Node* l=NULL, Node* r=NULL) { data = el; left = l; right = r; } int data; Node* left, *right; }; class Tree { public: Tree() { root = NULL; } ~Tree() { delete root; } int preOrder(Node*); int create(); int find(int); vector<vector<int>> levelTraversal(Node*); bool __insert(Node*&, int val); bool insert(Node*& , int val); int del(int); public: Node* root; }; //先序遍历打印 int Tree::preOrder(Node* root) { if (root != NULL) { cout << root->data << " "; preOrder(root->left); preOrder(root->right); } return 0; } //节点查找 int Tree::find(int key) { Node* p = root; while ( p != NULL) { if (p->data > key) p = p->left; else if (p->data < key) p = p->right; else return 1; } return 0; } //层次遍历 vector<vector<int>> Tree::levelTraversal(Node* root) { queue<Node*> inputQ; vector<vector<int>> ans; if (root == NULL) return ans; inputQ.push(root); while (!inputQ.empty()) { vector<int> temp; int len = inputQ.size(); for (int i = 0; i < len; i++) { Node* p = inputQ.front(); inputQ.pop(); temp.push_back(p->data); if (p->left) inputQ.push(p->left); if (p->right) inputQ.push(p->right); } ans.push_back(temp); } return ans; } //非递归插入法 bool Tree::__insert(Node*& root, int val) { Node* newnode = new Node(val); Node* cur = root, *pre = NULL; if (root == NULL) { root = newnode; return true; } while (cur != NULL) { pre = cur; if (cur->data == val) return false; if (cur->data > val) cur = cur->left; else cur = cur->right; } if (pre->data < val) pre->right = newnode; else pre->left = newnode; return true; } //递归插入法 bool Tree::insert(Node* &root, int val) { if (root == NULL) { root = new Node(val); return true; } if (val == root->data) return false; if (val < root->data) insert(root->left, val); else insert(root->right, val); return true; } //通过每次调用插入方法创建二叉树搜索树 int Tree::create() { for (int i = 0; i < arrrlens; i++) __insert(root, arr[i]); return 0; } int main() { Tree tree; tree.create(); tree.preOrder(tree.root); cout << endl << tree.find(20) << endl; vector<vector<int>> ans = tree.levelTraversal(tree.root); _reverse_iterator(ans); return 0; } [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1VwX2p1bmlvcg_size_16_color_FFFFFF_t_70]: /images/20211214/7529eaf964c14c7ca7be34fd9da87dff.png
相关 二叉搜索树 1 二叉搜索树 二叉搜索树是指一棵树的左子树上所有的节点都小于它的根节点;右子树上所有的节点都大于它的根节点。且对于它的所有子树都是如此。基于这个性质,当我们对二叉搜索树 心已赠人/ 2023年09月28日 09:18/ 0 赞/ 70 阅读
相关 二叉搜索树 在计算机术语中,二叉搜索树又叫二叉查找树、二叉排序树。 二叉搜索树(Binary Search Tree)的定义: 它或者是一棵空树,或者是具有下列性质的二叉树: 若它的 Myth丶恋晨/ 2022年09月30日 06:45/ 0 赞/ 156 阅读
相关 二叉搜索树 搜索树数据结构支持许多动态集合操作,包括SEARCH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE等。因此,我们使用一 ╰+哭是因爲堅強的太久メ/ 2022年08月14日 01:50/ 0 赞/ 154 阅读
相关 二叉搜索树 二叉搜索树的特征定义就是:一个节点的左子节点的关键字值小于这个节点,右子节点的关键字大于或等于这个父节点 package Trees; import java.ut 客官°小女子只卖身不卖艺/ 2022年05月31日 00:50/ 0 赞/ 243 阅读
相关 二叉搜索树 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于 ゝ一世哀愁。/ 2022年04月24日 11:20/ 0 赞/ 201 阅读
相关 二叉搜索树 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RqaDYy た 入场券/ 2022年03月17日 02:18/ 0 赞/ 239 阅读
相关 二叉搜索树 思路 二叉排序树,二叉搜索树好像都行,原理应该都懂,比较基础,但要写出来还是有相当大的难度的。 查找 查找比较简单,基本都是一个while就解决。但查前驱与后继较 短命女/ 2021年12月21日 09:15/ 0 赞/ 229 阅读
相关 二叉搜索树 二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不 小咪咪/ 2021年12月20日 02:53/ 0 赞/ 252 阅读
相关 二叉搜索树 二叉搜索树 C++实现![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9 今天药忘吃喽~/ 2021年12月14日 08:47/ 0 赞/ 232 阅读
相关 二叉搜索树 二叉搜索树 基本概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 1. 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 妖狐艹你老母/ 2021年11月22日 07:30/ 0 赞/ 298 阅读
还没有评论,来说两句吧...