问题：

如何将单节点树合并为大型树

郦楷

2023-03-14

我有一个项目是“从tree.java程序（清单8.1）开始，修改它，从一串字母（如a、B等）创建一个二叉树”由用户输入。每个字母都将显示在自己的节点中。构建树，使包含字母的所有节点都是叶子。父节点可以包含一些非字母符号，如。确保每个父节点正好有两个子节点。如果树不平衡，不要担心。”这本书给了我们一个如何开始的提示。“一种开始的方法是制作一组树（一组不相连的树被称为森林）将用户键入的每个字母放入一个节点中。将这些节点中的每一个放在一棵树中，它就是根。现在将所有这些单节点树放入数组中。首先创建一棵新树，根上有两棵单节点树作为其子树。然后继续将数组中的一个节点树添加到这个较大的树中。如果这是一棵不平衡的树，不要担心。”

 import java.io.*;
 import java.util.*;

 class Node 
 {
  public String iData; // data item (key)
  public Node leftChild; // this node’s left child
  public Node rightChild; // this node’s right child
  public void displayNode() // display ourself
  {
        System.out.print('{');
    System.out.print(iData);
    System.out.print("} ");
  }
  } // end class Node


class Tree
{
private Node root; // first node of tree
public void setNode(Node newNode)
{root = newNode;}
public Node getNode()
{return root;}
// -------------------------------------------------------------
public Tree() // constructor
{ root = null; } // no nodes in tree yet
// -------------------------------------------------------------


 public void traverse(int traverseType)
{
switch(traverseType)
{
    case 1: System.out.print("nPreorder traversal: ");
    preOrder(root);
    break;
    case 2: System.out.print("nInorder traversal: ");
    inOrder(root);
    break;
    case 3: System.out.print("nPostorder traversal: ");
    postOrder(root);
    break;
}
System.out.println();
}
private void preOrder(Node localRoot)
 {
if(localRoot != null)
{
    System.out.print(localRoot.iData + " ");
    preOrder(localRoot.leftChild);
    preOrder(localRoot.rightChild);
}
}

// -------------------------------------------------------------
private void inOrder(Node localRoot)
{
if(localRoot != null)
{
    inOrder(localRoot.leftChild);
    System.out.print(localRoot.iData + " ");
    inOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void postOrder(Node localRoot)
 {
if(localRoot != null)
{
    postOrder(localRoot.leftChild);
    postOrder(localRoot.rightChild);
    System.out.print(localRoot.iData + " ");
}
 }
// -------------------------------------------------------------
 public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
    Stack localStack = new Stack();
    isRowEmpty = true;
    for(int j=0; j<nBlanks; j++)
    System.out.print(' ');
    while(globalStack.isEmpty()==false)
    {
        Node temp = (Node)globalStack.pop();
        if(temp != null)
    {
            System.out.print(temp.iData);
            localStack.push(temp.leftChild);
            localStack.push(temp.rightChild);
            if(temp.leftChild != null ||
                    temp.rightChild != null)
                isRowEmpty = false;
    }
    else
    {
        System.out.print("--");
        localStack.push(null);
        localStack.push(null);
    }
    for(int j=0; j<nBlanks*2-2; j++)
        System.out.print(' ');
    } // end while globalStack not empty
    System.out.println();
    nBlanks /= 2;
    while(localStack.isEmpty()==false)
        globalStack.push( localStack.pop() );
    } // end while isRowEmpty is false
    System.out.println(
    "......................................................");
} // end displayTree()
    // -------------------------------------------------------------

 }       


 public class Leaves 
{
    //function used to enter the single node trees into a larger tree
public static void enterLetters(Node localRoot, Tree[] nodeTree, int i)
{
    if(localRoot != null && i == nodeTree.length)
    {
    if(nodeTree.length == i - 1)
    {
        localRoot.leftChild = nodeTree[i].getNode();
        localRoot.rightChild = nodeTree[i + 1].getNode();
        enterLetters(localRoot.leftChild, nodeTree, i + 1);
    }
    else
    {
        Node plusNode = new Node();
        plusNode.iData = "+";
        localRoot.leftChild = plusNode;
        localRoot.rightChild = nodeTree[i].getNode();
        enterLetters(localRoot.leftChild, nodeTree, i + 1);
    }
}
}

public static void main(String[] args) 
{
     Tree[] forest = new Tree[10];

     Scanner sc = new Scanner(System.in);

     for(int i = 0; i < 10; i++)
     {
        String letter;
        forest[i] = new Tree();
        System.out.println("Enter a letter: ");
        letter = sc.nextLine();

        Node newNode = new Node();
        newNode.iData = letter;
        forest[i].setNode(newNode);

    }

    Tree letterTree = new Tree();
    Node firstNode = new Node();
    firstNode.iData = "+";
    letterTree.setNode(firstNode);

    enterLetters(letterTree.getNode(), forest, 0);

    letterTree.displayTree();
}
}

我的问题是试图将单节点树数组放入更大的树中。我尝试创建一个递归函数，但当我显示较大的树时，它只显示第一个节点，就好像函数enterLeaves从来没有完成它的工作一样。

共有3个答案

樊杰

2023-03-14

if(localRoot != null && i == nodeTree.length -1)

如果不从节点树长度中减去一个，则在最后一个父节点下将有一个重复的子节点，其中包含两个子节点

侯向文

2023-03-14

以下是我想出的有效方法：

Node.java

/** Represents a node in a binary tree data structure */
public class Node {
    private char letter;
    private Node leftChild;
    private Node rightChild;

    public Node(char letter) {
        this.letter = letter;
    }

    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }

    public Node getRightChild() {
        return rightChild;
    }

    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }

    public Node getLeftChild() {
        return leftChild;
    }

    /** Returns a String representation of this node. */
    @Override
    public String toString() {
        return "" + letter;
    }
}

Tree.java

import java.util.Stack;

/**
 * A binary tree
 */
public class Tree {
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    public void addToLeft(Node node) {
        root.setLeftChild(node);
    }

    public void addToRight(Node node) {
        root.setRightChild(node);
    }

    public Node getRoot() {
        return root;
    }

    public void displayTree() {
        Stack<Node> globalStack = new Stack<>();
        globalStack.push(root);
        int nBlanks = 32;
        boolean isRowEmpty = false;
        System.out.println(
                "......................................................");
        while (!isRowEmpty) {
            Stack<Node> localStack = new Stack<>();
            isRowEmpty = true;

            for (int j = 0; j < nBlanks; j++)
                System.out.print(' ');

            while (!globalStack.isEmpty()) {
                Node temp = (Node) globalStack.pop();
                if (temp != null) {
                    System.out.print(temp);
                    localStack.push(temp.getLeftChild());
                    localStack.push(temp.getRightChild());

                    if (temp.getLeftChild() != null ||
                            temp.getRightChild() != null)
                        isRowEmpty = false;
                } else {
                    System.out.print("--");
                    localStack.push(null);
                    localStack.push(null);
                }
                for (int j = 0; j < nBlanks * 2 - 2; j++)
                    System.out.print(' ');
            }  // end while globalStack not empty
            System.out.println();
            nBlanks /= 2;
            while (!localStack.isEmpty())
                globalStack.push(localStack.pop());
        }  // end while isRowEmpty is false
        System.out.println(
                "......................................................");
    }
}

森林JAVA

/**
 * A collection of OneNodeTrees combined together in one tree
 */
public class Forest {
    private Tree[] forest;
    private int forestIndex;

    public Forest(int numTrees) {
        forest = new Tree[numTrees];
        forestIndex = 0;
    }

    public boolean add(Tree tree) {
        if(forestIndex < forest.length) {
            forest[forestIndex++] = tree;
            return true;
        } else {
            return false;
        }
    }

    public Tree createMainTree() {
        Tree firstTree = new Tree();
        firstTree.setRoot(new Node('+'));
        firstTree.addToLeft(forest[0].getRoot());
        firstTree.addToRight(forest[1].getRoot());
        forest[1] = firstTree;

        int mainTreeIndex = 0;
        Tree tempTree;
        for(mainTreeIndex = 2; mainTreeIndex < forest.length; mainTreeIndex++) {
            tempTree = new Tree();
            tempTree.setRoot(new Node('+'));
            tempTree.addToLeft(forest[mainTreeIndex - 1].getRoot());
            tempTree.addToRight(forest[mainTreeIndex].getRoot());
            forest[mainTreeIndex] = tempTree;
        }

        return forest[mainTreeIndex - 1];
    }

    public static void main(String[] args) {
        final int numberOfTrees = 6;
        Forest forest = new Forest(numberOfTrees);

        // Add characters starting from A which has ASCII value 65
        int charLimit = 65 + numberOfTrees;
        for(int i = 65; i < charLimit; i++) {
            // Make new node.
            Node newNode = new Node((char) i);
            // Add that node to Tree as a root.
            Tree newTree = new Tree();
            newTree.setRoot(newNode);
            // And add that one-node tree to forest(array)
            forest.add(newTree);
        }

        Tree mainTree = forest.createMainTree();
        mainTree.displayTree();
    }
}

上官自明

2023-03-14

这不可能是正确的：

public static void enterLetters(Node localRoot, Tree[] nodeTree, int i) {
    if (localRoot != null && i == nodeTree.length) {
        if (nodeTree.length == i - 1) {
            localRoot.leftChild = nodeTree[i].getNode();
            localRoot.rightChild = nodeTree[i + 1].getNode();
            enterLetters(localRoot.leftChild, nodeTree, i + 1);
        } else {
            Node plusNode = new Node();
            plusNode.iData = "+";
            localRoot.leftChild = plusNode;
            localRoot.rightChild = nodeTree[i].getNode();
            enterLetters(localRoot.leftChild, nodeTree, i + 1);
        }
    }
}

输入此方法时：localRoot！=null、i==0和nodeTree。长度=10

所以if语句失败了。我猜if语句应该是：

    if (localRoot != null && i < nodeTree.length)

另外，我很确定你的第二个if语句也不正确；我认为应该是这样。

        if (nodeTree.length-2 == i) {
            localRoot.leftChild = nodeTree[i].getNode();
            localRoot.rightChild = nodeTree[i + 1].getNode();
            return;
        }

而不是：

        if (nodeTree.length == i - 1) {
            localRoot.leftChild = nodeTree[i].getNode();
            localRoot.rightChild = nodeTree[i + 1].getNode();
            enterLetters(localRoot.leftChild, nodeTree, i + 1);
        }

当剩下两个节点（nodeTree.length-2==i）需要处理时，您希望停止，然后返回，而不是输入剩余的字母。

类似资料：

合并两个二叉树节点和

我正在研究合并两个二叉树的问题(https://www.geeksforgeeks.org/merge-two-binary-trees-node-sum/)我很难理解一些递归。为什么要将递归语句设置为和？当你这样做的时候，是否等于两个值？我只是不确定为什么我们要将递归语句设置为t1.leftt1.right'
XSLT-将子节点合并为一个

不具有任何3个属性值(TargetInteresting1、TargetInteresting2、TargetInteresting3)的节点应不加修改地复制到最终结果中。我正在寻找一个使用XSLT2.0的解决方案。我不知道从何说起，我还不太习惯xslt：-（
二叉搜索树查找最大节点并将其删除（泛型类）

正如标题所说，我目前正试图找到BST的最大节点，我想删除它。我有方法来查找最大节点和删除节点准备从我的算法书，但我不知道如何在主方法中使用它们。我有一个方法，可以通过输入一个数字插入节点，例如8，这将打印一个级别有序的树：4, 2, 6, 1, 3, 5, 7其中4是根。我希望能够找到最后一个节点并删除它。到目前为止，我有这些方法：我的主要方法是这样的：我希望能够自由插入任何节点，并且树仍然能
树、树节点父节点和子节点

如果我没弄错的话，树通常是一个列表，其中的元素按特定顺序排列。孩子们不在他们自己的子列表中，他们都在同一个列表中。所以，我试图创建一个Tree类，其中包含TreeNodes（类）使用Tree类中的List。我如何跟踪父母/孩子/叶子？如果父母“父母1”，有两个孩子“孩子A”和“孩子B”，我如何将他们联系在一起？
如何通过只保留所有树共有的节点来合并多棵树

所以我有两到三棵树，它们是在执行一些代码时生成的。此树的每个节点都有一个属性，即它至少有0个子节点，最多有8个子节点。我猜你可以得到这样一个完整的树的图片，在0级有一个根节点。在1级8个节点在2级64个节点，以此类推。父节点的每个子节点的编号从0到7，我在java中将其存储为字节整数类型，顺便说一句，我在java中实现了这一点。现在我需要合并这两到三棵树，我已经生成，我这样做的水平明智完全不考虑
将XML节点合并为一个逗号分隔的节点

我有一个XML结构，我想用XSLT转换它。然而，使其尽可能动态化是很重要的。我相信制作一个feed的副本是可能的，然后只需选择一个特定的部分并对其进行转换。当一个新节点添加到原始XML中时，不需要在XSLT中进行任何更改，就可以将这个新节点包含在XSLT的输出中。原始XML示例：

如何将单节点树合并为大型树

共有3个答案

相关问答

相关文章

相关阅读

相关工具

相关文档