数据结构 ——— 查找链式二叉树中值为X的节点

目录

链式二叉树示意图

手搓一个链式二叉树

查找链式二叉树中值为X的节点 

链式二叉树示意图

手搓一个链式二叉树

代码演示：

// 数据类型
typedef int BTDataType;
 
// 二叉树节点的结构
typedef struct BinaryTreeNode
{
    BTDataType data; //每个节点的数据
 
    struct BinaryTreeNode* left; //指向左子树的指针
 
    struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;
 
// 申请新节点
BTNode* BuyNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
 
    // 判断是否申请成功
    if (newnode == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
 
    // 初始化
    newnode->data = x;
    newnode->left = NULL;
    newnode->right = NULL;
 
    return newnode;
}
 
BTNode* CreatBinaryTree()
{
    BTNode* n1 = BuyNode(1);
    assert(n1);
    BTNode* n2 = BuyNode(2);
    assert(n2);
    BTNode* n3 = BuyNode(3);
    assert(n3);
    BTNode* n4 = BuyNode(4);
    assert(n4);
    BTNode* n5 = BuyNode(5);
    assert(n5);
    BTNode* n6 = BuyNode(6);
    assert(n6);
 
    n1->left = n2;
    n1->right = n4;
    n2->left = n3;
    n4->left = n5;
    n4->right = n6;
 
    return n1;
}

查找链式二叉树中值为X的节点

代码演示：

BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data == x)
		return root;

	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1 != NULL)
		return ret1;

	BTNode* ret2 = BTreeFind(root->right, x);
	if (ret2 != NULL)
		return ret2;

	return NULL;
}

代码解析：

第一个 if 语句用于判断当前 root 是否为空，为空就返回空
然后根据前序遍历的思路，先访问根节点，也就是当前 root 是否为 指定节点
在遍历 root 的左右子树，利用 ret1 和 ret2 将返回值接收
并且判断 ret1 和 ret2 是否为空，不为空的话那么就是指定节点
如果 ret1 和 ret2 都没有返回的话，那么最后返回 NULL

代码验证：

能查找到指定节点时：

查找不到指定节点时：