首页 > 代码库 > 15.输入一颗二元查找树，将该树转换为它的镜像， 即在转换后的二元查找树中，左子树的结点都大于右子树的结点， 用递归和循环两种方法完成树的镜像转换
15.输入一颗二元查找树，将该树转换为它的镜像， 即在转换后的二元查找树中，左子树的结点都大于右子树的结点， 用递归和循环两种方法完成树的镜像转换
转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4260432.html
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：输入一颗二元查找树，将该树转换为它的镜像， 即在转换后的二元查找树中，左子树的结点都大于右子树的结点， 用递归和循环两种方法完成树的镜像转换。
题目分析：
注：二叉排序树的中序遍历结果是升序排序的，因此将该树转换为它的镜像之后，该树的中序遍历结果应是降序排序的。
一、递归实现：
这种方式相对比较好实现，传入树的根节点，当节点不为空时，交换根节点的左右孩子，再递归交换左右子树的左右孩子。
算法实现：
1 private void exchangeRecursive(Node root){2 if(root!=null){ 3 swap(root); //交换根节点的左右子树4 exchangeRecursive(root.left); //递归交换左子树5 exchangeRecursive(root.right); //递归交换右子树6 }7 }
二、循环方式实现：
这种方式相对比较麻烦，可以用一个LinkedList的数据结构模拟栈来完成此操作。传入树的根节点root。
1.如果root为空则结束交换，否则root 进栈。
2.当栈不为空时进行如下操作：
a.弹出栈顶元节点，交换栈顶节点的左右孩子。
b.如果栈顶元素的左孩子不为空，左孩子节点进栈；如果栈顶元素的右孩子不为空，右孩子节点进栈。
算法实现：
1 private void exchangeCirculatory(Node root){ 2 if(root==null){ 3 return; 4 } 5 LinkedList<Node> nodelist = new LinkedList<Node>(); 6 System.out.println(); 7 nodelist.add(root); //根节点进栈 8 while(nodelist.size()!=0){ 9 root = nodelist.getLast(); //获得栈顶元素10 swap(root); //交换栈顶元素的左右孩子11 nodelist.removeLast();12 if(root.left!=null){ //如果栈顶元素的左孩子不为空，左孩子节点进栈13 nodelist.add(root.left);14 }15 if(root.right!=null){ //如果栈顶元素的右孩子不为空，右孩子节点进栈16 nodelist.add(root.right);17 }18 }19 }
java实现的完整源码：
1 package com.interview; 2 3 import java.util.LinkedList; 4 5 /** 6 * 题目:输入一颗二元查找树，将该树转换为它的镜像， 7 * 即在转换后的二元查找树中，左子树的结点都大于右子树的结点。 8 * 用递归和循环两种方法完成树的镜像转换。 9 * @author wjh 10 * 11 */ 12 public class _15MirrorTree { 13 14 /** 15 * @param args 16 */ 17 public static void main(String[] args) { 18 _15MirrorTree builder= new _15MirrorTree(); 19 int[] a = {56,45,47,67,35,76,22,89,91,27,11,21,19,87}; 20 Node root = null; 21 root = builder.buildTree(root, a); //1)创建二叉排序树 22 System.out.println("这是原二叉树的中序遍历结果:"); 23 builder.inOrder(root); //2)打印交换之前的二叉排序树的中序遍历结果 24 25 builder.exchangeRecursive(root); //3)递归交换二叉排序树的左右子树 26 System.out.println("\n\n这是用递归将该树转换为它的镜像的中序遍历结果:"); 27 builder.inOrder(root); //3)打印递归交换之后的二叉排序树的中序遍历结果 28 29 builder.exchangeRecursive(root); //4)将树转换回原二叉排序树 30 builder.exchangeCirculatory(root);//5)循环交换二叉排序树的左右子树 31 System.out.println("\n这是用循环将该树转换为它的镜像的中序遍历结果:"); 32 builder.inOrder(root); //5)打印循环交换之后的二叉排序树的中序遍历结果 33 } 34 35 //运用递归将该树转换为它的镜像 36 private void exchangeRecursive(Node root){ 37 if(root!=null){ 38 swap(root); //交换根节点的左右子树 39 exchangeRecursive(root.left); //递归交换左子树 40 exchangeRecursive(root.right); //递归交换右子树 41 } 42 } 43 44 //运用循环将该树转换为它的镜像,用LinkedList模拟栈来实现 45 private void exchangeCirculatory(Node root){ 46 if(root==null){ 47 return; 48 } 49 LinkedList<Node> nodelist = new LinkedList<Node>(); 50 System.out.println(); 51 nodelist.add(root); //根节点进栈 52 while(nodelist.size()!=0){ 53 root = nodelist.getLast(); //获得栈顶元素 54 swap(root); //交换栈顶元素的左右孩子 55 nodelist.removeLast(); 56 if(root.left!=null){ //如果栈顶元素的左孩子不为空，左孩子节点进栈 57 nodelist.add(root.left); 58 } 59 if(root.right!=null){ //如果栈顶元素的右孩子不为空，右孩子节点进栈 60 nodelist.add(root.right); 61 } 62 } 63 } 64 65 //交换节点的左右子树 66 private void swap(Node root){ 67 Node temp = root.left; 68 root.left = root.right; 69 root.right = temp; 70 } 71 72 //二叉树的中序遍历 73 private void inOrder(Node root){ 74 if(root==null){ 75 return; 76 } 77 else{ 78 inOrder(root.left); 79 System.out.print(root.data+" "); 80 inOrder(root.right); 81 } 82 } 83 84 //建二叉排序树 85 private Node buildTree(Node root, int[] data) { 86 for (int i = 0; i < data.length; i++) { 87 root=insert(root, data[i]); 88 } 89 return root; 90 } 91 92 //一次插入节点 93 private Node insert(Node node, int data) { 94 if (node == null) { 95 node = new Node(data,null,null); 96 }else{ 97 if(data <= node.data) { 98 node.left = insert(node.left, data); 99 } else {100 node.right = insert(node.right, data);101 }102 }103 return node;104 }105 106 //创建一个树节点类107 class Node {108 public int data;109 public Node left; //指向左孩子的指针 110 public Node right; //指向右孩子的指针 111 public Node() {112 super();113 }114 public Node(int data, Node left, Node right) {115 super();116 this.data =http://www.mamicode.com/ data;117 this.left = left;118 this.right = right;119 }120 }121 122 }
运行结果：
这是原二叉树的中序遍历结果:
11 19 21 22 27 35 45 47 56 67 76 87 89 91
这是用递归将该树转换为它的镜像的中序遍历结果:
91 89 87 76 67 56 47 45 35 27 22 21 19 11
这是用循环将该树转换为它的镜像的中序遍历结果:
91 89 87 76 67 56 47 45 35 27 22 21 19 11
15.输入一颗二元查找树，将该树转换为它的镜像， 即在转换后的二元查找树中，左子树的结点都大于右子树的结点， 用递归和循环两种方法完成树的镜像转换
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。