二叉树只在左侧添加节点。如何使其在根节点的左侧和右侧都工作？

Question

我最近开始学习数据结构和算法。我正在创建一个二叉树，它只在树的左侧添加节点。我如何创建这样一种方式，即它应该在根节点的两侧添加节点，并如下所示：

         2               
        / \       
       /   \      
      /     \     
     /       \    
     7       5       
    / \     / \   
   /   \   /   \  
   2   6   3   6   

以下是我编写的代码：

public class BinaryTreeOperations {

    BinaryTreeNode root;

    //let's start with an empty binary tree
    public BinaryTreeOperations(){
        root = null;
    }

    //let's initialize our tree with a root node
    public BinaryTreeOperations(BinaryTreeNode rootNode){
        this.root = rootNode;
    }


    public void insert(int data)
    {
        root = insertNode(root, data);
    }




    private BinaryTreeNode insertNode(BinaryTreeNode node, int data){


        //To check if the root is null then create a root node with no children
        if (node == null) {

            System.out.println("inserting root node"+ data+"\n");
            node = new BinaryTreeNode(data);
        }
        else {
            if(node.getRightChild() == null){
                System.out.println("inserting right child :"+data+"\n");
                node.rightChild=insertNode(node.rightChild, data);
            }
            else {
                System.out.println("inserting left child :"+data+"\n");
                node.leftChild = insertNode(node.leftChild, data);
            }
        }
        return node;
    }

    public int countNodes() {
        return countNodes(root);
    }

    private int countNodes(BinaryTreeNode r) {
        if (r == null)
            return 0;
        else
        {
            int count = 1;
            count += countNodes(r.getLeftChild());
            count += countNodes(r.getRightChild());
            return count;
        }
    }
}

主要类别：

public class BinaryTreeMain {
    public static void main(String args[]){

        BinaryTreeOperations binaryTreeOperations = new BinaryTreeOperations();
        binaryTreeOperations.insert(12);
        binaryTreeOperations.insert(17);
        binaryTreeOperations.insert(11);
        binaryTreeOperations.insert(21);
        binaryTreeOperations.insert(27);

        System.out.println("Total number of nodes :" + binaryTreeOperations.countNodes());

    }
}

Answer 1

例如，您可以在每个节点上存储额外的信息，比如一个布尔值，它给出了插入的方向，您可以在插入后对其进行切换。它只需要比您已经做的多几行。