复制一颗二叉树（java语言)

在一棵二叉链表表示的二叉树中，复制一颗二叉树（利用java编程语言）

我的求解方法：
首先创建一个泛型的数组，目的是为了存放二叉树（新复制）的标明空子树的先根序列，数组的长度为原来需要复制的二叉树的长度（标明空子树的先根序列）；
在原来的方法体内再次写一个方法，该方法是一个递归的方法，思想是利用先序遍历的思想，并且定义一个全局变量number，每当在数组中存放结点的时候number++，数组当前的下标往后移一位。当传入一个结点，若该结点是null，则存放在该数组中，number++；若该结点不为null，则将该结点存在数组中，number++，随后利用递归，先递归该结点的左孩子以及该数组，若此递归完成，则再递归该结点的右孩子以及该数组；
若全部遍历完成后，则返回原来的方法体中，此时数组已存在需要复制的表名空子树的先根序列，随后创建棵树，将该数组放入该构造构造方法，这样一颗树就复制完成了；
最后用先序，中序，后序分别遍历这两个二叉树，以此来验证复制的是否正确。

源代码

createTree(int treeLength)是复制二叉树的方法

    /**
    * 复制一颗二叉树，首先先构造一颗新的树
    *
    * @return    返回值
    */
   public BinaryTree createTree (int treeLength) {
       T[] copyT = (T[])new Object[treeLength];   //声明一个泛型数组
       copy(this.root, copyT);                               
       //将需要复制的二叉树的根节点以及该数组放入递归方法中去
       BinaryTree<T> copyTree = new BinaryTree<>(copyT);  
       //声明树变量，把标明空子树的先序序列放入构造方法中
       return copyTree;    //返回复制好的树对象
   }

BinaryTree的构造方法

     /**
     * 利用空子树先根序列推出根节点
     *
     * @param prelist 先根序列（泛型）
     */
    public BinaryTree(T[] prelist) {
        this.root = create(prelist);
    }
    
    /**
     * 从父母结点调用到孩子结点，再依次返回，最后再返回到树的根节点
     *
     * @param prelist 先序序列
     * @return 返回值
     */
    private BinaryNode<T> create(T[] prelist) {
        BinaryNode<T> p = null;           
        if (i < prelist.length) {
            T elem = prelist[i];
            i++;
            if (elem != null) {
                p = new BinaryNode<T>(elem);
                p.left = create(prelist);        //遍历该结点的左孩子
                p.right = create(prelist);       //遍历该结点的右孩子
            }
        }
        return p;
    }

递归调用方法copy

     /**
     * 拷贝一颗二叉树，利用先序遍历的方法
     *
     * @param node        树结点
     * @param copyT       泛型数组
     */
    public void copy (BinaryNode<T> node, T[] copyT) {
        if (node != null) {
            copyT[number] = node.data;
            number ++;
            copy(node.left, copyT);       //遍历该结点的左孩子
            copy(node.right, copyT);    //遍历该结点的右孩子
        }else if (node == null) {
            copyT[number] = null;
            number++;
        }
    }

先序遍历，中序遍历，后序遍历

    public void preOrder() {      //输出先根次序遍历序列
        preOrder(this.root);      //先根次序遍历以root结点为根的二叉树
        System.out.println();
    }

    /**
     * 先根次序遍历以p结点为根的子树，递归方法
     *
     * @param p 树结点
     */
    private void preOrder(BinaryNode<T> p) {
        if (p != null) {                                  //若二叉树不为空
            System.out.print(p.data.toString() + "");     //先访问当前的结点元素
            preOrder(p.left);                             
            //按先根次序遍历p的左子树，递归调用，参数为左孩子
            preOrder(p.right);                            
            //按先根次序遍历p的右子树，递归调用，参数为右孩子
        }
    }

    public void inOrder() {         //输出中根次序遍历序列
        inOrder(this.root);
        System.out.println();
    }

    /**
     * 中根次序遍历以p结点为根的子树，递归调用
     *
     * @param p 树结点
     */
    private void inOrder(BinaryNode<T> p) {
        if (p != null) {
            inOrder(p.left);                               
            //中根次序遍历p的左子树，递推调用，参数为左孩子
            System.out.print(p.data.toString() + "");    //访问当前的结点元素
            inOrder(p.right);                              
            //中根次序遍历p的右子树，递归调用，参数为右孩子
        }
    }

    public void postOrder() {          //输出后根次序遍历序列
        postOrder(this.root);
        System.out.println();
    }

    /**
     * 后根次序遍历p结点为根的子树，递归调用
     *
     * @param p 树结点
     */
    private void postOrder(BinaryNode<T> p) {
        if (p != null) {
            postOrder(p.left);                         
            //后根次序遍历p的左子树，递归调用，参数为左孩子
            postOrder(p.right);                        
            //后根次序遍历p的右子树，递归调用，参数为右孩子
            System.out.print(p.data.toString() + "");  //访问当前的结点元素
        }
    }

测试类

public static void main(String[] args) {
	String[] prelist_1 = {
	        "A",
	        "B", 
	        "D", 
	        null,
	        "G",
	        null, 
	        null, 
	        null,
	        "C", 
	        "E", 
	        null, 
	        null, 
	        "F",
	        "H", 
	        null, 
	        null, 
	        null
   };
   BinaryTree<String> bitee_1 = new BinaryTree<> (prelist_1);
   System.out.println("第一颗树的先序遍历：");
   bitee_1.preOrder();
   System.out.println("第一颗树的中序遍历：");
   bitee_1.inOrder();
   System.out.println("第一颗树的后序遍历：");
   bitee_1.postOrder();
   BinaryTree<String> bitee_1_copy ;
   bitee_1_copy = bitee_1.createTree(prelist_1.length);
   System.out.println("复制树的先序遍历：");
   bitee_1_copy.preOrder();
   System.out.println("复制树的中序遍历：");
   bitee_1_copy.inOrder();
   System.out.println("复制树的后序遍历：");
   bitee_1_copy.postOrder();
}

运行结果

原文链接：https://blog.csdn.net/XiaoGuYing/article/details/90480595

复制一颗二叉树（java语言)

你可能也喜欢