使用 C 的 DSA - 树
概述
树表示通过边连接的节点。我们将专门讨论二叉树或二叉搜索树。
二叉树是一种用于数据存储目的的特殊数据结构。二叉树有一个特殊条件，即每个节点最多可以有两个子节点。二叉树兼具有序数组和链表的优点，因为搜索速度与排序数组一样快，插入或删除操作与链表一样快。
术语
以下是与树有关的重要术语。
路径 −路径是指沿着树的边缘的节点序列。
根 − 树顶部的节点称为根。每棵树只有一个根，从根节点到任何节点只有一条路径。
父节点 − 除根节点外的任何节点都有一条向上的边指向称为父节点的节点。
子节点 − 通过向下的边连接的给定节点下方的节点称为其子节点。
叶节点 − 没有任何子节点的节点称为叶节点。
子树 − 子树表示节点的后代。
访问 −访问是指在控制节点上时检查节点的值。
遍历 − 遍历意味着按特定顺序穿过节点。
级别 − 节点的级别表示节点的代数。如果根节点在级别 0，则其下一个子节点在级别 1，其孙节点在级别 2，依此类推。
键 − 键表示节点的值，基于该值对节点执行搜索操作。
二叉搜索树表现出一种特殊的行为。节点的左子节点的值必须小于其父节点的值，而节点的右子节点的值必须大于其父节点的值。
二叉搜索树表示
我们将使用节点对象实现树并通过引用连接它们。
基本操作
以下是树的基本主要操作。
搜索 − 在树中搜索元素。
插入 − 在树中插入元素。
前序遍历 −以前序方式遍历一棵树。
中序遍历 − 以中序方式遍历一棵树。
后序遍历 − 以后序方式遍历一棵树。
节点
定义一个节点，该节点包含一些数据、对其左子节点和右子节点的引用。
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);
//转到左边的树
if(current->data > data){
current = current->leftChild;
}//否则转到右边的树
else{
current = current->rightChild;
}
//未找到
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(root == NULL){
root = tempNode;
} else {
current = root;
parent = NULL;
while(1){
parent = current;
//转到树的左边
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;
}
}
}
}
}
前序遍历
这是一个简单的三步过程。
访问根节点
遍历左子树
遍历右子树
void preOrder(struct node* root){
if(root!=NULL){
printf("%d ",root->data);
preOrder(root->leftChild);
preOrder(root->rightChild);
}
}
中序遍历
这是一个简单的三步过程。
遍历左子树
访问根节点
遍历右子树
void inOrder(struct node* root){
if(root!=NULL){
inOrder(root->leftChild);
printf("%d ",root->data);
inOrder(root->rightChild);
}
}
后序遍历
这是一个简单的三步过程。
遍历左子树
遍历右子树
访问根节点
void postOrder(struct node* root){
if(root!=NULL){
postOrder(root->leftChild);
postOrder(root->rightChild);
printf("%d ",root->data);
}
}
示例
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
struct node *root = NULL;
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(root == NULL){
root = tempNode;
} else {
current = root;
parent = NULL;
while(1){
parent = current;
//转到树的左边
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;
}
}
}
}
}
struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data){
if(current != NULL)
printf("%d ",current->data);
//转到左边的树
if(current->data > data){
current = current->leftChild;
}//否则转到右边的树
else{
current = current->rightChild;
}
//未找到
if(current == NULL){
return NULL;
}
}
return current;
}
void preOrder(struct node* root){
if(root!=NULL){
printf("%d ",root->data);
preOrder(root->leftChild);
preOrder(root->rightChild);
}
}
void inOrder(struct node* root){
if(root!=NULL){
inOrder(root->leftChild);
printf("%d ",root->data);
inOrder(root->rightChild);
}
}
void postOrder(struct node* root){
if(root!=NULL){
postOrder(root->leftChild);
postOrder(root->rightChild);
printf("%d ",root->data);
}
}
void traverse(int traversalType){
switch(traversalType){
case 1:
printf("
Preorder traversal: ");
preOrder(root);
break;
case 2:
printf("
Inorder traversal: ");
inOrder(root);
break;
case 3:
printf("
Postorder traversal: ");
postOrder(root);
break;
}
}
int main()
{
/* 11 //Level 0
*/
insert(11);
/* 11 //Level 0
* |
* |---20 //Level 1
*/
insert(20);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
*/
insert(3);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* |--42 //Level 2
*/
insert(42);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* |--42 //Level 2
* |
* |--54 //Level 3
*/
insert(54);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* 16--|--42 //Level 2
* |
* |--54 //Level 3
*/
insert(16);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* 16--|--42 //Level 2
* |
* 32--|--54 //Level 3
*/
insert(32);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* | |
* |--9 16--|--42 //Level 2
* |
* 32--|--54 //Level 3
*/
insert(9);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* | |
* |--9 16--|--42 //Level 2
* | |
* 4--| 32--|--54 //Level 3
*/
insert(4);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* | |
* |--9 16--|--42 //Level 2
* | |
* 4--|--10 32--|--54 //Level 3
*/
insert(10);
struct node * temp = search(32);
if(temp!=NULL){
printf("Element found.
");
printf("( %d )",temp->data);
printf("
");
} else {
printf("Element not found.
");
}
struct node *node1 = search(2);
if(node1!=NULL){
printf("Element found.
");
printf("( %d )",node1->data);
printf("
");
} else {
printf("Element not found.
");
}
//pre-order traversal
//root, left ,right
traverse(1);
//in-order traversal
//left, root ,right
traverse(2);
//post order traversal
//left, right, root
traverse(3);
}
输出
如果我们编译并运行上述程序，则会产生以下输出 −
Visiting elements: 11 20 42 Element found.(32) Visiting elements: 11 3 Element not found. Preorder traversal: 11 3 9 4 10 20 16 42 32 54 Inorder traversal: 3 4 9 10 11 16 20 32 42 54 Postorder traversal: 4 10 9 3 16 32 54 42 20 11
