내 연락처 정보
우편메소피아@프로톤메일.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
나무는비선형 n(n>=0)개의 제한된 노드로 구성된 계층적 관계 집합인 데이터 구조입니다.묶음뿌리가 위를 향하고 잎이 아래를 향하고 있는 거꾸로 된 나무처럼 보이기 때문에 나무라고 불립니다.
- 루트 노드: 루트 노드에는 선행 노드가 없습니다.
- 루트 노드를 제외한 나머지 노드는 트리와 유사한 구조를 갖는 하위 트리로 나누어집니다. 각 하위 트리의 루트 노드에는 단 하나의 선행 노드가 있고 0개 이상의 후속 노드가 있을 수 있습니다.
- 그러므로 나무는재귀 정의의.
트리 구조는 선형 테이블보다 더 복잡하고, 이를 저장하고 표현하는 것이 더 번거롭습니다.값 범위와 노드와 노드 사이의 관계를 모두 저장해야 합니다.실제로 다음과 같이 트리를 표현하는 방법은 다양합니다.부모 표기, 자식 표기, 자식 부모 표기, 자식 형제 표기기다리다.
다음 저장소 구조를 도입하는 과정에서 다음 트리를 예로 들어 보겠습니다.
우리는 트리의 노드가 일련의 연속적인 공간에 저장되어 있으며 동시에각 노드에는 연결된 목록에서 상위 노드의 위치를 나타내는 표시기가 첨부됩니다. . 즉, 각 노드는 자신이 누구인지 아는 것 외에도 부모가 어디에 있는지도 알고 있습니다.
그 중 데이터는 노드의 데이터 정보를 저장하는 데이터 필드이다. 그리고 parent는 배열에 있는 노드 부모의 첨자를 저장하는 포인터 필드입니다.
다음은 상위 표현에 대한 노드 구조 정의 코드입니다.
/*树的双亲表示法结点结构定义*/
#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. 힙과 힙 응용
이진 트리 구조를 학습하는 가장 간단한 방법은 이를 순회하는 것입니다.소위이진 트리 순회(Traversal)는 특정 규칙에 따라 이진 트리의 노드에 대해 순차적으로 해당 작업을 수행하는 것이며 각 노드는 한 번만 작동합니다. . 노드에 액세스하여 수행되는 작업은 특정 애플리케이션 문제에 따라 다릅니다. 순회는 이진 트리에서 가장 중요한 작업 중 하나이며 이진 트리에서 다른 작업의 기초이기도 합니다.
//根 左子树 右子树
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이라고 가정합니다. 레벨 순서 탐색은 이진 트리의 루트 노드에서 시작하여 먼저 첫 번째 레벨의 루트 노드를 방문한 다음 두 번째 레벨의 노드를 방문합니다. 왼쪽에서 오른쪽으로 레벨을 지정한 다음 레이어의 노드 등을 지정합니다.트리의 노드를 위에서 아래로, 왼쪽에서 오른쪽으로 레이어별로 방문하는 과정이 레이어순회(layer-order traversal)이다.。
삽화:
여기서 우리는 이진 트리의 선주문 순회를 수행하기 위해 대기열에 개입합니다.
// 层序遍历
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 등 다양한 언어에 능숙하며, 오픈 소스 분야에 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.
우편메소피아@프로톤메일.com