如何反转（镜像）递归二叉搜索树的子树

Question

我正在尝试在 Java 中编写二叉搜索树。我的 BST 采用许多 "keywords" 并使用大多数递归方法将它们插入到树中。

不幸的是，它似乎在向后添加它们，E.x。右侧的字母 (a-c...) 比左侧 (x-z...) 大。

我不知道如何正确地反转逻辑。

这是我的插入代码：

  /**
 * This method creates a new record for theFileData.
 * This is a recursive insertion method, that adds recordToAdd to the list of records
 * for the node associated with theKeyword.
 * 
 * If there is no keyword, create a new Node for it.
 * 
 * @param theKeyword keyword to associate with new record.
 * @param theFileData file data to associate with new record.
 */
public void insert(String theKeyword, FileData fd) {
    if (fd == null) {
        throw new NullPointerException("Invalid file data.");
    }
    if (theKeyword == null) {
        throw new NullPointerException("Invalid keyword.");
    }
    theKeyword = theKeyword.toLowerCase();

    Record recordToAdd = new Record(fd.id, fd.author, fd.title, null);

    // step one is to find the node with keyword theKeyword. That will give us the correct list to insert into.
    if (root == null) {
        /*
         * If the tree is currently empty, we create a new node as root.
         * This node than has the record added to it's records list.
         */
        Node newNode = new Node(theKeyword);
        newNode.update(recordToAdd);
        root = newNode;
    } else if (!contains(theKeyword)) {
        Node newNode = new Node(theKeyword);
        newNode.update(recordToAdd);
        insert(root, newNode);
    } else {
        Node target = find(theKeyword, root);
        target.update(recordToAdd);
    }
}

/**
 * This recursive insertion helper method allows us to quickly and easily add a new Node object
 * to our BST.
 */
private Node insert(Node theParent, Node theNode) {
    if (theParent == null) {
        return theNode;
    } else if (theNode.keyword.compareTo(theParent.keyword) < 0) {
        theParent.right = insert(theParent.right, theNode);
    } else if (theNode.keyword.compareTo(theParent.keyword) > 0) {
        theParent.left = insert(theParent.left, theNode);
    }
    return theParent;
}

/**
 * This helper method searches for a given keyword, returning the node when found.
 * 
 * @return Node containing the keyword you are looking for. Else null.
 */
private Node find(String keyword, Node root) {
    if (keyword == null) {
        throw new IllegalArgumentException("Invalid keyword.");
    }

    if (root == null) {
        return null;
    }
    keyword = keyword.toLowerCase();
    if (keyword.compareTo(root.keyword) > 0) {
        return find(keyword, root.left);
    }
    if (keyword.compareTo(root.keyword) < 0) {
        return find(keyword, root.right);
    }
    return root;
}

/**
 * This method simply calls the find helper method. If find returns null, we know the value does not exist.
 * 
 * @param keyword keyword to search for.
 * @return true or false depending on if the keyword exists in the BST.
 */
public boolean contains(String keyword) {

    keyword = keyword.toLowerCase();

    if (find(keyword, root) != null) {
        return true; // if the keyword exists.
    }
    return false;
}

强文本

这是树的图示：

| | |--------斑点
| |--------建筑物
| | | |--------因果关系
| | | | |--------分类规则
| | |--------聚类
|-------基于内容
| |--------数据挖掘
数据库
| | |-------距离测量
| | | |-------图像显示
| |--------图像管理
|--------图像检索
| | | |-------图像堆栈
| | | | | |--------索引
| | | | | | | |--------信息检索
| | | | | | |--------基于实例
| | | | | | | |--------基于实例
| | | | |--------知识
| | |--------行数
| |--------匹配
| | | | | |--------多媒体
| | | | | | |--------神经网络
| | | | |-------姿势
| | | |--------修剪
| | | | |------查询
| | |--------实例查询
| | | | |--------查询树
| | | |--------识别
| | | | | |------基于区域
| | | | | | |--------关系
| | | | |--------搜索
| | | | | |--------相似度
| | | | | | | |--------空间
| | | | | | | | |--------时间
| | | | | | | | | |--------时间相关
| | | | | | |--------三角不等式
| | | | | | | |--------加权

斑点应该在左边，匹配应该在右边，等等

Answer 1

在这个方法中：

private Node insert(Node theParent, Node theNode) {
    if (theParent == null) {
        return theNode;
    } else if (theNode.keyword.compareTo(theParent.keyword) < 0) {
        theParent.right = insert(theParent.right, theNode);
    } else if (theNode.keyword.compareTo(theParent.keyword) > 0) {
        theParent.left = insert(theParent.left, theNode);
    }
    return theParent;
}

当您要插入的节点在字典序上小于父节点时，您将向右插入。以 'a' 开头的单词在字典上小于以 'z' 开头的单词，因此您得到的正是代码建议的内容。

要修改这个，只需翻转所有比较即可。

Answer 2

在您的代码中，反转 < 和 >。这样代码就变成了

private Node insert(Node theParent, Node theNode) {
if (theParent == null) {
    return theNode;
} else if (theNode.keyword.compareTo(theParent.keyword) > 0) {
    theParent.right = insert(theParent.right, theNode);
} else if (theNode.keyword.compareTo(theParent.keyword) < 0) {
    theParent.left = insert(theParent.left, theNode);
}
    return theParent;
}

如何反转（镜像）递归二叉搜索树的子树

How to reverse (mirror) a recursive binary search tree's subtrees

algorithm

tree

recursion

binary-search-tree

data-structures