模拟实现一个简单的中英互译字典——二叉搜索树的应用KV模型

模拟实现一个简单的中英互译字典——二叉搜索树的应用KV模型

模拟实现一个简单的中英互译字典

    请模拟实现一个简单的中英互译字典，要求能实现简单的查找，插入新词以及删除操作；例如

BinaryTree.h

#pragma once#include <stdio.h>
#include <stdlib.h>//二叉搜索树的应用
//1. 请模拟实现一个简单的中英互译的字典typedef char* KeyType;
typedef char* ValueType;typedef struct BSTreeNode
{struct BSTreeNode* _left;struct BSTreeNode* _right;KeyType _key;ValueType _value;
}BSTreeNode;BSTreeNode* BuyBSTreeNode(KeyType key, ValueType value)
{BSTreeNode* tree = (BSTreeNode*)malloc(sizeof(BSTreeNode));tree->_key = key;tree->_value = value;tree->_left = NULL;tree->_right = NULL;return tree;
}int BSTreeInsertR(BSTreeNode** ppTree, KeyType key, ValueType value)
{if (*ppTree == NULL){*ppTree = BuyBSTreeNode(key, value);return 0;}if (key < (*ppTree)->_key)BSTreeInsertR(&(*ppTree)->_left,key,value);if (key >(*ppTree)->_key)BSTreeInsertR(&(*ppTree)->_right, key, value);elsereturn -1;
}BSTreeNode* BSTreeFindR(BSTreeNode* tree, KeyType key)
{if (tree == NULL)return NULL;if (key < tree->_key)return BSTreeFindR(tree->_left,key);if (key > tree->_key)return BSTreeFindR(tree->_right, key);elsereturn tree;
}int BSTreeRemoveR(BSTreeNode** ppTree,KeyType key)
{if (*ppTree == NULL)return -1;if (key < (*ppTree)->_key)return BSTreeRemoveR(&(*ppTree)->_left,key);if (key >(*ppTree)->_key)return BSTreeRemoveR(&(*ppTree)->_left, key);else{BSTreeNode* cur = *ppTree;if (cur->_left == NULL)*ppTree = cur->_right;if (cur->_right == NULL)*ppTree = cur->_left;else{BSTreeNode* sub = (*ppTree)->_right;while (sub->_left){sub = sub->_left;}(*ppTree)->_key = sub->_key;(*ppTree)->_value = sub->_value;sub = sub->_right;}return 0;}
}void TestBSTree()
{BSTreeNode* tree = NULL;BSTreeInsertR(&tree, "tree", "树");BSTreeInsertR(&tree, "sort", "排序");BSTreeInsertR(&tree, "binary", "二分");BSTreeInsertR(&tree, "return", "返回");BSTreeInsertR(&tree, "hash", "哈希");BSTreeInsertR(&tree, "list", "链表");printf("tree: %sn", BSTreeFindR(tree, "tree")->_value);printf("return: %sn", BSTreeFindR(tree, "return")->_value);printf("hash: %sn", BSTreeFindR(tree, "hash")->_value);printf("list: %sn", BSTreeFindR(tree, "list")->_value);
};

test.c

#include <windows.h>
#include "BinaryTree.h"int main(void)
{TestBSTree();system("pause");return 0;
}

测试结果：