Berbagi teknologi

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

1. Konsep dan struktur pohon

1.1 Konsep pohon

pohon adalah anonlinier Struktur data, yang merupakan sekumpulan hubungan hierarki yang terdiri dari n (n>=0) node terbatas.BundelDisebut pohon karena bentuknya seperti pohon terbalik, artinya akarnya mengarah ke atas dan daunnya mengarah ke bawah.

• Node root: Node root tidak memiliki node pendahulunya.
• Kecuali simpul akar, simpul-simpul yang tersisa dibagi menjadi sub-pohon dengan struktur yang mirip dengan pohon. Node akar dari setiap subpohon mempunyai satu dan hanya satu pendahulu, dan dapat mempunyai 0 atau lebih penerus.
• Oleh karena itu, pohon itu adalahdefinisi rekursifdari.

1.2 Konsep terkait pohon

• Derajat simpul: Jumlah subpohon yang terdapat dalam suatu simpul disebut derajat simpul; seperti yang ditunjukkan pada gambar di atas: A adalah 4
• Simpul daun atau simpul terminal: Node yang berderajat 0 disebut node daun; Seperti terlihat pada gambar di atas: Node B, F, G, D, dan H adalah node daun.
• Node non-terminal atau node cabang: Simpul yang derajatnya bukan 0; Seperti terlihat pada gambar di atas: simpul A, C, dan E merupakan simpul cabang.
• Node induk atau simpul induk: Jika suatu node berisi node anak, maka node tersebut disebut node induk dari node turunannya. Seperti terlihat pada gambar di atas: A adalah node induk dari B
• simpul anak atau simpul anak: Node akar dari subpohon yang ditampung oleh sebuah node disebut node anak dari node tersebut; Seperti yang ditunjukkan pada gambar di atas: B adalah node anak dari A
• Node saudara: Node dengan node induk yang sama disebut node saudara; seperti yang ditunjukkan di atas: B dan C adalah node saudara.
• derajat pohon: Dalam sebuah pohon, derajat simpul terbesar disebut derajat pohon; seperti gambar di atas: derajat pohon adalah 4
• tingkat simpul: Mulai dari definisi root, root level 1, node anak root level 2, dan seterusnya;
• tinggi atau kedalaman pohon: Level maksimum node di pohon; seperti yang ditunjukkan di atas: tinggi pohon adalah 3
• simpul sepupu: Node-node yang orang tuanya berada pada level yang sama adalah sepupu satu sama lain; seperti yang ditunjukkan pada gambar di atas: F dan G adalah node saudara satu sama lain.
• Nenek moyang simpul: Semua node pada cabang dari akar hingga node; seperti yang ditunjukkan pada gambar di atas: A adalah nenek moyang dari semua node
• keturunan : Setiap node dalam subpohon yang berakar pada node tertentu disebut turunan dari node tersebut.Seperti yang ditunjukkan di atas: semua node adalah keturunan A
• hutan: Kumpulan m pohon yang saling lepas disebut hutan;

1.3 Representasi pohon

Struktur pohon lebih rumit daripada tabel linier, dan lebih sulit untuk menyimpan dan merepresentasikannya.Penting untuk menyimpan rentang nilai dan hubungan antara node dan node., sebenarnya ada banyak cara untuk merepresentasikan pohon, seperti:Notasi orang tua, notasi anak, notasi orang tua anak, dan notasi saudara anakTunggu.

Dalam proses memperkenalkan struktur penyimpanan berikut, kami mengambil pohon berikut sebagai contoh.

1.3.1 Keterwakilan orang tua

Kami berasumsi bahwa simpul-simpul pohon disimpan dalam sekumpulan ruang yang berkesinambungan, dan pada waktu yang samaDi setiap node, dipasang indikator untuk menunjukkan posisi node induknya dalam daftar tertaut. . Dengan kata lain, selain mengetahui siapa node tersebut, setiap node juga mengetahui keberadaan induknya.

Diantaranya, data adalah bidang data, yang menyimpan informasi data dari node. Dan induk adalah bidang penunjuk yang menyimpan subskrip induk simpul dalam larik.
Berikut ini adalah kode definisi struktur simpul untuk representasi induk kita.

/*树的双亲表示法结点结构定义*/
#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

Dengan struktur penyimpanan seperti itu, kita dapat dengan mudah menemukan node induknya sesuai dengan penunjuk induk dari node yang digunakanKompleksitas waktu adalah 0(1) , hingga induknya -1, menandakan bahwa akar simpul pohon telah ditemukan. Namun jika kita ingin mengetahui apa itu anak dari node tersebut, maaf silahkan melintasi seluruh strukturnya.

1.3.2 Representasi adik laki-laki

Baru saja kita mempelajari struktur penyimpanan pohon dari sudut pandang orang tua dan sudut pandang anak. Bagaimana jika kita melihat saudara dari simpul pohon? Tentu saja, untuk struktur hierarki seperti pohon, kita hanya mempelajarinya saudara dari simpul tersebut. Hal ini tidak mungkin. Setelah observasi, kami menemukan bahwa untuk pohon mana pun, anak pertama dari simpul tersebut adalah unik jika ada, dan saudara kanannya juga unik jika ada. Oleh karena itu, kami menetapkan dua pointer, menunjuk ke anak pertama dari node dan saudara kanan dari node.

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

1.4 Penerapan praktis pohon

2. Konsep dan struktur pohon biner

2.1 Konsep

Pohon biner adalah kumpulan node berhingga, yaitu:

• atau kosong
• Ini terdiri dari sebuah simpul akar ditambah dua pohon biner, juga dikenal sebagai subpohon kiri dan subpohon kanan.

Seperti yang terlihat dari gambar di atas:

1. Tidak ada simpul dengan derajat lebih besar dari 2 dalam pohon biner
2. Subpohon dari pohon biner dapat dibagi menjadi subpohon kiri dan kanan, dan urutannya tidak dapat dibalik, sehingga pohon binernya adalahpohon yang dipesan

Catatan: Setiap pohon biner terdiri dari situasi berikut:

2.2 Pohon biner khusus

1. pohon biner penuh: pohon biner,Jika jumlah node pada setiap lapisan mencapai maksimum, maka pohon biner adalah pohon biner penuh. . Artinya, jika jumlah level pohon biner adalah K dan jumlah total node adalah 2^k-1, maka pohon tersebut merupakan pohon biner penuh.
2. pohon biner lengkap: Pohon biner lengkap adalah struktur data yang sangat efisien.Pohon biner lengkap diturunkan dari pohon biner penuh . Untuk pohon biner dengan n simpul dengan kedalaman K, disebut pohon biner lengkap jika dan hanya jika setiap simpul berkorespondensi satu-ke-satu dengan simpul-simpul yang diberi nomor dari 1 hingga n pada pohon biner lengkap dengan kedalaman K. Untuk berhati-hatiPohon biner penuh adalah jenis pohon biner lengkap yang khusus.
   

2.3 Sifat pohon biner

1. Jika jumlah level dari simpul akar ditentukan menjadi 1, makaTerdapat paling banyak 2^(i-1) pada lapisan ke-i node
2. Jika jumlah level dari simpul akar ditentukan menjadi 1, makaJumlah maksimum node pohon biner dengan kedalaman h adalah 2^h-1
3. Untuk pohon biner apa pun, jikaBanyaknya simpul daun yang berderajat 0 adalah n0, dan banyaknya simpul cabang yang berderajat 2 adalah n2, maka n0=n2 +1
4. Jika jumlah level node akar ditentukan menjadi 1,Kedalaman pohon biner penuh dengan n node, h=log (n+1) (ps: log adalah basis 2, n+1 adalah logaritma)
5. Untuk pohon biner lengkap dengan n node, jika semua node diberi nomor mulai dari 0 secara berurutan dari atas ke bawah, kiri ke kanan, maka untuk node dengan nomor urut i:
   • Jika i>0, nomor induk node pada posisi i: (i-1)/2;, i adalah nomor simpul akar, tidak ada simpul induk
   • Jika 2i+1, 2i+1>=n jika tidak, tidak ada anak kiri
   • Jika 2i+2, 2i+2>=n jika tidak, tidak ada anak yang tepat

2.4 Struktur penyimpanan pohon biner

Pohon biner umumnya dapat disimpan menggunakan dua struktur:Struktur berurutan, struktur rantai.

1. penyimpanan berurutan
   Penyimpanan struktur berurutan akan digunakanHimpunanUntuk menyimpan, umumnya menggunakan arrayHanya cocok untuk merepresentasikan pohon biner lengkap , karena ini bukan pohon biner yang lengkap dan akan membuang-buang ruang. Pada kenyataannya, hanya heap yang menggunakan array untuk penyimpanan.Penyimpanan sekuensial pohon biner secara fisik berupa array dan secara logis merupakan pohon biner.
   2. Penyimpanan rantai
   Struktur penyimpanan tertaut dari pohon biner mengacu pada,Gunakan daftar tertaut untuk mewakili pohon biner , yaitu menggunakan rantai untuk menunjukkan hubungan logis elemen. **Metode yang biasa dilakukan adalah setiap node dalam daftar tertaut terdiri dari tiga bidang, yaitu bidang data dan bidang penunjuk kiri dan kanan. Penunjuk kiri dan kanan digunakan untuk memberikan alamat penyimpanan titik tautan tempat anak kiri dan anak kanan dari node berada masing-masing. **Struktur rantai dibagi menjadi rantai biner dan rantai bercabang tiga. Saat ini, kita umumnya mempelajari rantai biner.
   

3. Struktur sekuensial dan implementasi pohon biner

Pohon biner biasa tidak cocok untuk disimpan dalam susunan karena mungkin terdapat banyak ruang yang terbuang.DanPohon biner lengkap lebih cocok untuk penyimpanan struktur sekuensial .Kenyataannya, kita biasanyaHeap (pohon biner) menggunakan array struktur berurutan untuk menyimpan, perlu dicatat bahwa heap di sini dan heap di ruang alamat proses virtual sistem operasi adalah dua hal yang berbeda. Yang pertama adalah struktur data, dan yang lainnya adalah segmentasi area yang mengelola memori dalam sistem operasi.
Untuk implementasi dan penerapan spesifik, silakan lihat:[Struktur Data] 08. Aplikasi heap dan heap

4. Struktur rantai pohon biner dan implementasinya

4.1 Penjelajahan pohon biner

Cara paling sederhana untuk mempelajari struktur pohon biner adalah dengan melintasinya.yang disebutPenjelajahan pohon biner (Traversal) adalah melakukan operasi terkait pada node dalam pohon biner secara berurutan sesuai aturan tertentu, dan setiap node hanya dioperasikan satu kali . Operasi yang dilakukan dengan mengakses node bergantung pada masalah aplikasi spesifik. Traversal adalah salah satu operasi terpenting pada pohon biner dan juga merupakan dasar untuk operasi lain pada pohon biner.

4.1.1 Penjelajahan praorder

//根 左子树 右子树
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

Gambar di bawah menunjukkan proses rekursif:

4.1.2 Penjelajahan berurutan

//左子树 根 右子树
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

Berikut ini adalah proses rekursifnya:

4.1.3 Penjelajahan pasca pesanan

//左子树 右子树 根
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

Berikut ini adalah proses rekursifnya:

4.2.4 Penjelajahan tingkat-urutan

Penjelajahan tingkat pesanan: Selain penjelajahan pesanan sebelumnya, penjelajahan dalam pesanan, dan penjelajahan pasca pesanan, penjelajahan tingkat pesanan juga dapat dilakukan pada pohon biner. Asumsikan bahwa jumlah level dari simpul akar pohon biner adalah 1. Penjelajahan urutan tingkat dimulai dari simpul akar dari pohon biner. Pertama, ia mengunjungi simpul akar pada tingkat pertama, kemudian mengunjungi simpul pada tingkat kedua tingkat dari kiri ke kanan, dan kemudian tingkat ketiga. Node lapisan, dan seterusnya,Proses mengunjungi node pohon selapis demi selapis dari atas ke bawah dan dari kiri ke kanan merupakan traversal urutan lapisan.。
Ilustrasi:

Di sini kita mengintervensi antrian untuk melakukan pre-order traversal dari pohon biner.

// 层序遍历
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 Penciptaan dan penghancuran pohon biner

Untuk membuat dan menghancurkan pohon biner, kami menggunakanPenjelajahan pohon binerMisalnya.

//二叉树的创建
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 Operasi lain pada pohon biner

Semua operasi berikut dilakukan sesuai dengan gagasan traversal.

// 二叉树节点个数
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