大话数据结构之二叉树

本文主要是介绍大话数据结构之二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、概述

二叉树是一种非常重要的数据结构，它由节点组成，每个节点都包含三个部分：一个存储数据的元素（如整数、浮点数、字符、字符串等），一个指向左子节点的指针，以及一个指向右子节点的指针。二叉树的特点是每个节点最多有两个子节点，通常称为左子节点和右子节点。

二、常见类型

1. 普通二叉树：没有额外约束的二叉树。
2. 二叉搜索树（BST）：二叉搜索树（也称为二叉排序树、有序二叉树）是一种特殊的二叉树，它满足这样的性质：左子树的所有节点的值都小于根节点的值；右子树的所有节点的值都大于根节点的值；适用于快速查找、插入和删除操作。
3. 满二叉树：一个二叉树，如果每一个层的节点数都达到最大值，则这个二叉树就是满二叉树。也就是说，除了叶子节点外，每个节点都有两个子节点。
4. 完全二叉树（Complete Binary Tree）：每一层都被完全填充，除了最后一层，且最后一层的节点集中在左侧。
5. 平衡二叉树：

•    AVL 树：任意节点的两个子树的高度差至多为 1。
•    红黑树：通过颜色标记节点，并保持特定的平衡规则，以保证操作在对数时间内完成。

三、基本操作

1、遍历：前序遍历、中序遍历、后序遍历和层次遍历。

• 前序遍历（Pre-order）：访问根节点，遍历左子树，遍历右子树，图1的遍历顺序为：ABDHKECFIGJ。
• 中序遍历（In-order）：遍历左子树，访问根节点，遍历右子树，图1的遍历顺序为：HKDBEAIFCGJ 。
• 后序遍历（Post-order）：遍历左子树，遍历右子树，访问根节点，图1的遍历顺序为：KHDEBIFJGCA。
• 层序遍历（Level-order）：逐层访问节点，通常使用队列实现，图1的遍历顺序为：ABCDEFGHIJK。

2、插入：在二叉搜索树中，插入新的节点以保持树的排序属性。

3、删除：从二叉搜索树中删除节点，并重新组织树以维持其排序属性。

4、查找：在二叉树中查找具有特定值的节点。

#include <stdlib.h>
#include <stdio.h>typedef int TElemType;/* 二叉树的二叉链表结点结构定义 */
/* 结点结构 */
typedef struct Node_t
{/* 结点数据 */TElemType data;/* 左右孩子指针 */struct Node_t*lchild, *rchild;
} Node;/* 二叉树的前序遍历递归算法 */
void PreOrderTraverse(Node *T)
{if (T == NULL)return;/* 显示结点数据，可以更改为其他对结点操作 */printf("%d ", T->data);/* 再先序遍历左子树 */PreOrderTraverse(T->lchild);/* 最后先序遍历右子树 */PreOrderTraverse(T->rchild);
}/* 二叉树的中序遍历递归算法 */
void InOrderTraverse(Node *T)
{if (T == NULL)return;/* 中序遍历左子树 */InOrderTraverse(T->lchild);/* 显示结点数据，可以更改为其他对结点操作 */printf("%d ", T->data);/* 最后中序遍历右子树 */InOrderTraverse(T->rchild);
}/* 二叉树的后序遍历递归算法 */
void PostOrderTraverse(Node *T)
{if (T == NULL)return;/* 先后序遍历左子树 */PostOrderTraverse(T->lchild);/* 再后序遍历右子树 */PostOrderTraverse(T->rchild);/* 显示结点数据，可以更改为其他对结点操作 */printf("%d ", T->data);
}// 查找节点  
Node* search(Node* root, int key) 
{  if (root == NULL || root->data == key) {  return root;  }  if (key < root->data) {  return search(root->lchild, key);  } else {  return search(root->rchild, key);  }  
}// 查找最小节点（用于删除有两个子节点的节点时替换）  
Node* minValueNode(Node* node) 
{  Node* current = node;  while (current->lchild != NULL) {  current = current->lchild;  }  return current;  
}  // 删除节点  
Node* deleteNode(Node* root, int key) 
{  if (root == NULL) return root;  if (key < root->data) {  root->lchild = deleteNode(root->lchild, key);  } else if (key > root->data) {  root->rchild = deleteNode(root->rchild, key);  } else {  // 节点有两个子节点  if (root->lchild != NULL && root->rchild != NULL) {  Node* temp = minValueNode(root->rchild);  root->data = temp->data;  root->rchild = deleteNode(root->rchild, temp->data);  }  // 节点有一个子节点或没有子节点  else {  Node* temp = root->lchild ? root->lchild : root->rchild;  free(root);  return temp;  }  }  return root;  
}/* 插入节点到二叉搜索树 */
Node *insert(Node *node, TElemType value)
{if(node == NULL){	node = (Node *)malloc(sizeof(Node));node->data = value;node->lchild = NULL;node->rchild = NULL;return node;}if(value < node->data)node->lchild = insert(node->lchild, value);elsenode->rchild = insert(node->rchild, value);return node;
}int main(int argc, char *argv[])
{Node *root = NULL;root = insert(root, 50);insert(root, 30);insert(root, 20);insert(root, 40);insert(root, 70);insert(root, 60);insert(root, 80);//前序遍历printf("front:");PreOrderTraverse(root);printf("\n");//中序遍历printf("mid:");InOrderTraverse(root);printf("\n");//后序遍历printf("back:");PostOrderTraverse(root);printf("\n");//查找const Node *node = search(root, 80);if(node != NULL){printf("search:%d\n", node->data);} //删除deleteNode(root, 20);deleteNode(root, 70);//中序遍历printf("mid:");InOrderTraverse(root);printf("\n");return 0;
}

qq群交流：698593923

觉得有帮助的话，打赏一下呗。。

           

这篇关于大话数据结构之二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---