二进制搜索树(BST)是一棵树,其中所有节点都遵循下述属性-
节点的左子树的键小于或等于其父节点的键。
节点的右子树的键大于其父节点的键。
因此,BST将其所有子树分为两个部分:左子树和右子树,可以定义为-
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
BST是以保持BST属性的方式排列的节点的集合,每个节点都有一个键和一个关联的值,在搜索时,将所需的键与BST中的键进行比较,如果找到,则会检索关联的值。
以下是BST的图形表示-
我们观察到,根节点键(27)在左子树上具有所有值较低的键,而在右子树上具有较高值的键。
以下是树的基本操作-
搜索 - 搜索树中的元素。
插入 - 在树中插入一个元素。
前序遍历 - 以预定顺序遍历一棵树。
中序遍历 - 以有序方式遍历树。
后序遍历 - 以后序方式遍历树。
定义一个包含一些数据的节点,并引用其左子节点和右子节点。
struct node { int data; struct node *leftChild; struct node *rightChild; };
每当要搜索元素时,都从根节点开始搜索。然后,如果数据小于键值,则在左侧子树中搜索元素。否则在右子树中搜索该元素。
链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/binary-search-tree.html
来源:LearnFk无涯教程网
struct node* search(int data){ struct node *current = root; printf("Visiting elements: "); while(current->data != data){ if(current != NULL) { printf("%d ",current->data); //go to left tree if(current->data > data){ current = current->leftChild; } //else go to right tree else { current = current->rightChild; } //not found if(current == NULL){ return NULL; } } } return current; }
每当要插入元素时,请先找到其正确位置。从根节点开始搜索,然后如果数据小于键值,则在左侧子树中搜索空位置并插入数据。否则在右侧子树中搜索空白位置并插入数据。
void insert(int data) { struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //if tree is empty if(root == NULL) { root = tempNode; } else { current = root; parent = NULL; while(1) { parent = current; //go to left of the tree if(data < parent->data) { current = current->leftChild; //insert to the left if(current == NULL) { parent->leftChild = tempNode; return; } } //go to right of the tree else { current = current->rightChild; //insert to the right if(current == NULL) { parent->rightChild = tempNode; return; } } } } }
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)