完成一个函数,输入一个二叉树,该函数输出它的镜像。
站在用户的角度思考问题,与客户深入沟通,找到秦安网站设计与秦安网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都网站设计、做网站、企业官网、英文网站、手机端网站、网站推广、国际域名空间、虚拟主机、企业邮箱。业务覆盖秦安地区。
镜像其实就是在转变成镜子当中的像,观察可以发现,根结点不变,左右结点交换顺序,然后以左右结点为根结点,其左右结点再次交换顺序,依次类推,所以可以用递归来完成;但是这样的一种方法会改变原来树的结构,如果这是我们想要的就没什么,但如果不想破坏原来树的结构,就不能改变左右结点的连接;
另外一种方法,其实可以观察,树的镜像,如果用前序遍历输出原来树的结点,如果要用相同的前序遍历输出树的镜像,会发现树的镜像用前序遍历输出,其实就是在原来的树中采用“根->右结点->左结点”的方法,不同于前序遍历“根->左结点->右结点”;
程序设计如下:
#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"< 运行程序:
运行两种方法结果是相同的。
《完》
标题名称:二叉树的镜像——19
URL标题:http://njwzjz.com/article/pihdoo.html