数据结构&算法 二叉搜索树
-
二叉搜索树
二叉搜索树(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; };
-
搜索操作
每当要搜索元素时,都从根节点开始搜索。然后,如果数据小于键值,则在左侧子树中搜索元素。否则,在右子树中搜索该元素。每个节点遵循相同的算法。算法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; } } } } }
遍历示例:》》》》》》