查找

二叉排序树的查找

#include<stdio.h>
#include<stdlib.h>

typedef struct TreeNode {
	int data;
	struct TreeNode* left;
	struct TreeNode* right;
}TreeNode;

TreeNode* createTreeNode(int value) {
	TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
	newNode->data = value;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}
//递归
TreeNode* find(TreeNode* root, int value) {
	if (root == NULL || root->data == value) {
		return root;
	}
	if (value < root->data) {
		return find(root->left, value);
	}
	else {
		return find(root->right, value);
	}
}

//非递归
TreeNode* Find(TreeNode* root, int value) {
    TreeNode* a = root;
    while (a != NULL && a->data != value) {
        if (value < a->data) {
            a = a->left;
        }
        else {
            a = a->right;
        }
    }
    return a;
}




int main() {
    // 创建一棵二叉排序树
    TreeNode* root = createTreeNode(50);
    root->left = createTreeNode(30);
    root->right = createTreeNode(70);
    root->left->left = createTreeNode(20);
    root->left->right = createTreeNode(40);
    root->right->left = createTreeNode(60);
    root->right->right = createTreeNode(80);

    int value;
    printf("Enter value to search: ");
    scanf_s("%d", &value);

    // 递归查找
    TreeNode* resultRecursive = find(root, value);
    if (resultRecursive != NULL) {
        printf("Recursive search: Value %d found!\n", value);
    }
    else {
        printf("Recursive search: Value %d not found!\n", value);
    }

    // 非递归查找
    TreeNode* resultIterative = Find(root, value);
    if (resultIterative != NULL) {
        printf("Iterative search: Value %d found!\n", value);
    }
    else {
        printf("Iterative search: Value %d not found!\n", value);
    }

    return 0;
}

二叉排序树的插入

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
    int data;                // 节点数据
    struct TreeNode *left;  // 左子节点指针
    struct TreeNode *right; // 右子节点指针
} TreeNode;

// 创建新节点的函数
TreeNode* createTreeNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 非递归插入函数
void iterativeInsert(TreeNode** root, int value) {
    TreeNode* newNode = createTreeNode(value);
    if (*root == NULL) {
        *root = newNode; // 如果树为空，直接插入到根节点
        return;
    }

    TreeNode* current = *root;
    TreeNode* parent = NULL;

    while (current != NULL) {
        parent = current;
        if (value < current->data) {
            current = current->left; // 向左子树查找
        } else {
            current = current->right; // 向右子树查找
        }
    }

    // 插入新节点
    if (value < parent->data) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }
}

// 中序遍历函数（用于验证插入是否正确）
void inOrderTraversal(TreeNode* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

 mainint() {
    TreeNode* root = NULL;

    // 插入节点
    int values[] = {50, 30, 20, 40, 70, 60, 80};
    int n = sizeof(values) / sizeof(values[0]);

    for (int i = 0; i < n; i++) {
        iterativeInsert(&root, values[i]);
    }

    printf("In-order traversal of the BST: ");
    inOrderTraversal(root);
    printf("\n");

    return 0;
}