使用 C 的 DSA - 树

更新于 2024/7/3 15:18:00

概述

树表示通过边连接的节点。我们将专门讨论二叉树或二叉搜索树。

二叉树是一种用于数据存储目的的特殊数据结构。二叉树有一个特殊条件，即每个节点最多可以有两个子节点。二叉树兼具有序数组和链表的优点，因为搜索速度与排序数组一样快，插入或删除操作与链表一样快。

术语

以下是与树有关的重要术语。

路径 −路径是指沿着树的边缘的节点序列。
根 − 树顶部的节点称为根。每棵树只有一个根，从根节点到任何节点只有一条路径。
父节点 − 除根节点外的任何节点都有一条向上的边指向称为父节点的节点。
子节点 − 通过向下的边连接的给定节点下方的节点称为其子节点。
叶节点 − 没有任何子节点的节点称为叶节点。
子树 − 子树表示节点的后代。
访问 −访问是指在控制节点上时检查节点的值。
遍历 − 遍历意味着按特定顺序穿过节点。
级别 − 节点的级别表示节点的代数。如果根节点在级别 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

❮ 使用 C 的 DSA 优先级队列使用 C 的 DSA 哈希表 ❯

使用 C 的 DSA 教程

使用 C 的 DSA 有用资源

使用 C 的 DSA - 树

概述

术语

二叉搜索树表示

基本操作

节点

搜索操作

插入操作

前序遍历

中序遍历

后序遍历

示例

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！