首页 > 代码库 > 构建伸展树的伸展操作
构建伸展树的伸展操作
以下结果与书中描述略有出入，因为书中没有给出代码示例，因此只能认为本人的结果与书中描述的现象大致相似；
主要的函数：查找函数（同时伸展）：
1 ETree *findNode(ETree *&root,const int &data) 2 { 3 ETree *tmp; 4 ETree *k1, *k2, *k3; 5 if (root == nullptr) 6 return root; 7 8 //三种主要情况 9 if (root->data =http://www.mamicode.com/= data) 10 return root; 11 else if (root->data > data) 12 {//在左子树的情况 13 if (root->left == nullptr) 14 return nullptr; 15 if (root->left->data =http://www.mamicode.com/= data) 16 { 17 tmp = root->left; 18 root->left = tmp->right; 19 tmp->right = root; 20 root = tmp;//将查到的节点转移到当前根节点 21 } 22 else if (root->left->data > data) 23 {//在左儿子的左子树 24 if (root->left->left == nullptr) 25 return nullptr; 26 if (root->left->left->data =http://www.mamicode.com/= data) 27 { 28 k1 = root; 29 k2 = root->left; 30 k3 = k2->left; 31 k1->left = k2->right; 32 k2->right = k1; 33 k2->left = k3->right; 34 k3->right = k2; 35 root = k3; 36 } 37 else 38 { 39 root->left->left = findNode(root->left->left, data);//这里是实现的重点 40 root = findNode(root, data); 41 } 42 } 43 else 44 { 45 if (root->left->right == nullptr) 46 return nullptr; 47 if (root->left->right->data =http://www.mamicode.com/= data) 48 { 49 k1 = root; 50 k2 = root->left; 51 k3 = k2->right; 52 k1->left = k3->right; 53 k2->right = k3->left; 54 k3->left = k2; 55 k3->right = k1; 56 root = k3; 57 } 58 else 59 { 60 root->left->right = findNode(root->left->right, data); 61 root = findNode(root, data); 62 } 63 } 64 } 65 else 66 { 67 if (root->right == nullptr) 68 return nullptr; 69 70 if (root->right->data =http://www.mamicode.com/= data) 71 { 72 tmp = root->right; 73 root->right = tmp->left; 74 tmp->left = root; 75 root = tmp; 76 } 77 else if (root->right->data < data) 78 { 79 if (root->right->right == nullptr) 80 return nullptr; 81 82 if (root->right->right->data =http://www.mamicode.com/= data) 83 { 84 k1 = root; 85 k2 = root->right; 86 k3 = k2->right; 87 k1->right = k2->left; 88 k2->left = k1; 89 k2->right = k3->left; 90 k3->left = k2; 91 root = k3; 92 } 93 else 94 { 95 root->right->right = findNode(root->right->right, data); 96 root = findNode(root, data); 97 } 98 } 99 else100 {101 if (root->right->left == nullptr)102 return nullptr;103 if (root->right->left->data =http://www.mamicode.com/= data)104 {105 k1 = root;106 k2 = root->right;107 k3 = k2->left;108 k1->right = k3->left;109 k2->left = k3->right;110 k3->left = k1;111 k3->right = k2;112 root = k3;113 }114 else115 {116 root->right->left = findNode(root->right->left, data);117 root = findNode(root, data);118 }119 }120 }121 122 return root;123 }
函数分别为两种情况进行了操作，分别是对称的，其中递归调用的部分是我出错最多的地方；
总体结果与书中类似，但是由于我是间隔进行查询的，因此与书中有差异；应当不影响结果：
全部代码如下：
1 #include <iostream> 2 using namespace std; 3 4 typedef struct _extTree_ 5 { 6 int data; 7 struct _extTree_ *left; 8 struct _extTree_ *right; 9 }ETree; 10 11 ETree *insertNode(ETree *root,const int &data) 12 { 13 if (root == nullptr) 14 { 15 root = new ETree; 16 root->left = nullptr; 17 root->right = nullptr; 18 root->data =http://www.mamicode.com/ data; 19 } 20 else if (root->data > data) 21 root->left = insertNode(root->left, data); 22 else if (root->data < data) 23 root->right = insertNode(root->right, data); 24 return root; 25 } 26 27 ETree *findNode(ETree *&root,const int &data) 28 { 29 ETree *tmp; 30 ETree *k1, *k2, *k3; 31 if (root == nullptr) 32 return root; 33 34 //三种主要情况 35 if (root->data =http://www.mamicode.com/= data) 36 return root; 37 else if (root->data > data) 38 {//在左子树的情况 39 if (root->left == nullptr) 40 return nullptr; 41 if (root->left->data =http://www.mamicode.com/= data) 42 { 43 tmp = root->left; 44 root->left = tmp->right; 45 tmp->right = root; 46 root = tmp;//将查到的节点转移到当前根节点 47 } 48 else if (root->left->data > data) 49 {//在左儿子的左子树 50 if (root->left->left == nullptr) 51 return nullptr; 52 if (root->left->left->data =http://www.mamicode.com/= data) 53 { 54 k1 = root; 55 k2 = root->left; 56 k3 = k2->left; 57 k1->left = k2->right; 58 k2->right = k1; 59 k2->left = k3->right; 60 k3->right = k2; 61 root = k3; 62 } 63 else 64 { 65 root->left->left = findNode(root->left->left, data);//这里是实现的重点 66 root = findNode(root, data); 67 } 68 } 69 else 70 { 71 if (root->left->right == nullptr) 72 return nullptr; 73 if (root->left->right->data =http://www.mamicode.com/= data) 74 { 75 k1 = root; 76 k2 = root->left; 77 k3 = k2->right; 78 k1->left = k3->right; 79 k2->right = k3->left; 80 k3->left = k2; 81 k3->right = k1; 82 root = k3; 83 } 84 else 85 { 86 root->left->right = findNode(root->left->right, data); 87 root = findNode(root, data); 88 } 89 } 90 } 91 else 92 { 93 if (root->right == nullptr) 94 return nullptr; 95 96 if (root->right->data =http://www.mamicode.com/= data) 97 { 98 tmp = root->right; 99 root->right = tmp->left;100 tmp->left = root;101 root = tmp;102 }103 else if (root->right->data < data)104 {105 if (root->right->right == nullptr)106 return nullptr;107 108 if (root->right->right->data =http://www.mamicode.com/= data)109 {110 k1 = root;111 k2 = root->right;112 k3 = k2->right;113 k1->right = k2->left;114 k2->left = k1;115 k2->right = k3->left;116 k3->left = k2;117 root = k3;118 }119 else120 {121 root->right->right = findNode(root->right->right, data);122 root = findNode(root, data);123 }124 }125 else126 {127 if (root->right->left == nullptr)128 return nullptr;129 if (root->right->left->data =http://www.mamicode.com/= data)130 {131 k1 = root;132 k2 = root->right;133 k3 = k2->left;134 k1->right = k3->left;135 k2->left = k3->right;136 k3->left = k1;137 k3->right = k2;138 root = k3;139 }140 else141 {142 root->right->left = findNode(root->right->left, data);143 root = findNode(root, data);144 }145 }146 }147 148 return root;149 }150 151 void deleteTree(ETree *&root)152 {153 if (root == nullptr)154 return;155 if (root->left != nullptr)156 deleteTree(root->left);157 if (root->right != nullptr)158 deleteTree(root->right);159 delete root;160 root = nullptr;161 }162 163 int main(void)164 {165 ETree *root = nullptr;166 ETree *test = nullptr;167 int i = 32;168 while (i > 0)169 {170 root = insertNode(root, i);171 --i;172 }173 test = findNode(root, 1);174 test = findNode(root, 2);175 test = findNode(root, 3);176 deleteTree(root);177 system("pause");178 return 0;179 }
伸展树相关可以自行查阅介绍资料；
以上。
构建伸展树的伸展操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。