моя контактная информация
Почтамезофия@protonmail.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
дерево - этонелинейный Структура данных, представляющая собой набор иерархических связей, состоящих из n (n>=0) ограниченных узлов.ПучокЕго называют деревом, потому что оно похоже на перевернутое дерево, а это значит, что его корни направлены вверх, а листья — вниз.
- Корневой узел: Корневой узел не имеет узла-предшественника.
- За исключением корневого узла, остальные узлы разбиваются на поддеревья, имеющие структуру, аналогичную структуре дерева. Корневой узел каждого поддерева имеет одного и только одного предшественника и может иметь 0 или более преемников.
- Следовательно, дереворекурсивное определениеиз.
Древовидная структура сложнее линейной таблицы, ее сложнее хранить и представлять.Необходимо сохранить как диапазон значений, так и связь между узлами и узлами.На самом деле существует множество способов представления деревьев, например:Обозначение родителя, обозначение дочернего элемента, обозначение дочернего родителя и обозначение дочернего братаждать.
В процессе внедрения следующей структуры хранения в качестве примера мы возьмем следующее дерево.
Мы предполагаем, что узлы дерева хранятся в множестве непрерывных пространств, и в то же времяК каждому узлу прикреплен индикатор, указывающий положение его родительского узла в связанном списке. . Другими словами, каждый узел не только знает, кто он, но и знает, где находятся его родители.
Среди них данные — это поле данных, в котором хранится информация данных узла. Родитель — это поле указателя, в котором хранятся индексы родителей узла в массиве.
Ниже приведен код определения структуры узла для нашего родительского представления.
/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType; //树结点的数据类型，目前暂定为整型
/*结点结构*/
typedef struct TreeNode
{
TElemType data; //结点数据
int parent; //双亲位置
}TreeNode;
/*树结构*/
typedef struct
{
TreeNode nodes[MAX_TREE_SIZE]; //结点数组
int r, n; //根的位置和结点数
}PTree;
При такой структуре хранения мы можем легко найти его родительские узлы по родительскому указателю используемого узла.Временная сложность равна 0(1) , пока родительский элемент не станет равен -1, что указывает на то, что корень узла дерева найден. Но если мы хотим знать, что такое дочерние элементы узла, извините, пожалуйста, просмотрите всю структуру.
Только что мы изучали структуру хранения дерева с точки зрения родителей и ребенка. Что, если мы посмотрим на братьев узлов дерева? Конечно, для такой иерархической структуры, как дерево, мы изучаем только узлы? братья узлов Это невозможно. После наблюдения мы обнаружили, что для любого дерева первый дочерний элемент его узла уникален, если он существует, и его правый брат также уникален, если он существует. Поэтому мы устанавливаем два указателя, указывающие на первого дочернего элемента узла и правого брата узла.
/*树的孩子兄弟表示法结构定义*/
typedef struct TreeNode
{
TElemtype data;
struct TreeNode *firstchild, *rightsib;
} TreeNode,* pTreeNode;
Бинарное дерево — это конечный набор узлов, который:
- или пустой
- Он состоит из корневого узла и двух двоичных деревьев, также известных как левое поддерево и правое поддерево.
Как видно из картинки выше:
- В двоичном дереве нет узла со степенью больше 2.
- Поддеревья двоичного дерева можно разделить на левое и правое поддеревья, причем порядок не может быть изменен на противоположный, поэтому двоичное дерево имеет видупорядоченное дерево
Примечание. Любое двоичное дерево состоит из следующих ситуаций:
Двоичные деревья обычно можно хранить с использованием двух структур:Последовательная структура, цепная структура.
2. Хранение цепи
Обычные бинарные деревья не подходят для хранения в массивах, так как может оказаться много ненужного пространства.иПолные двоичные деревья больше подходят для хранения последовательной структуры. .На самом деле мы обычноКуча (двоичное дерево) использует для хранения массив последовательных структур., следует отметить, что куча здесь и куча в адресном пространстве виртуального процесса операционной системы — это две разные вещи: одна — это структура данных, а другая — сегментация области, которая управляет памятью в операционной системе.
Подробнее о конкретной реализации и применении см.:[Структура данных] 08. Куча и приложения кучи
Самый простой способ изучить бинарную древовидную структуру — пройти по ней.так называемыеОбход бинарного дерева (Trversal) заключается в последовательном выполнении соответствующих операций над узлами бинарного дерева по определенным правилам, причем каждый узел обрабатывается только один раз. . Операции, выполняемые при доступе к узлам, зависят от конкретной проблемы приложения. Обход — одна из наиболее важных операций над двоичным деревом, а также основа для других операций над двоичным деревом.
//根 左子树 右子树
void PrevOrder(pTreeNode root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}
На рисунке ниже показан рекурсивный процесс:
//左子树 根 右子树
void InOrder(pTreeNode root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
Ниже приводится рекурсивный процесс:
//左子树 右子树 根
void PostOrder(pTreeNode root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
Ниже приводится рекурсивный процесс:
Обход уровня: в дополнение к обходу предварительного порядка, обходу по порядку и обходу после порядка, обход уровня может также выполняться на двоичных деревьях. Предположим, что номер уровня корневого узла двоичного дерева равен 1. Обход уровня начинается с корневого узла двоичного дерева. Сначала он посещает корневой узел первого уровня, затем посещает узлы второго уровня. уровень слева направо, а затем третий уровень. Узлы слоя и так далее.Процесс посещения узлов дерева послойно сверху вниз и слева направо представляет собой обход послойного порядка.。
Иллюстрация:
Здесь мы вмешиваемся в очередь, чтобы выполнить предварительный обход двоичного дерева.
// 层序遍历
void LevelOrder(pTreeNode root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
pTreeNode front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
printf("NULL ");
}
else
{
printf("%d ", front->val);
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
QueueDestory(&q);
}
Чтобы создать и уничтожить двоичное дерево, мы используемОбход двоичного дереваНапример.
//二叉树的创建
struct TreeNode* Creat(char* arr,int n,int* i)
{
if(*i<n&&arr[*i]=='#')
{
(*i)++;
return NULL;
}
TreeNode* newnode=(TreeNode*)malloc(sizeof(TreeNode));
newnode->left=NULL;
newnode->right=NULL;
newnode->val=arr[(*i)++];
newnode->left=Creat(arr,n,i);
newnode->right=Creat(arr,n,i);
return newnode;
}
//二叉树的销毁
void TreeDestroy(struct TreeNode* root)
{
if(root==NULL)
{
return;
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
Все последующие операции выполняются по идее обхода.
// 二叉树节点个数
int TreeSize(pTreeNode root)
{
if (root == NULL)
{
return 0;
}
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
int TreeLeafSize(pTreeNode root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int TreeLevelKSize(pTreeNode root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
pTreeNode TreeFind(pTreeNode root, TreeDataType x)
{
if (root == NULL)
{
return NULL;
}
//相等就返回
if (root->val == x)
return root;
//找左子树
pTreeNode left=TreeFind(root->left, x);
if (left)
{
return left;
}
//找右子树
pTreeNode right = TreeFind(root->right, x);
if (right)
{
return right;
}
//都没找到
return NULL;
}
//二叉树的高度
int TreeHeight(pTreeNode root)
{
if (root == NULL)
{
return 0;
}
int max_left = TreeHeight(root->left) ;
int max_right = TreeHeight(root->right);
return max_left > max_right ? max_left + 1 : max_right + 1;
}
//判断是否是完全二叉树
bool TreeComplete(pTreeNode root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
pTreeNode front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
else
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
while (!QueueEmpty(&q))
{
pTreeNode front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestory(&q);
return false;
}
}
QueueDestory(&q);
return true;
}
Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.
Почтамезофия@protonmail.com