algorithm - 如何反转(镜像)递归二叉搜索树的子树

Question

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

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

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

这是我的插入代码:

  /**
 * 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;
}

强文本

这是树的图形表示:

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

Blob 应该在左边，匹配应该在右边，等等。

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;
}