完成一个函数,输入一个二叉树,该函数输出它的镜像。
镜像其实就是在转变成镜子当中的像,观察可以发现,根结点不变,左右结点交换顺序,然后以左右结点为根结点,其左右结点再次交换顺序,依次类推,所以可以用递归来完成;但是这样的一种方法会改变原来树的结构,如果这是我们想要的就没什么,但如果不想破坏原来树的结构,就不能改变左右结点的连接;
另外一种方法,其实可以观察,树的镜像,如果用前序遍历输出原来树的结点,如果要用相同的前序遍历输出树的镜像,会发现树的镜像用前序遍历输出,其实就是在原来的树中采用“根->右结点->左结点”的方法,不同于前序遍历“根->左结点->右结点”;
程序设计如下:
#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"<
运行程序:
运行两种方法结果是相同的。
《完》