由后序遍历结果构造二叉查找树 && 二叉查找树链表化-白红宇

由后序遍历结果构造二叉查找树 && 二叉查找树链表化

阅读量：7163 次

发布时间：2019-06-29

本文共 5826 字，大约阅读时间需要 19 分钟。

　　二叉查找树通俗说就是左孩子比父亲小，右孩子比父亲大。构造这么一个树，树嘛，递归即可。

　　例如一棵树后序遍历是这样（下图的树）：2 9 8 16 15 10 25 38 45 42 30 20。最后的20肯定是树根，这里要抓住一个规律：20是树根，那么2 9 8 16 15 10都是左子树，25 38 42 45 30在右子树，因为左边都小于根、右边都大于根嘛。然后递归即可。

　　下面是树的样子和代码和src.txt（后序遍历的结果）以及运行结果：

1 #include 
       
         2 #include 
        
          3 #include 
         
           4  5 using std::cin; 6 using std::cout; 7 using std::endl; 8 using std::vector; 9 10 #define MY_DEBUG11 12 struct Node13 {14     int data;15     Node* pLC;16     Node* pRC;17 };18 19 Node* creatBSTree(vector
          
           & arr)20 {21     //数组里面没有元素22     if (!arr.size())23         return nullptr;24 25     Node* pNode = new Node;26     int thisData = arr.back();27     pNode->data = thisData;28 29     //只有一个元素就不要折腾了，它就是叶子节点，它没有左右孩子30     if (1 == arr.size())31     {32         pNode->pLC = pNode->pRC = nullptr;33         return pNode;34     }35 36     //下面找出左半边37     vector
           
             arrLeft;38     for (int i = 0; i < arr.size() - 1; i++)39     {40         if (arr[i] < thisData)41             arrLeft.push_back(arr[i]);42         else43             break;44     }45 46     //下面找出右半边47     vector
            
              arrRight;48 for (int i = arrLeft.size(); i < arr.size() - 1; i++)49 arrRight.push_back(arr[i]);50 51 #ifdef MY_DEBUG52 for (int i = 0; i < arrLeft.size(); i++)53 cout << arrLeft[i] << " ";54 cout << endl;55 56 for (int i = 0; i < arrRight.size(); i++)57 cout << arrRight[i] << " ";58 cout << endl << endl;59 #endif60 61 //递归处理左右孩子。arrLeft和arrRight可能为空，不要紧，在函数的开头处理了62 pNode->pLC = creatBSTree(arrLeft);63 pNode->pRC = creatBSTree(arrRight);64 65 return pNode;66 }67 68 69 //中序遍历70 void show(Node* pNode)71 {72 if (!pNode)73 return;74 75 show(pNode->pLC);76 cout << pNode->data << " ";77 show(pNode->pRC);78 }79 80 int main(void)81 {82 vector
             
               arr;83 std::ifstream fin("src.txt");84 85 int temp;86 while (fin >> temp)87 arr.push_back(temp);88 89 Node* pHead = creatBSTree(arr);90 show(pHead);91 cout << endl;92 cin.get();93 }

View Code

2 9 8 16 15 10 25 38 45 42 30 20

　　由其他的遍历方式得到树的道理类似。

题目：

　　输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。

分析：

　　这不是很简单了嘛，由最后的根把输入分成三份，第一份是左孩子，第二份是右孩子，最后是树根。7、4、6、5就不能构成了，因为5是根，那么7,4,6都是右子树里面的，但是里面有小于5的4，所以不行。递归即可。

题目：

　　输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

　　例如如果树如上图，那么得到的链表是 2=8=9=……=42=45。

分析：

　　树嘛，递归就是啦。

　　如上树，先递归处理左子树（根为10的树），处理完左子树就成了一个链表了，并要能够返回左子树的最大节点16；然后递归处理右子树（根为30的树），处理完右子树也成了一个有序链表，并返回右子树的最小节点25，然后把16、20、25串起来，不就是链表了嘛？

　　这里要注意一点：在处理根为20的树时，这是不是要递归处理根为10的左子树嘛，那么这个左子树怎么知道它要返回16节点呢？同样对于20的右子树，它怎么知道返回25以和20串起来呢？所以在处理子树的时候，要传给它一个标志，表明它是父亲的左子树还是右子树。我在这里纠结好久……

代码：

1 #include 
       
          2 #include 
        
           3 #include 
         
            4 #include 
          
             5   6 using std::cin;  7 using std::cout;  8 using std::endl;  9 using std::set; 10 using std::vector; 11  12 struct Node 13 { 14     int data; 15     Node* pLC; 16     Node* pRC; 17 }; 18  19 Node* creatBSTree(vector
           
            & arr) 20 { 21     //数组里面没有元素 22     if (!arr.size()) 23         return nullptr; 24  25     Node* pNode = new Node; 26     int thisData = arr.back(); 27     pNode->data = thisData; 28  29     //只有一个元素就不要折腾了，它就是叶子节点，它没有左右孩子 30     if (1 == arr.size()) 31     { 32         pNode->pLC = pNode->pRC = nullptr; 33         return pNode; 34     } 35  36     //下面找出左半边 37     vector
            
              arrLeft; 38 for (int i = 0; i < arr.size() - 1; i++) 39 { 40 if (arr[i] < thisData) 41 arrLeft.push_back(arr[i]); 42 else 43 break; 44 } 45 46 //下面找出右半边 47 vector
             
               arrRight; 48 for (int i = arrLeft.size(); i < arr.size() - 1; i++) 49 arrRight.push_back(arr[i]); 50 51 #ifdef MY_DEBUG 52 for (int i = 0; i < arrLeft.size(); i++) 53 cout << arrLeft[i] << " "; 54 cout << endl; 55 56 for (int i = 0; i < arrRight.size(); i++) 57 cout << arrRight[i] << " "; 58 cout << endl << endl; 59 #endif 60 61 //递归处理左右孩子。arrLeft和arrRight可能为空，不要紧，在函数的开头处理了 62 pNode->pLC = creatBSTree(arrLeft); 63 pNode->pRC = creatBSTree(arrRight); 64 65 return pNode; 66 } 67 68 //中序遍历 69 void show(Node* pNode) 70 { 71 if (!pNode) 72 return; 73 74 show(pNode->pLC); 75 cout << pNode->data << " "; 76 show(pNode->pRC); 77 } 78 79 //这个函数多传了一个参数 asLeft，表明树根是树根的左子树还是右子树 80 //因为如果是左子树的话，那么要返回左子树最大节点，右子树要返回最小节点 81 //不要这个标志的话 pNode 不知道指向的树到底是父亲的左子树还是右子树 82 Node* letStraight(Node* pNode, bool asLeft) 83 { 84 //如果是空树或者只是一个叶子节点，返回自身 85 if (!pNode || (!pNode->pLC && !pNode->pRC)) 86 return pNode; 87 88 //递归处理左右子树 89 Node* pLMax = nullptr; 90 if (pNode->pLC) 91 pLMax = letStraight(pNode->pLC, true); 92 93 Node* pRMin = nullptr; 94 if (pNode->pRC) 95 pRMin = letStraight(pNode->pRC, false); 96 97 //连接左子树、右子树、树根 98 if (pLMax) 99 {100 pNode->pLC = pLMax;101 pLMax->pRC = pNode;102 }103 if (pRMin)104 {105 pNode->pRC = pRMin;106 pRMin->pLC = pNode;107 }108 109 //返回值处理，注意 asLeft 表明这棵树是它父亲的左子树还是右子树，所以它要重新找到合适的返回节点110 // pNode 的左孩子最大或右孩子最小并不是它要返回的值，它要返回的还是要看这整棵树，而不是单单看左右孩子111 Node* pRetutnNode = pNode;112 if (asLeft)113 {114 while (pRetutnNode->pRC)115 pRetutnNode = pRetutnNode->pRC;116 } 117 else118 {119 while (pRetutnNode->pLC)120 pRetutnNode = pRetutnNode->pLC;121 }122 return pRetutnNode;123 }124 125 int main(void)126 {127 vector
              
                arr;128 std::ifstream fin("src.txt");129 130 int temp;131 while (fin >> temp)132 arr.push_back(temp);133 134 Node* pHead = creatBSTree(arr);135 show(pHead);136 cout << endl;137 138 //顺序链表化并返回第一个节点139 pHead = letStraight(pHead, false);140 while (pHead)141 {142 cout << pHead->data << " ";143 pHead = pHead->pRC;144 }145 cout << endl;146 147 cin.get();148 }

View Code

结果：

转载于:https://www.cnblogs.com/jiayith/p/3935895.html

你可能感兴趣的文章