首页 > 代码库 > 二叉树的实现_遍历_重构_树形显示
二叉树的实现_遍历_重构_树形显示
1 //测试数据 2 //1 2 4 7 -1 -1 -1 5 -1 -1 3 -1 6 -1 -1 3 //1 2 4 11 -1 22 -1 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1 4 5 6 #include <iostream> 7 #include <cstring> 8 using namespace std; 9 10 template<typename T> 11 struct BinaryNode 12 { 13 T element; 14 BinaryNode<T> *left; 15 BinaryNode<T> *right; 16 17 BinaryNode() : element(0), left(nullptr), right(nullptr) { } 18 BinaryNode(const T &theElement, BinaryNode *lt, BinaryNode *rt) 19 : element(theElement), left(lt), right(rt) {} 20 21 }; 22 23 24 template<typename T> 25 class BinarySearchTree 26 { 27 public: 28 BinarySearchTree() { 29 root = nullptr; 30 } 31 BinarySearchTree(const BinarySearchTree& rhs) { //复制构造函数 32 root = clone(rhs.root); 33 } 34 ~BinarySearchTree(); 35 36 void RootCreate(const T& end); //创建根结点的以下结点 37 38 bool contains(const T& x) const; 39 40 bool getNode(const T& e, const T&sub) { 41 if (getNode(e, root) != nullptr) { 42 getNode(e, root)->element = sub; //得到元素为e的结点 43 return true; 44 } 45 return false; 46 } 47 48 //求父亲的值 49 T getParents(const T& e) const { 50 return getParents(root, e); 51 } 52 53 bool isEmpty() const { 54 if (root == nullptr) 55 return true; 56 return false; 57 } 58 59 void PreprintTree() const { 60 PreprintTree(root); 61 } 62 63 void InprintTree() const { 64 InprintTree(root); 65 } 66 67 void PostprintTree() const { 68 PostprintTree(root); 69 } 70 71 void LevelprintTree() const { 72 LevelprintTree(root); 73 } 74 75 void PreprintTree_N() const { 76 PreprintTree_N(root); 77 } 78 79 void InprintTree_N() const { 80 InprintTree_N(root); 81 } 82 83 void PostprintTree_N() const { 84 PostprintTree_N(root); 85 } 86 87 void DisplayTreeShape(int level = 1) const { 88 DisplayTreeShape(root, level); 89 } 90 91 void makeEmpty(); 92 93 void remove(const T &x); 94 95 int Depth(); 96 int CountLeaf() { 97 BinaryNode<T> *p = root; 98 int count = 0; 99 CountLeaf(p, count);100 return count;101 }102 103 const BinarySearchTree& operator = (const BinarySearchTree& rhs);104 105 private:106 107 BinaryNode<T> *root; //指向树根结点的指针108 109 int Create(BinaryNode<T> *p, T end, int flag);110 111 void remove(const T & x, BinaryNode<T> * & t, int rh);112 113 bool contains(const T & x, BinaryNode<T> *t) const;114 115 BinaryNode<T> * getNode(const T &x, BinaryNode<T> *t);116 117 T getParents(BinaryNode<T> *p, const T& e) const;118 119 void makeEmpty(BinaryNode<T> * & t);120 //利用 递归 算法 计算树的 深度 121 int Depth(BinaryNode<T> * t, int level, int &depth);122 //利用 递归 算法 计算树的 高度123 void CountLeaf(BinaryNode<T> * t, int &count);124 125 126 void PreprintTree(BinaryNode<T> * t) const; //先序遍历 127 void InprintTree(BinaryNode<T> *t) const; //中序遍历 128 void PostprintTree(BinaryNode<T> * t) const; //后序遍历129 void LevelprintTree(BinaryNode<T> * t) const; //层次遍历 130 131 void PreprintTree_N(BinaryNode<T> * t) const; //非递归先序遍历132 void InprintTree_N(BinaryNode<T> * t) const; //非递归中序遍历二叉树 133 void PostprintTree_N(BinaryNode<T> * t) const; //非递归后序遍历二叉树 134 void DisplayTreeShape(BinaryNode<T> *bt, int level) const; //二叉树的树形显示算法 135 136 137 BinaryNode<T> * clone(BinaryNode<T> * t) const;138 };139 140 template<typename T>141 bool BinarySearchTree<T>::contains(const T& x) const142 {143 return contains(x, root);144 }145 146 template<typename T>147 bool BinarySearchTree<T>::contains(const T & x, BinaryNode<T> *t) const148 {149 bool judge;150 if (t) {151 if (t->element == x)152 return true;153 judge = contains(x, t->left);154 if (judge) return true;155 judge = contains(x, t->right);156 if (judge) return true;157 }158 return false;159 }160 161 template<typename T>162 BinaryNode<T>* BinarySearchTree<T>::getNode(const T & x, BinaryNode<T> *t)163 {164 BinaryNode<T>* ptemp;165 if (t)166 {167 if (t->element == x) return t;168 ptemp = getNode(x, t->left);169 if (ptemp) return ptemp;170 ptemp = getNode(x, t->right);171 if (ptemp) return ptemp; 172 } 173 return nullptr;174 }175 176 template<typename T>177 T BinarySearchTree<T>::getParents(BinaryNode<T> *p, const T& e) const178 {179 const int maxn = 1024;180 BinaryNode<T> *Queue[maxn], *ptemp;181 int front = 0, rear = 0;182 if (p != nullptr && e != root->element) //为空，没有父节点, 且不为根结点 183 {184 Queue[rear++] = p; //让根结点入队列,rear加1 185 while (front != rear) //栈不为空 186 {187 ptemp = Queue[front++]; //将队列的结点依次出队188 if ((ptemp->left && ptemp->right->element == e )|| (ptemp->right && ptemp->left->element == e))189 return ptemp->element; //如果是，则返回 190 else 191 {192 if (ptemp->left) Queue[rear++] = ptemp->left; //左结点不为空，则入栈 193 if (ptemp->right) Queue[rear++] = ptemp->right; //右不为空，则入栈 194 }195 }196 }197 return -1; 198 }199 200 201 template<typename T>202 void BinarySearchTree<T>::RootCreate(const T& end) //创建二叉树 203 {204 cout << "请按先序序列的顺序输入二叉树,-1为空指针域标志：" << endl;205 BinaryNode<T> *p;206 int x;207 cin >> x;208 if (x == end) return;209 p = new BinaryNode<T>(x, nullptr, nullptr);210 root = p;211 Create(p, end, 1);212 Create(p, end, 2);213 }214 215 template<typename T>216 int BinarySearchTree<T>::Create(BinaryNode<T> *p, T end, int flag)217 {218 BinaryNode<T> *t;219 T x;220 cin >> x;221 if (x != end)222 {//子节点的左右结点先赋值 223 t = new BinaryNode<T>(x, nullptr, nullptr);224 if (flag == 1) p->left = t; //标志i=1,代表左孩子225 if (flag == 2) p->right = t; //i=2结点为右孩子 226 Create(t, end, 1); //递归调用，直到 x == end 227 Create(t, end, 2);228 }229 return 0;230 }231 232 template<typename T>233 void BinarySearchTree<T>::remove(const T &x)234 {235 remove(x, root, 1);236 remove(x, root, 2);237 }238 239 /************************************************************************/240 /* x is item to remove */241 /* t is the node that roots the subtree */242 /* Set the new root of the subtree */243 /* 1.结点是一片树叶时 -- 可被立即删除*/244 /* 2.结点有一个儿子, 则该结点可以在其父节点调整他的链 以绕过该结点后被删除 */245 /* 3.结点有两个儿子, 则其右子树的最小数据代替该结点的数据，并递归删除那个结点 */246 /* 注: 右子树中的最小的结点不可能有左结点 */247 /************************************************************************/248 template<typename T>249 void BinarySearchTree<T>::remove(const T &x, BinaryNode<T> * & t, int rh)250 {251 if (t == nullptr) return;252 if (t->element == x && rh == 1)253 {254 makeEmpty(t->left);255 }256 else {257 makeEmpty(t->right);258 }259 remove(x, t->left, rh);260 remove(x, t->right, rh);261 }262 263 /************************************************************************/264 ///* Destructor for the tree265 /************************************************************************/266 template<typename T>267 BinarySearchTree<T>::~BinarySearchTree()268 {269 makeEmpty();270 }271 272 template<typename T>273 void BinarySearchTree<T>::makeEmpty() //公有函数274 {275 makeEmpty(root);276 }277 278 /************************************************************************/279 ///* Internal method to make subtree empty -- 私有函数280 /************************************************************************/281 template<typename T>282 void BinarySearchTree<T>::makeEmpty(BinaryNode<T> * & t)283 {284 if (t != nullptr)285 {286 makeEmpty(t->left);287 makeEmpty(t->right);288 delete t;289 }290 t = nullptr;291 }292 293 /************************************************************************/294 ///* Deep copy295 /************************************************************************/296 template<typename T>297 const BinarySearchTree<T>& BinarySearchTree<T>::operator = (const BinarySearchTree &rhs)298 {299 if (this != &rhs) {300 makeEmpty();301 root = clone(rhs.root);302 }303 return *this;304 }305 306 /************************************************************************/307 ///* Internal method to clone subtree. -- 递归复制结点308 /************************************************************************/309 template<typename T>310 BinaryNode<T>* BinarySearchTree<T>::clone(BinaryNode<T> * t) const311 {312 if (t == nullptr)313 return nullptr;314 return new BinaryNode<T>(t->element, clone(t->left), clone(t->right));315 }316 317 //利用递归计算树的深度 318 template<typename T>319 int BinarySearchTree<T>::Depth()320 {321 BinaryNode<T> *t = root;322 int depth = 0;323 if (root == nullptr)324 return 0;325 Depth(t, 1, depth);326 return depth;327 }328 329 //由public的函数Depth调用, 完成树的深度的计算，p是根结点，Level是层，depth用来返回树的深度 330 template<typename T>331 int BinarySearchTree<T>::Depth(BinaryNode<T> *t, int level, int &depth)332 {333 if (level > depth) depth = level; //层数334 if (t->left) Depth(t->left, level + 1, depth); //递归遍历左子树，且层数加1 335 if (t->right) Depth(t->right, level + 1, depth); //递归遍历右子树, 且层数加1 336 return 0;337 }338 339 template<typename T>340 //利用 递归 算法 计算树的 高度341 void BinarySearchTree<T>::CountLeaf(BinaryNode<T> * t, int &count)342 {343 if (t == nullptr) return; //为空时，退出344 345 // CountLeaf(t->left, count);346 // CountLeaf(t->right, count); 347 if (!(t->left) && !(t->right)) { //儿子为空时 348 count++;349 }350 CountLeaf(t->left, count);351 CountLeaf(t->right, count);352 }353 354 355 /************************************************************************/356 ///* printTree --- 前序遍历 357 /************************************************************************/358 template<typename T>359 void BinarySearchTree<T>::PreprintTree(BinaryNode<T> * t) const360 {361 if (t != nullptr) {362 cout << t->element << ‘ ‘;363 PreprintTree(t->left);364 PreprintTree(t->right);365 }366 }367 368 //中序遍历 369 template<typename T>370 void BinarySearchTree<T>::InprintTree(BinaryNode<T> * t) const371 {372 if (t != nullptr) {373 InprintTree(t->left);374 cout << t->element << ‘ ‘;375 InprintTree(t->right);376 }377 }378 379 //后序遍历 380 template<typename T>381 void BinarySearchTree<T>::PostprintTree(BinaryNode<T> * t) const382 {383 if (t != nullptr) {384 PostprintTree(t->left);385 PostprintTree(t->right);386 cout << t->element << ‘ ‘;387 }388 }389 390 //利用队列Queue层次遍历二叉树 391 template<typename T>392 void BinarySearchTree<T>::LevelprintTree(BinaryNode<T> * t) const393 {394 const int maxn = 1024;395 BinaryNode<T> *Queue[maxn]; //一维数组作为队列 396 BinaryNode<T> *tmp;397 int front = 0, rear = 0; //队列初始为空 398 if (root) {399 Queue[rear++] = root; //二叉树的根结点指针入队列 400 while (front != rear)401 {402 tmp = Queue[front++]; //队首的元素出队列403 if (tmp) cout << tmp->element << ‘ ‘; //输出结点值404 if (tmp->left) Queue[rear++] = tmp->left;405 if (tmp->right) Queue[rear++] = tmp->right;406 }407 }408 }409 410 //先序遍历 (DLR)411 template<typename T>412 void BinarySearchTree<T>::PreprintTree_N(BinaryNode<T> * t) const //非递归先序遍历413 {414 const int maxn = 1024;415 BinaryNode<T> *Stack[maxn];416 int top = 0;417 BinaryNode<T> *tmp = root; //将根结点的指针赋值给tmp 418 419 // cout << "Debug :\n";420 while (tmp || top != 0)421 {422 // cout << "debug : \n";423 while (tmp) {424 cout << tmp->element << ‘ ‘;425 Stack[top++] = tmp; //右孩子入栈 426 tmp = tmp->left; //一直递归到最左的结点 427 }428 if (top) { //栈不为空, 从栈中取出一个结点指针 429 tmp = Stack[--top];430 tmp = tmp->right;431 }432 }433 }434 435 //中序非递归遍历二叉树 (LDR)436 template<typename T>437 void BinarySearchTree<T>::InprintTree_N(BinaryNode<T> * t) const //非递归中序遍历二叉树 438 {439 const int maxn = 1024;440 BinaryNode<T> *Stack[maxn];441 int top = 0;442 BinaryNode<T> *tmp = root;443 444 while (tmp || top != 0)445 {446 while (tmp) { //迭代到最左的子树 447 Stack[top++] = tmp; //左子树入栈 448 tmp = tmp->left;449 } 450 if (top) {451 tmp = Stack[--top]; //出栈最左的子树 452 cout << tmp->element << ‘ ‘; //输出该元素 453 tmp = tmp->right; //并指向右结点开始迭代 454 }455 }456 457 }458 459 //非递归后序遍历二叉树 (LRD)460 template<typename T>461 void BinarySearchTree<T>::PostprintTree_N(BinaryNode<T> * t) const462 {463 const int maxn = 1024;464 struct Mystack {465 BinaryNode<T> * link;466 int flag;467 };468 469 Mystack Stack[maxn];470 BinaryNode<T> * p = root, *tmp;471 472 if (root == nullptr) return;473 474 int top = -1, //栈顶初始化 475 sign = 0; //为结点tmp 的标志量 476 477 while (p != nullptr || top != -1)478 {479 while (p != nullptr) //遍历到最左 480 {481 Stack[++top].link = p; //并且一直入栈 482 Stack[top].flag = 1; //设置flag为第一次入栈 483 p = p->left;484 }485 486 if (top != -1)487 {488 tmp = Stack[top].link;489 sign = Stack[top].flag;490 top--; //出栈 491 492 if (sign == 1) //结点第一次进栈 493 {494 top++;495 Stack[top].link = tmp;496 Stack[top].flag = 2; //标记为第二次出栈 497 p = tmp->right;498 }499 else { //第二次出栈就输出 500 cout << tmp->element << ‘ ‘; //访问该结点数据域 501 p = nullptr;502 }503 }504 505 }506 507 }508 509 //树形显示二叉树，也是中序遍历 510 template<typename T>511 void BinarySearchTree<T>::DisplayTreeShape(BinaryNode<T> *bt, int level) const512 { 513 if (bt) //二叉树的树形显示算法514 {515 DisplayTreeShape(bt->right, level + 1); //空二叉树不显示516 cout << endl;517 for (int i = 0; i < level - 1; i++)518 cout << " "; //确保在第level列显示结点 519 cout << bt->element;520 DisplayTreeShape(bt->left, level + 1); //显示左子树521 }522 }523 524 //先序(preorder) -- 中序(inorder) ===> 得到后序遍历(postorder)525 //先序为了得到根结点， 中序为了得到左右两个子序列 526 template<typename T>527 void BinaryTreeFromOrderings(const T *inorder, const T *preorder, int length)528 {529 if (length == 0) return;530 T node_value = http://www.mamicode.com/*preorder; //得到先序序列的第一个元素 ==> 根结点 531 int rootIndex = 0; //根结点的索引 532 for (; rootIndex < length; rootIndex++) { //在中序序列中，遍历到(先序遍历的)根结点的地方终止 533 if (inorder[rootIndex] == *preorder) 534 break;535 }536 537 /******************* Left Root Right *********************/538 //left -- 中序遍历开始的位置，后序遍历开始的位置 可以遍历的总长度 539 BinaryTreeFromOrderings(inorder, preorder + 1, rootIndex);540 //Right541 BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1)); 542 cout << node_value << ‘ ‘;543 }544 545 546 int main()547 {548 int testData;549 BinarySearchTree<int> test;550 cout << "创建树: \n";551 test.RootCreate(-1);552 553 cout << "\n全部元素为: \n";554 test.PreprintTree();555 556 cout << endl;557 558 cout << "输入查找元素: \n";559 cin >> testData;560 cout << "是否包含 " << testData << " : " << test.contains(testData) << endl;561 562 cout << testData << "的父亲是:\t";563 cout << test.getParents(testData) << endl;564 565 cout << endl;566 cout << "输入修改元素: \n";567 cin >> testData;568 if (test.getNode(testData, 1000))569 cout << "OK !\n";570 test.PreprintTree();571 cout << "\n";572 573 cout << "\n树的高度: " << test.Depth() << endl;574 cout << "\n叶子的个数: " << test.CountLeaf() << endl;575 cout << endl;576 577 cout << "先序遍历树元素: \n";578 test.PreprintTree();579 580 cout << "\n\n中序遍历树元素: \n";581 test.InprintTree();582 583 cout << "\n\n后序遍历树元素: \n";584 test.PostprintTree();585 586 cout << "\n\n层次遍历树元素: \n";587 test.LevelprintTree();588 589 cout << "\n\n先序遍历树元素(非递归): \n";590 test.PreprintTree_N();591 592 cout << "\n\n中序遍历树元素(非递归): \n";593 test.InprintTree_N();594 595 cout << "\n\n后序遍历树元素(非递归): \n";596 test.PostprintTree_N();597 598 cout << "\n\n二叉树的树形显示算法(下面是逆时针旋转了90°的树): \n";599 test.DisplayTreeShape(43);600 601 cout << endl;602 603 const char* pr = "ABCDEFGHI"; //GDAFEMHZ604 const char* in = "BCAEDGHFI"; //ADEFGHMZ605 BinaryTreeFromOrderings(in, pr, strlen(pr));606 607 cout << endl; 608 609 return 0;610 }
二叉树的实现_遍历_重构_树形显示
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。