首页 > 代码库 > 二叉查找树-插入的函数
二叉查找树-插入的函数
在已知的二叉查找树中插入节点，当然插入后的节点会位于叶子上，如果插入的数据与原来就有的数据相同，那么就不插入，当然如果在树的结构中增加一个代表数据重复次数的成员或是另开一个数据结构保存重复次数。
主要函数如下：
1 BTree *insertNode(BTree *root,int data) 2 { 3 BTree *tmp = nullptr; 4 if (root == nullptr) 5 { 6 tmp = (BTree *)malloc(sizeof(BTree)); 7 tmp->data =http://www.mamicode.com/ data; 8 tmp->left = nullptr; 9 tmp->right = nullptr;10 root = tmp;11 }12 else13 {14 if (data < root->data)15 {16 root->left = insertNode(root->left, data);17 }18 else if (data > root->data)19 {20 root->right = insertNode(root->right, data);21 }22 }23 return root;24 }
全部源代码如下，其余部分同上一篇：查找函数：的代码
1 #include "iostream" 2 #include "stdlib.h" 3 4 #define log(s); std::cout<<s; 5 6 typedef struct _btree_ 7 { 8 int data; 9 struct _btree_ *left; 10 struct _btree_ *right; 11 }BTree; 12 13 BTree *createNode(int data) 14 { 15 BTree *p = (BTree *)malloc(sizeof(BTree)); 16 p->data =http://www.mamicode.com/ data; 17 p->left = nullptr; 18 p->right = nullptr; 19 return p; 20 } 21 22 BTree *findKey(BTree *father,int data) 23 { 24 if (father->data < data) 25 return findKey(father->right, data); 26 else if (father->data>data) 27 return findKey(father->left, data); 28 else 29 return father; 30 } 31 32 BTree *findMax(BTree *root) 33 { 34 if (root != nullptr) 35 while (root->right != nullptr) 36 root = root->right; 37 return root; 38 } 39 40 BTree *findMin(BTree *root) 41 { 42 if (root->left == nullptr) 43 return root; 44 else 45 return findMin(root->left); 46 } 47 48 BTree *createTree(BTree *&root) 49 { 50 BTree *t1, *t2, *t4, *t3, *t6, *t7, *t8, *t9, *t10; 51 t1 = createNode(1); 52 t2 = createNode(9); 53 t3 = createNode(7); 54 t4 = createNode(5); 55 t6 = createNode(15); 56 t7 = createNode(11); 57 t8 = createNode(16); 58 t9 = createNode(12); 59 t10 = createNode(17); 60 root->left = t4; 61 root->right = t6; 62 t4->left = t1; 63 t4->right = t2; 64 t2->left = t3; 65 t6->left = t7; 66 t6->right = t8; 67 t8->left = t9; 68 t8->right = t10; 69 return root; 70 } 71 72 void showResult(BTree *node) 73 { 74 if (node == nullptr) 75 return; 76 std::cout << node->data << std::endl; 77 } 78 79 BTree *insertNode(BTree *root,int data) 80 { 81 BTree *tmp = nullptr; 82 if (root == nullptr) 83 { 84 tmp = (BTree *)malloc(sizeof(BTree)); 85 tmp->data =http://www.mamicode.com/ data; 86 tmp->left = nullptr; 87 tmp->right = nullptr; 88 root = tmp; 89 } 90 else 91 { 92 if (data < root->data) 93 { 94 root->left = insertNode(root->left, data); 95 } 96 else if (data > root->data) 97 { 98 root->right = insertNode(root->right, data); 99 }100 }101 return root;102 }103 104 int main(void)105 {106 BTree *root = nullptr;107 root = createNode(10);108 root = createTree(root);109 root = insertNode(root,8);110 system("pause");111 return 0;112 }
结果是这样的：
树的原结构如下：（用Word画的）
如果有错误之处希望读者能够指出，不胜感激。
以上。
二叉查找树-插入的函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。