給別人做網(wǎng)站別人違法經(jīng)營(yíng)優(yōu)化關(guān)鍵詞有哪些方法
‘’’
樹(shù)狀存儲(chǔ)基本概念
深度(層數(shù))
度(子樹(shù)個(gè)數(shù))
葉子
孩子
兄弟
堂兄弟
二叉樹(shù):
滿(mǎn)二叉樹(shù):
完全二叉樹(shù):
存儲(chǔ):順序,鏈?zhǔn)?/p>
樹(shù)的遍歷:按層遍歷,先序,中序,后序
‘’’
樹(shù)是計(jì)算機(jī)科學(xué)中的一種重要數(shù)據(jù)結(jié)構(gòu)。以下是關(guān)于樹(shù)的基本概念和類(lèi)型的詳細(xì)介紹。
基本概念
-
深度(層數(shù)):樹(shù)中某個(gè)節(jié)點(diǎn)的深度是從根節(jié)點(diǎn)到該節(jié)點(diǎn)所經(jīng)歷的邊的數(shù)目。根節(jié)點(diǎn)的深度為0。
-
度(子樹(shù)個(gè)數(shù)):一個(gè)節(jié)點(diǎn)的度是該節(jié)點(diǎn)的子節(jié)點(diǎn)(或子樹(shù))的個(gè)數(shù)。樹(shù)的度是指樹(shù)中所有節(jié)點(diǎn)的度的最大值。
-
葉子:葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn),即度為0的節(jié)點(diǎn)。
-
孩子:某個(gè)節(jié)點(diǎn)的直接下屬節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的孩子。
-
兄弟:具有同一個(gè)父節(jié)點(diǎn)的多個(gè)節(jié)點(diǎn)之間互稱(chēng)為兄弟。
-
堂兄弟:具有同一祖父節(jié)點(diǎn)但不同父節(jié)點(diǎn)的節(jié)點(diǎn)之間互稱(chēng)為堂兄弟。
二叉樹(shù)
二叉樹(shù)是一種特殊的樹(shù)形結(jié)構(gòu),每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn),分別稱(chēng)為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。二叉樹(shù)有以下幾種特殊形式:
-
滿(mǎn)二叉樹(shù):一個(gè)二叉樹(shù)如果除了葉子節(jié)點(diǎn)外,每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn),并且所有葉子節(jié)點(diǎn)都在同一層次上,那么這個(gè)二叉樹(shù)就是滿(mǎn)二叉樹(shù)。
-
完全二叉樹(shù):一個(gè)二叉樹(shù),如果除了最后一層外,每一層的節(jié)點(diǎn)都是滿(mǎn)的,并且最后一層的節(jié)點(diǎn)都從左到右連續(xù)排列,這樣的二叉樹(shù)就是完全二叉樹(shù)。
存儲(chǔ)方式
-
順序存儲(chǔ):利用數(shù)組存儲(chǔ)二叉樹(shù)。通常按層次順序存儲(chǔ),從根節(jié)點(diǎn)開(kāi)始,依次存入數(shù)組的相應(yīng)位置。
-
鏈?zhǔn)酱鎯?chǔ):利用鏈表存儲(chǔ)二叉樹(shù)。每個(gè)節(jié)點(diǎn)使用一個(gè)結(jié)構(gòu)體表示,結(jié)構(gòu)體包含數(shù)據(jù)域和兩個(gè)指針域,分別指向左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。
樹(shù)的遍歷
-
按層遍歷:從樹(shù)的根節(jié)點(diǎn)開(kāi)始,逐層遍歷樹(shù)中的所有節(jié)點(diǎn)。這種遍歷方式也稱(chēng)為廣度優(yōu)先遍歷。
-
先序遍歷(前序遍歷):先訪(fǎng)問(wèn)根節(jié)點(diǎn),然后遞歸地先序遍歷左子樹(shù),最后遞歸地先序遍歷右子樹(shù)。
-
中序遍歷:先遞歸地中序遍歷左子樹(shù),然后訪(fǎng)問(wèn)根節(jié)點(diǎn),最后遞歸地中序遍歷右子樹(shù)。
-
后序遍歷:先遞歸地后序遍歷左子樹(shù),然后遞歸地后序遍歷右子樹(shù),最后訪(fǎng)問(wèn)根節(jié)點(diǎn)。
-
先中 和中后 能確定一顆樹(shù)
以下是樹(shù)的各種存儲(chǔ)方式和遍歷方式的示例代碼:
順序存儲(chǔ)示例
#define MAXSIZE 100typedef struct {int data[MAXSIZE];int size;
} SeqTree;
鏈?zhǔn)酱鎯?chǔ)示例
typedef struct TreeNode {int data;struct TreeNode *left, *right;
} TreeNode;
樹(shù)的遍歷示例
// 先序遍歷
void preOrder(TreeNode *root) {if (root != NULL) {printf("%d ", root->data);preOrder(root->left);preOrder(root->right);}
}// 中序遍歷
void inOrder(TreeNode *root) {if (root != NULL) {inOrder(root->left);printf("%d ", root->data);inOrder(root->right);}
}// 后序遍歷
void postOrder(TreeNode *root) {if (root != NULL) {postOrder(root->left);postOrder(root->right);printf("%d ", root->data);}
}// 按層遍歷
void levelOrder(TreeNode *root) {if (root == NULL) return;Queue q;initQueue(&q);enqueue(&q, root);while (!isEmpty(&q)) {TreeNode *node = dequeue(&q);printf("%d ", node->data);if (node->left != NULL) enqueue(&q, node->left);if (node->right != NULL) enqueue(&q, node->right);}
}
通過(guò)以上介紹,相信你對(duì)樹(shù)的基本概念、二叉樹(shù)及其特殊形式、存儲(chǔ)方式和遍歷方法有了更清晰的理解。