如何在不比较节点值的情况下使用递归来实现完整的二进制树？ [英] How to implement a Complete Binary Tree using recursion without comparing the value of the node?

问题描述

public void recurInsert(BinaryTree.Node root, BinaryTree.Node newNode, int height) {
    if (newNode == null) {
        System.out.println("InsertNode is empty, please create new one");
        return;
    }
    else{
        if (height == 1) {
            if (root == null)
                return;
            else if (root.leftChild == null) {
                root.leftChild = newNode;
                System.out.println("left" + newNode.data);
            }
            else {
                root.rightChild = newNode;
                System.out.println("right" + newNode.data);
            }
        }
        else{
            if (root.leftChild != null)
                recurInsert(root.leftChild, newNode, height-1);
            //else (root.rightChild != null)
            //    recurInsert(root.rightChild, newNode, height-1);
            if (root.rightChild != null)
                recurInsert(root.rightChild, newNode, height-1);
        }
    }
}

这是我实现的代码，但它实际上插入两个相同的节点来使其平衡。任何人都可以帮助我修复错误或以其他方式实现？

This is the code I implemented, but it actually inserts two same nodes to make it balance. Can anyone help me to fix the bug or implement it in another way?

我只想使用递归来实现一个完整的二进制树的插入。说插入一个序列A，B，C，D，E，F的节点。它像根是A，其左边的孩子是B，右边的孩子是C和B的孩子是D和E，C的左边的孩子是F。

I just want to implement an insertion for a complete binary tree using recursion . Say inserting a node with a sequence A,B,C,D,E,F. It comes like root is A and its left child is B, and right child is C and B's children are D and E,and C's left child is F.

我的代码有bug但实现这个插入，使树是二进制完整的树。这就像A的孩子是B和C.但B的孩子是D，E和C的孩子是D和E，而不是F.所以希望你们可以帮助我修复错误或以另一种方式使用递归来实现。

My code has bug but implemented this insertion to make the tree is binary complete tree. It comes like A's children are B and C. But B's children is D,E and C's children is D and E as well instead of F. So hope you guys can help me to fix the bug or to implement it in another way using recursion.

幸运的是。我在Stack Overflow上看到一个类似的问题，但是我想使用递归来实现它，而不是附加数据结构。 / p>

Fortunately. I've seen a similar question posted on Stack Overflow, but I want to implement it using recursion, not with additional data structure.

推荐答案

递归方法只是隐式地从您链接到的示例中实现显式堆栈。下面的C＃程序显示了如何完成。我假设你可以轻松地转换为Java。

The recursive method just implicitly implements the explicit stack from the example you linked to. The C# program below shows how it's done. I assume you can convert to Java easily enough.

请注意， TreeInsert 方法假设 root node is not null。

Note that the TreeInsert method assumes that the root node is not null.

    public class TreeNode
    {
        public TreeNode Left;
        public TreeNode Right;
        public int Value;
    }

    private void DoStuff()
    {
        TreeNode Root = new TreeNode {Value = 0};
        for (var i = 1; i < 10; ++i)
        {
            TreeInsert(Root, new TreeNode {Value = i}, i);
        }
        PreOrder(Root, 0);
    }

    private void TreeInsert(TreeNode root, TreeNode item, int node)
    {
        int parent = (node - 1)/2;
        if (parent == 0)
        {
            if (root.Left == null)
                root.Left = item;
            else
                root.Right = item;
        }
        else
        {
            TreeNode child = ((parent%2) == 1) ? root.Left : root.Right;
            TreeInsert(child, item, parent);
        }
    }

    private void PreOrder(TreeNode root, int level)
    {
        if (root == null) return;
        Console.WriteLine("{0}{1}", new String('-', 2*level), root.Value);
        PreOrder(root.Left, level+1);
        PreOrder(root.Right, level + 1);
    }

这篇关于如何在不比较节点值的情况下使用递归来实现完整的二进制树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！