Teknologian jakaminen

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Puun käsite ja rakenne

1.1 Puun käsite

puu on aepälineaarinen Tietorakenne, joka on joukko hierarkkisia suhteita, jotka koostuvat n:stä (n>=0) rajoitetusta solmusta.NippuSitä kutsutaan puuksi, koska se näyttää ylösalaisin olevalta puulta, mikä tarkoittaa, että sen juuret osoittavat ylöspäin ja lehdet alaspäin.

• Juurisolmu: juurisolmulla ei ole edeltävää solmua.
• Juurisolmua lukuun ottamatta loput solmut on jaettu alipuihin, joiden rakenne on samanlainen kuin puulla. Kunkin alipuun juurisolmulla on yksi ja vain yksi edeltäjä, ja sillä voi olla 0 tai useampia seuraajia.
• Siksi puu onrekursiivinen määritelmä/.

1.2 Puihin liittyvät käsitteet

• Solmun aste: Solmun sisältämien alipuiden lukumäärää kutsutaan solmun asteeksi, kuten yllä olevassa kuvassa on esitetty: A on 4
• Lehtisolmu tai terminaalisolmu: Solmuja, joiden aste on 0, kutsutaan lehtisolmuiksi. Kuten yllä olevasta kuvasta näkyy: Solmut B, F, G, D ja H ovat lehtisolmuja.
• Ei-päätesolmu tai haarasolmu: Solmu, jonka aste ei ole 0 Kuten yllä olevasta kuvasta näkyy: solmut A, C ja E ovat haarasolmuja.
• Pääsolmu tai yläsolmu: Jos solmu sisältää lapsisolmuja, tätä solmua kutsutaan sen alisolmun pääsolmuksi. Kuten yllä olevasta kuvasta näkyy: A on B:n pääsolmu
• lapsisolmu tai lapsisolmu: Solmun sisältämän alipuun juurisolmua kutsutaan solmun lapsisolmuksi Kuten yllä olevasta kuvasta näkyy: B on A:n lapsisolmu
• Sisarussolmu: Solmuja, joilla on sama pääsolmu, kutsutaan sisarussolmuiksi, kuten yllä on esitetty: B ja C ovat sisarussolmuja.
• puun aste: Puussa suurimman solmun astetta kutsutaan puun asteeksi, kuten yllä on esitetty: puun aste on 4
• Solmutaso: Juuren määritelmästä alkaen juuri on 1. taso, juuren lapsisolmut ovat 2. taso ja niin edelleen;
• puun korkeus tai syvyys: Puun solmujen enimmäistaso, kuten yllä on esitetty: puun korkeus on 3
• serkkusolmu: Solmut, joiden vanhemmat ovat samalla tasolla, ovat toistensa serkkuja, kuten yllä olevasta kuvasta näkyy: F ja G ovat toistensa velisolmuja.
• Solmun esi-isä: Kaikki haaroissa olevat solmut juuresta solmuun, kuten yllä olevassa kuvassa näkyy: A on kaikkien solmujen esi-isä
• jälkeläisiä : Mitä tahansa alipuun solmua, joka on juurtunut tiettyyn solmuun, kutsutaan kyseisen solmun jälkeläiseksi.Kuten yllä näkyy: kaikki solmut ovat A:n jälkeläisiä
• metsä: Joukkoa, jossa on m erillisiä puita, kutsutaan metsäksi;

1.3 Puun esittäminen

Puurakenne on monimutkaisempi kuin lineaaritaulukko, ja sen tallentaminen ja esittäminen on hankalampaa.Sekä arvoalue että solmujen ja solmujen välinen suhde on tallennettava., itse asiassa on monia tapoja esittää puita, kuten:Vanhemman merkintä, lapsimerkintä, lapsen vanhemman merkintä ja lapsivelimerkintäodota.

Seuraavan tallennusrakenteen käyttöönotossa otamme seuraavan puun esimerkkinä.

1.3.1 Vanhemman edustus

Oletetaan, että puun solmut on tallennettu joukkoon jatkuvia tiloja, ja samaan aikaanJokaisessa solmussa on osoitin, joka osoittaa sen pääsolmun sijainnin linkitetyssä luettelossa. . Toisin sanoen, sen lisäksi, että jokainen solmu tietää kuka se on, se tietää myös missä sen vanhemmat ovat.

Niiden joukossa data on tietokenttä, joka tallentaa solmun datatiedot. Ja vanhempi on osoitinkenttä, joka tallentaa solmun vanhempien alaindeksit taulukkoon.
Seuraava on solmurakenteen määrityskoodi ylätason esityksellemme.

/*树的双亲表示法结点结构定义*/
#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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Tällaisella tallennusrakenteella voimme helposti löytää sen pääsolmut käytetyn solmun pääosoittimen mukaanAika monimutkaisuus on 0(1) , kunnes vanhempi on -1, mikä osoittaa, että puusolmun juuri on löydetty. Mutta jos haluamme tietää, mitä solmun lapset ovat, sorry, käy läpi koko rakenne.

1.3.2 Lapsiveljen edustus

Juuri nyt tutkimme puun säilytysrakennetta vanhempien ja lapsen näkökulmasta. Entä jos tarkastelemme puun solmujen veljiä Solmujen veljet Havainnon jälkeen havaitsimme, että sen solmun ensimmäinen lapsi on ainutlaatuinen, jos se on olemassa, ja sen oikea veli on myös ainutlaatuinen. Siksi asetamme kaksi osoitinta, jotka osoittavat solmun ensimmäistä lasta ja solmun oikeaa sisarusta.

/*树的孩子兄弟表示法结构定义*/
typedef struct TreeNode
{
	TElemtype data;
	struct TreeNode *firstchild, *rightsib;
} TreeNode,* pTreeNode;
1
2
3
4
5
6

1.4 Puiden käytännön sovellukset

2. Binääripuun käsite ja rakenne

2.1 Konsepti

Binääripuu on äärellinen joukko solmuja, joka on:

• tai tyhjä
• Se koostuu juurisolmusta ja kahdesta binääripuusta, jotka tunnetaan myös nimellä vasen alipuu ja oikea alipuu.

Kuten yllä olevasta kuvasta näkyy:

1. Binääripuussa ei ole solmua, jonka aste on suurempi kuin 2
2. Binääripuun alipuut voidaan jakaa vasempaan ja oikeaan alipuuhun, eikä järjestystä voida kääntää, joten binääripuu ontilattu puu

Huomautus: Mikä tahansa binääripuu koostuu seuraavista tilanteista:

2.2 Erityiset binaaripuut

1. täysi binääripuu: binääripuu,Jos solmujen lukumäärä kussakin kerroksessa saavuttaa maksimin, binääripuu on täysi binääripuu. . Toisin sanoen, jos binääripuun tasojen lukumäärä on K ja solmujen kokonaismäärä on 2^k-1, niin se on täysi binääripuu.
2. täydellinen binääripuu: Täydellinen binääripuu on erittäin tehokas tietorakenne.Täydelliset binääripuut johdetaan täysistä binääripuista . Binääripuuta, jossa on n syvyyden K solmua, kutsutaan täydelliseksi binääripuuksi silloin ja vain, jos jokainen solmu vastaa yksi-yhteen solmuja, jotka on numeroitu syvyyden K koko binääripuussa. VaroakseenTäysi binääripuu on erityinen täydellinen binääripuu.
   

2.3 Binääripuiden ominaisuudet

1. Jos juurisolmun tasojen lukumääräksi on määritetty 1, niinI:nnellä tasolla on enintään 2^(i-1). solmut
2. Jos juurisolmun tasojen lukumääräksi on määritetty 1, niinBinääripuun, jonka syvyys on h, solmujen enimmäismäärä on 2^h-1
3. Mille tahansa binääripuulle, josLehtisolmujen määrä asteella 0 on n0 ja haarasolmujen määrä asteella 2 on n2, jolloin n0=n2 +1
4. Jos juurisolmun tasojen lukumääräksi on määritetty 1,Täyden binääripuun syvyys, jossa on n solmua, h=log (n+1) (ps: log on kantaluku 2, n+1 on logaritmi)
5. Täydelliselle binääripuulle, jossa on n solmua, jos kaikki solmut on numeroitu alkaen 0:sta taulukon järjestyksessä ylhäältä alas, vasemmalta oikealle, niin solmulle, jonka sarjanumero on i:
   • Jos i>0, asemassa i olevan solmun emonumero: (i-1)/2;, i on juurisolmun numero, yläsolmua ei ole
   • Jos 2i+1, 2i+1>=n muuten ei ole jäljellä lasta
   • Jos 2i+2, 2i+2>=n muuten ei ole oikeaa lasta

2.4 Binääripuun tallennusrakenne

Binääripuita voidaan yleensä tallentaa käyttämällä kahta rakennetta:Peräkkäinen rakenne, ketjurakenne.

1. peräkkäinen tallennus
   Käytetään peräkkäistä rakennettajoukkoKäytä tallentamiseen yleensä taulukkoaSoveltuu vain täydellisten binääripuiden esittämiseen , koska se ei ole täydellinen binääripuu ja siellä tulee tuhlaamaan tilaa. Todellisuudessa vain kasa käyttää taulukoita varastointiin.Binääripuiden peräkkäinen tallennus on fyysisesti taulukko ja loogisesti binääripuu.
   2. Ketjuvarasto
   Binääripuun linkitetty tallennusrakenne viittaaKäytä linkitettyä luetteloa edustamaan binaaripuuta , eli ketjujen käyttäminen elementtien loogisen suhteen osoittamiseen. **Tavallinen menetelmä on, että linkitetyn luettelon jokainen solmu koostuu kolmesta kentästä, tietokentästä sekä vasemmasta ja oikeasta osoitinkentästä. Vasenta ja oikeaa osoitinta käytetään antamaan niiden linkkipisteiden tallennusosoitteet, joissa vasen lapsi ja solmun oikea lapsi ovat vastaavasti. **Ketjurakenteet jaetaan binääriketjuihin ja kolmihaaraisiin ketjuihin.
   

3. Binääripuun peräkkäinen rakenne ja toteutus

Tavalliset binaaripuut eivät sovellu varastointiin ryhmissä, koska siellä voi olla paljon hukkaan heitettyä tilaa.jaTäydelliset binaaripuut sopivat paremmin peräkkäiseen rakenteiden varastointiin .Todellisuudessa me yleensäKasa (binääripuu) käyttää tallentamiseen joukkoa peräkkäisiä rakenteita, on huomattava, että kasa tässä ja käyttöjärjestelmän virtuaalisen prosessin osoiteavaruudessa ovat kaksi eri asiaa, toinen on tietorakenne ja toinen aluesegmentointi, joka hallitsee käyttöjärjestelmän muistia.
Katso tarkempi toteutus ja sovellus:[Tietorakenne] 08. Kasa ja kasasovellukset

4. Binääripuun ketjurakenne ja sen toteutus

4.1 Binaaripuun läpikulku

Yksinkertaisin tapa oppia binääripuurakenne on kulkea sen läpi.niin sanottuBinääripuun läpikulku (Traversal) on suorittaa vastaavat toiminnot binääripuun solmuille järjestyksessä tiettyjen sääntöjen mukaisesti, ja jokaista solmua käytetään vain kerran. . Solmuihin pääsyn suorittamat toiminnot riippuvat tietystä sovellusongelmasta. Traversal on yksi tärkeimmistä binääripuun operaatioista ja myös muiden binääripuun toimintojen perusta.

4.1.1 Ennakkotilausmatka

//根 左子树 右子树
void PrevOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Alla oleva kuva näyttää rekursiivisen prosessin:

4.1.2 Tilauksen läpikulku

//左子树 根 右子树
void InOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Seuraava on rekursiivinen prosessi:

4.1.3 Postorder-läpikulku

//左子树 右子树 根
void PostOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Seuraava on rekursiivinen prosessi:

4.2.4 Tasojärjestyksen läpikulku

Tasojärjestyksen läpikulku: Ennakkotilauksen, tilauksen läpikulun ja tilauksen jälkeisen läpikulun lisäksi tasojärjestyksen läpikulku voidaan suorittaa myös binääripuille. Oletetaan, että binääripuun juurisolmun tasonumero on 1. Tasojärjestyksen läpikulku alkaa binääripuun juurisolmusta. Ensin se vierailee ensimmäisen tason juurisolmussa ja sitten toisen tason solmuissa taso vasemmalta oikealle ja sitten kolmas taso Tason solmut ja niin edelleen,Menettely puun solmuissa kerros kerrokselta ylhäältä alas ja vasemmalta oikealle on kerrosjärjestyksen läpikulku.。
Kuva:

Tässä puutumme jonoon suorittaaksemme binääripuun ennakkotilauksen läpikäynnin.

// 层序遍历
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

4.1 Binääripuiden luominen ja tuhoaminen

Käytämme binääripuun luomiseen ja tuhoamiseenBinaaripuun läpikulkuEsimerkiksi.

//二叉树的创建
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//二叉树的销毁
void TreeDestroy(struct TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    TreeDestroy(root->left);
    TreeDestroy(root->right);
    free(root);
}
1
2
3
4
5
6
7
8
9
10
11

4.3 Muut toiminnot binääripuilla

Seuraavat toiminnot suoritetaan kaikki läpikulkuajatuksella.

// 二叉树节点个数
int TreeSize(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}
1
2
3
4
5
6
7
8
9

// 二叉树叶子节点个数
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// 二叉树第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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// 二叉树查找值为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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//二叉树的高度
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;
}
1
2
3
4
5
6
7
8
9
10
11

//判断是否是完全二叉树
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36