【考研数据结构代码题1】二叉搜索树的插入与查找

数据结构代码题1】二叉搜索树的插入与查找"/>

【考研数据结构代码题1】二叉搜索树的插入与查找

题目：请用C语言写出二叉树的二叉链表结构，并编写一个函数在二叉搜索树中可以搜索给定的关键字

难度：★

 二叉树的二叉链表结构

#include<stdio.h>
#include<stdlib.h>
//二叉树的结点结构
typedef struct Node{int data;//存放结点数据struct Node *left;//左子树指针struct Node *right;//右子树指针 
}Node;

在二叉搜索树中搜索指定关键字(递归方式)

算法思路：根据二叉排序树的特性，左<根<右，进行递归遍历查找

Node *searchNode(Node* root,int key){//递归出口if(root==NULL||root->data==key){return root;//返回存储待查找关键字的节点 } else if(key<root->data){return searchNode(root->left,key); } else {return searchNode(root->right,key); }
} 

在二叉搜索树中搜索指定关键字(非递归方式)

Node *searchNode(Node* root,int key){//若树为空或者关键字等于根结点值则结束循环 while(root!=NULL&&key!=root->data){if(key<root->data){root=root->left;} else{root=root->right;}} return root;
}

补充

1.二叉搜索树（二叉排序树、二叉查找树、BST树）的特性

二叉排序树又称为二叉查找树，它是一种特殊的二叉树。
其定义为：二叉树排序树或者是一棵空树，或者是具有如下性质的二叉树：
（1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
（2）若它的右子树非空，则右子树上所有结点的值均大于（或大于等于）根结点的值；
（3）它的左右子树也分别为二叉排序树。
这是一个递归定义。

2.二叉搜索树的插入（递归方式）

算法思路： 先判断树是否为空树，若为空树则需要将第一个插入的结点作为根结点，利用C语言中的malloc函数申请一个结点内存空间，并初始化左右子树指针为空；若不为空树则根据二叉排序树的特性：左<根<右 进行递归地插入。注意：参数列表中Node*代表数的结点指针类型，&root表示取出当前结点的地址。

//二叉搜索树的插入(递归方式)
void InsertNode(Node* &root,int key){//原始树为空则新插入的结点作为根结点 if(root==NULL){root=(Node*)malloc(sizeof(Node));root->data=key;root->left=root->right=NULL;}else if(key<root->data){InsertNode(root->left,key);}else {InsertNode(root->right,key);}
} 

3.C语言小知识点：指针类型 * 与取地址符& 的用法

参考文章

C语言中 指针变量 取地址符&的用法 *指针变量名的用法=1001.2101.3001.6650.3&utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-3-128752845-blog-105318954.235%5Ev38%5Epc_relevant_anti_t3&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-3-128752845-blog-105318954.235%5Ev38%5Epc_relevant_anti_t3&utm_relevant_index=6

C语言指针详解=%257B%2522request%255Fid%2522%253A%2522169901195416800182115107%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169901195416800182115107&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-90731422-null-null.142%5Ev96%5Epc_search_result_base2&utm_term=C%E8%AF%AD%E8%A8%80%E6%8C%87%E9%92%88&spm=1018.2226.3001.4187