數據結構-非線性結構-二叉樹

概述

/**

?* 術語

?* 根節點（root node）：位于二叉樹頂層的節點，沒有父節點。

?* 葉節點（leaf node）：沒有子節點的節點，其兩個指針均指向 None 。

?* 邊（edge）：連接兩個節點的線段，即節點引用（指針）。

?* 節點所在的層（level）：從頂至底遞增，根節點所在層為 1 。

?* 節點的度（degree）：節點的子節點的數量。在二叉樹中，度的取值范圍是 0、1、2 。

?* 二叉樹的高度（height）：從根節點到最遠葉節點所經過的邊的數量。

?* 節點的深度（depth）：從根節點到該節點所經過的邊的數量。

?* 節點的高度（height）：從距離該節點最遠的葉節點到該節點所經過的邊的數量。

?*/

/**

?* 二叉樹遍歷：【前序、中序、后序】->【遞歸遍歷實現、非遞歸遍歷實現（棧實現）】、層次遍歷（隊列實現）

?* 二叉查找樹：具有性質如下的二叉樹：對于任一結點，如果它包含的數據元素為data，

?* ? ? 那么它的左子樹（如果非空）只包含小于data的元素，并且它的右子樹（如果非空）只包含大于或等于data的元素。

?* ? ? 中序遍歷二叉查找樹將會得到從小到大排列的結點序列。

?* 二叉線索樹：通過利用原本指向空子節點（即 NULL 指針）的空間來指向前驅或后繼節點，從而在遍歷時不需要使用額外的棧或遞歸。

?* ? ? 這種結構特別適用于那些需要頻繁遍歷而修改較少的應用場景。

?* 平衡二叉樹：AVL樹、紅黑樹

?* ? ? 關鍵特性：左右子樹高度差的絕對值不超過1

?* 完全二叉樹：主要用于實現堆（最大堆、最小堆）、哈夫曼編碼

?* ? ? 關鍵特性：按層次填充，每一層（除了最后一層）都完全填滿，最后一層從左到右依次填充，沒有間斷

?* 滿二叉樹：一種特殊的二叉樹，每一層的節點都完全填滿的二叉樹

?*/

/**

?* 遞歸遍歷

?* 前序遍歷：訪問順序為“根-左-右”。即先訪問根節點，然后依次遞歸遍歷左子樹和右子樹。

?* 中序遍歷：訪問順序為“左-根-右”。即先遞歸遍歷左子樹，然后訪問根節點，最后遞歸遍歷右子樹。

?* 后序遍歷：訪問順序為“左-右-根”。即先遞歸遍歷左子樹，然后遞歸遍歷右子樹，最后訪問根節點。

?*/

/**

?* 紅黑樹

?* 紅黑樹的一些基本特性和規則：

?* 每個節點要么是紅色，要么是黑色。

?* 根節點是黑色。

?* 所有葉子節點（NIL節點，通常不顯示在圖中）都是黑色的。

?* 如果一個節點是紅色，則它的兩個子節點都是黑色（即不能有兩個連續的紅色節點）。

?* 從任一節點到其每個葉子的所有路徑都包含相同數量的黑色節點。

?*/

?// 難點：遍歷、旋轉、刪除

common.h

#pragma once#define TRUE 1
#define FALSE 0// 定義節點數據類型
#define DATA_TYPE int

二叉樹插入、刪除、遞歸遍歷

BinaryTree.h

#pragma once#include "common.h"typedef struct Node
{DATA_TYPE data;struct Node *left;struct Node *right;
} Node;// 創建一個樹結點
static Node *newBinaryTreeNode(DATA_TYPE data)
{Node *node = malloc(sizeof(Node));node->data = data;node->left = NULL;node->right = NULL;return node;
}// 旋轉節點使二叉樹平衡
Node *rotate(Node *node);// 向二叉樹插入數據 平衡化重構
Node *insertNode(Node *T, DATA_TYPE data); // 遞歸void insertNode_root(DATA_TYPE data); // 插入、從root開始
void insertData(DATA_TYPE data);           // 迭代 不會選擇平衡化// 返回二叉樹結點數
int size();// 節點高度
int height(Node *T);// 前序、中序、后序遍歷
void preOrder(Node *T);
void inOrder(Node *T);
void postOrder(Node *T);
// 逆中序打印二叉樹
void printTree(Node *T, int level);// 判斷二叉樹是否平衡
int is_balanced(Node *T);// 查找數據是否在二叉樹中
int search_val(DATA_TYPE val);// 二叉樹的root結點
Node *getRoot();// 刪除節點
Node *delete_data(DATA_TYPE val);// 清空二叉樹
void clear();void test_binary_tree();

BinaryTree.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>#include "BinaryTree.h"#define MAX_LINE 1024 // 定義二叉樹每行包含節點的最大個數 2的指數static Node *root = NULL;
static int node_size = 0;/*********************二叉樹平衡化*********************/
// 獲取平衡因子
static int balanceFactor(Node *node)
{if (node == NULL){return 0;}return height(node->left) - height(node->right);
}static Node *leftRotate(Node *node)
{Node *right = node->right;node->right = right->left;right->left = node;return right;
}static Node *rightRotate(Node *node)
{Node *left = node->left;node->left = left->right;left->right = node;return left;
}// 旋轉節點使二叉樹平衡
Node *rotate(Node *node)
{int bf = balanceFactor(node);if (bf > 1) // 左子樹{if (balanceFactor(node->left) >= 0) // 左子樹{return rightRotate(node);}else{// 先左旋再右旋node->left = leftRotate(node->left);return rightRotate(node);}}else if (bf < -1) // 右子樹{if (balanceFactor(node->right) <= 0) // 右子樹{return leftRotate(node);}else{node->right = rightRotate(node->right);return leftRotate(node);}}return node;
}
/*********************二叉樹平衡化*********************/// 插入數據，迭代方式 不會選擇平衡化
void insertData(DATA_TYPE data)
{if (root == NULL){root = malloc(sizeof(Node));root->data = data;root->left = NULL;root->right = NULL;node_size++;return;}Node *node = root;while (node){if (data < node->data){if (node->left == NULL){node->left = malloc(sizeof(Node));node->left->data = data;node->left->left = NULL;node->left->right = NULL;break;}else{node = node->left;}}else{if (node->right == NULL){node->right = malloc(sizeof(Node));node->right->data = data;node->right->left = NULL;node->right->right = NULL;break;}else{node = node->right;}}}node_size++;
}// 插入數據：遞歸方式 平衡化重構
Node *insertNode(Node *T, DATA_TYPE data)
{if (root == NULL){root = malloc(sizeof(Node));root->data = data;root->left = NULL;root->right = NULL;node_size++;return root;}if (T == NULL){Node *node = malloc(sizeof(Node));node->data = data;node->left = NULL;node->right = NULL;node_size++;return node;}if (data >= T->data){T->right = insertNode(T->right, data);}else{T->left = insertNode(T->left, data);}T = rotate(T);return T;
}void insertNode_root(DATA_TYPE data)
{root = insertNode(root, data);
}void preOrder(Node *T)
{if (T){printf("%d -> ", T->data);preOrder(T->left);preOrder(T->right);}
}
void inOrder(Node *T)
{if (T){inOrder(T->left);printf("%d -> ", T->data);inOrder(T->right);}
}
void postOrder(Node *T)
{if (T){postOrder(T->left);postOrder(T->right);printf("%d -> ", T->data);}
}// 采用逆中序和按層次縮進，是因為把打印結果按順時針方向旋轉90度就能呈現出正常的二叉樹形狀
void printTree(Node *T, int level)
{if (T){printTree(T->right, level + 1);for (int i = 0; i < level; i++){printf("     ");}printf("%d\n", T->data);printTree(T->left, level + 1);}
}int size()
{return node_size;
}int height(Node *T)
{if (T == NULL){return 0;}return __max(abs(height(T->left)), abs(height(T->right))) + 1;
}static void insertToRoot(DATA_TYPE data)
{insertNode(root, data);
}// 左右子樹高度差小于等于1
int is_balanced(Node *T)
{if (T == NULL){return TRUE; // 空樹被認為是平衡的}return abs(height(T->left) - height(T->right)) <= 1 && is_balanced(T->left) && is_balanced(T->right);
}static int search(Node *T, DATA_TYPE val)
{while (T){if (T->data == val){return TRUE;}T = (T->data > val) ? T->left : T->right;}return FALSE;
}int search_val(DATA_TYPE val)
{return search(root, val);
}Node *getRoot()
{return root;
}/*********************刪除元素*********************/
static Node *deleteLeftmost(Node *T)
{if (T->left == NULL){return T->right;}else{T->left = deleteLeftmost(T->left);return T;}
}static DATA_TYPE getLeftmost(Node *T)
{if (T->left == NULL){return T->data;}else{return getLeftmost(T->left);}
}static Node *deleteTopmost(Node *T)
{if (T->left == NULL){return T->right;}else if (T->right == NULL){return T->left;}else{T->data = getLeftmost(T->right);T->right = deleteLeftmost(T->right);return T;}
}static Node *delete(Node *T, DATA_TYPE val)
{if (T){if (T->data == val){node_size--;return deleteTopmost(T);}else if (val < T->data){T->left = delete(T->left, val);}else{T->right = delete(T->right, val);}}return T;
}Node *delete_data(DATA_TYPE val)
{return delete(root, val);
}void clear()
{free(root);root = NULL;node_size = 0;
}
/*********************刪除元素*********************/void test_binary_tree()
{printf("|***********************基礎操作***********************|\n");// insertData(4); // root// insertData(2); // root left child// insertData(1); // 2 left child// insertData(3); // 2 right child// insertData(6); // root right child// insertData(5); // 6 left child// insertData(7); // 6 right child// insertToRoot(4); // root// insertToRoot(2); // root left child// insertToRoot(1); // 2 left child// insertToRoot(3); // 2 right child// insertToRoot(6); // root right child// insertToRoot(5); // 6 left child// insertToRoot(7); // 6 right childinsertNode_root(4);insertNode_root(2);insertNode_root(1);insertNode_root(3);insertNode_root(6);insertNode_root(5);insertNode_root(7);insertNode_root(8);insertNode_root(9);insertNode_root(10);insertNode_root(11);insertNode_root(12);// insertNode_root(13);printf("逆中序打印：\n");printTree(root, 0);printf("結點數：%d\n", size());printf("是否包含[%d]:%d\n", 3, search_val(3));printf("是否包含[%d]:%d\n", 9, search_val(9));printf("前序遍歷：");preOrder(root);printf("\n");printf("中序遍歷：");inOrder(root);printf("\n");printf("后序遍歷：");postOrder(root);printf("\n");printf("逆中序打印：\n");printTree(root, 0);printf("\n");int len = height(root);printf("二叉樹高度：%d\n", len);printf("二叉樹是否平衡：%d\n", is_balanced(root));printf("測試刪除元素......");printf("\n");delete_data(4);printf("逆中序打印：\n");printTree(root, 0);printf("\n");delete_data(1);printf("逆中序打印：\n");printTree(root, 0);printf("\n");delete_data(5);printf("逆中序打印：\n");printTree(root, 0);clear();printf("\n");insertNode_root(10);insertNode_root(8);insertNode_root(15);insertNode_root(12);insertNode_root(19);insertNode_root(13); // 先右旋再左旋printf("逆中序打印：\n");printTree(root, 0);printf("|***********************平衡樹***********************|\n");
}

二叉樹層序遍歷

BinaryTreeLevelOrder.h

#include "BinaryTree.h"// 輔助隊列節點--用于層序遍歷
typedef struct QueueNode
{Node *data;struct QueueNode *next;
} QueueNode;/********************輔助隊列方法********************/
int is_queue_empty();
void enQueue(Node *T);
Node *deQueue();
/********************輔助隊列方法********************/// 二叉樹層序遍歷
DATA_TYPE **levelOrder(Node *T, int len /* 有多少層 */);void test_binary_tree_level_order();

BinaryTreeLevelOrder.c

#include <stdio.h>
#include <stdlib.h>#include "BinaryTreeLevelOrder.h"// #define col_len (height(getRoot()))// 層序遍歷輔助隊列結點數
static int queue_node_size = 0;
static QueueNode *Q = NULL;// 存儲二維數組每行有多少個列 即表示二叉樹每一層有多少個節點
static int *col;
static int col_len = 0;/********************輔助隊列方法********************/
int is_queue_empty()
{return queue_node_size == 0 || Q == NULL;
}
void enQueue(Node *T)
{if (Q == NULL){Q = malloc(sizeof(QueueNode));Q->data = T;Q->next = NULL;queue_node_size++;return;}QueueNode *q_node = Q;while (q_node->next != NULL){q_node = q_node->next;}q_node->next = malloc(sizeof(QueueNode));q_node->next->data = T;q_node->next->next = NULL;queue_node_size++;
}
Node *deQueue()
{Node *val = Q->data;Q = Q->next;queue_node_size--;return val;
}
/********************輔助隊列方法********************/DATA_TYPE **levelOrder(Node *T, int len /* 有多少層 */)
{// int (*arr)[MAX_LINE] = malloc(sizeof(*arr) * MAX_LINE);// DATA_TYPE *arr;DATA_TYPE **arr = malloc(sizeof(DATA_TYPE *) * len);col = malloc(sizeof(int) * len);enQueue(T);while (!is_queue_empty()){int curr_queue_size = queue_node_size; // 每行節點個數DATA_TYPE *per_line = malloc(sizeof(DATA_TYPE) * curr_queue_size);int index = 0;for (int i = 0; i < curr_queue_size; i++){Node *n = deQueue();per_line[index++] = n->data;// 從左到右收集節點if (n->left){enQueue(n->left);}if (n->right){enQueue(n->right);}}col[col_len] = index; // 每行有多少列arr[col_len] = per_line;col_len++;}return arr;
}void test_binary_tree_level_order()
{printf("|***********************層序遍歷***********************|\n");Node *root = getRoot();int len = height(root);DATA_TYPE **arr = levelOrder(root, len); // 鋸齒形數組 需要額外數據結構（數組或鏈表）保存每行列數// col_len 等于 len 即二叉樹的高度 即二叉樹有幾行for (int i = 0; i < col_len; i++){printf("第%d行有結點數: %d\t", i + 1, col[i]);}printf("\n");for (int i = 0; i < len; i++){int c = col[i];for (int j = 0; j < c; j++){int x = arr[i][j];printf("arr[%d][%d] = %d\t", i, j, x);}printf("\n");}
}

二叉樹非遞歸遍歷

BinaryTreeNonRecursiveOrder.h

#include "BinaryTree.h"// 輔助隊列節點--用于層序遍歷
typedef struct StackNode
{Node *data;struct StackNode *next;
} StackNode;/********************輔助隊列方法********************/
int is_stack_empty();
void push(Node *T);
Node *pop();
/********************輔助隊列方法********************/// 非遞歸前序遍歷
DATA_TYPE *non_recursive_pre_order(Node *root, int node_size);
// 非遞歸中序遍歷
DATA_TYPE *non_recursive_in_order(Node *root, int node_size);
// 非遞歸后序遍歷
DATA_TYPE *non_recursive_post_order(Node *root, int node_size);void test_binary_tree_non_recursive_order();

BinaryTreeNonRecursiveOrder.c

#include <stdio.h>
#include <stdlib.h>#include "BinaryTreeNonRecursiveOrder.h"static int stack_size = 0;
static StackNode *head = NULL;/********************輔助棧方法********************/static StackNode *newStackNode(Node *T)
{StackNode *node = malloc(sizeof(StackNode));node->data = T;node->next = NULL;return node;
}int is_stack_empty()
{return stack_size == 0;
}
void push(Node *T)
{if (head == NULL){head = newStackNode(T);stack_size++;return;}StackNode *node = newStackNode(T);node->next = head;head = node;stack_size++;
}
Node *pop()
{Node *node = head->data;head = head->next;stack_size--;return node;
}
/********************輔助棧方法********************/DATA_TYPE *non_recursive_pre_order(Node *root, int node_size)
{if (root == NULL){return NULL;}DATA_TYPE *result = malloc(sizeof(DATA_TYPE) * node_size);DATA_TYPE *p = result;while (root || !is_stack_empty()){if (root){*p++ = root->data;push(root);root = root->left;}else{root = pop();root = root->right;}}return result;
}
DATA_TYPE *non_recursive_in_order(Node *root, int node_size)
{if (root == NULL){return NULL;}DATA_TYPE *result = malloc(sizeof(DATA_TYPE) * node_size);DATA_TYPE *p = result;while (root || !is_stack_empty()){if (root){push(root);root = root->left;}else{root = pop();*p++ = root->data;root = root->right;}}return result;
}// 非遞歸后序遍歷
DATA_TYPE *non_recursive_post_order(Node *root, int node_size)
{if (root == NULL){return NULL;}DATA_TYPE *result = malloc(sizeof(DATA_TYPE) * node_size);DATA_TYPE *p = result;Node *pre = NULL;while (root || !is_stack_empty()){while (root){push(root);root = root->left;}root = pop();if (root->right == NULL || root->right == pre){*p++ = root->data;pre = root;root = NULL;}else{push(root);root = root->right;}}return result;
}static void printArray(DATA_TYPE *arr, int len)
{for (int i = 0; i < len; i++){printf("%d -> ", *arr++);}printf("\n");
}void test_binary_tree_non_recursive_order()
{printf("|***********************二叉樹非遞歸遍歷***********************|\n");Node *root = getRoot();int len = size(root); // 二叉樹結點數 用于動態內存分配時計算長度DATA_TYPE *arr = non_recursive_post_order(root, len);printf("非遞歸后序遍歷：");printArray(arr, len);arr = non_recursive_in_order(root, len);printf("非遞歸中序遍歷：");printArray(arr, len);arr = non_recursive_pre_order(root, len);printf("非遞歸前序遍歷：");printArray(arr, len);
}