完成一个函数,输入一个二叉树,该函数输出它的镜像。
镜像其实就是在转变成镜子当中的像,观察可以发现,根结点不变,左右结点交换顺序,然后以左右结点为根结点,其左右结点再次交换顺序,依次类推,所以可以用递归来完成;但是这样的一种方法会改变原来树的结构,如果这是我们想要的就没什么,但如果不想破坏原来树的结构,就不能改变左右结点的连接;
另外一种方法,其实可以观察,树的镜像,如果用前序遍历输出原来树的结点,如果要用相同的前序遍历输出树的镜像,会发现树的镜像用前序遍历输出,其实就是在原来的树中采用“根->右结点->左结点”的方法,不同于前序遍历“根->左结点->右结点”;
程序设计如下:
#include#include using namespace std; struct BinaryTreeNode { int _val; BinaryTreeNode* _Lchild; BinaryTreeNode* _Rchild; BinaryTreeNode(int val) :_val(val) ,_Lchild(NULL) ,_Rchild(NULL) {} }; BinaryTreeNode* _CreatTree(const int *arr, size_t& index, size_t size) { if((arr[index] != '#') && (index < size)) { BinaryTreeNode *root = new BinaryTreeNode(arr[index]); root->_Lchild = _CreatTree(arr, ++index, size); root->_Rchild = _CreatTree(arr, ++index, size); return root; } else return NULL; }; BinaryTreeNode* CreatTree(const int *arr, size_t size) { assert(arr && size); size_t index = 0; return _CreatTree(arr, index, size); } void PrevOrder(BinaryTreeNode *root) { if(root != NULL) { cout< _val<<"->"; PrevOrder(root->_Lchild); PrevOrder(root->_Rchild); } } void DestoryTree(BinaryTreeNode *root) { if(root != NULL) { delete root; DestoryTree(root->_Lchild); DestoryTree(root->_Rchild); } } //方法一: //void ImageTree(BinaryTreeNode *root) //{ // if(root == NULL) // return; // BinaryTreeNode* tmp = root->_Lchild; // root->_Lchild = root->_Rchild; // root->_Rchild = tmp; // // ImageTree(root->_Lchild); // ImageTree(root->_Rchild); //} //方法二: void ImageTree(BinaryTreeNode *root) { if(root != NULL) { cout< _val<<"->"; ImageTree(root->_Rchild); ImageTree(root->_Lchild); } } int main() { int arr[] = {1,2,4,'#','#',5,'#','#',3,6,'#','#',7,'#','#'}; BinaryTreeNode *root = CreatTree(arr, sizeof(arr)/sizeof(arr[0])); PrevOrder(root); cout<<"NULL"< 运行程序:
运行两种方法结果是相同的。
《完》
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
标题名称:二叉树的镜像——19-创新互联
文章网址:http://bjjierui.cn/article/doggec.html