Đang chuẩn bị liên kết để tải về tài liệu:
Chương 2. cây cấu trúc

Đây là một đồ thị có hướng mà mỗi đỉnh có một trước đó nhưng một người không: gốc rễ. Đối với tất cả x trong X, có tồn tại một con đường duy nhất từ gốc đến x. Hãy xem xét một x nút của cây T, gốc r. Để bất kỳ nút trên con đường duy nhất từ r đến x được gọi là tổ tiên x, x là một hậu duệ của y. Nếu hồ quang mới nhất trên con đường x là r (y, x), sau đó có là cha của x, x là một con. | Chapitre 2. Structures Arborescentes CHAPITRE 2. STRUCTURES ARBORESCENTES. 2.1 DEFINITIONS. 2.1.1 Arbres. C est un graphe non orienté connexe acyclique. Un arbre comprend n - 1 arêtes. L addition à un arbre d une arête entre deux sommets crée un cycle et un seul. 2.1.2 Forets. C est un graphe non orienté acyclique pas forcément connexe . Chaque composante connexe d une forêt est un arbre. 2.1.3 Arborescence. C est un graphe orienté où chaque sommet possède un seul précédent sauf un qui n en a pas la RACINE. Pour tout x de X il existe un chemin unique de la racine à x. On considère un nreud x d une arborescence T de racine r. Un nreud y quelconque sur le chemin unique de rà x est appelé ANCETRE de x x est un DESCENDANT de y. Si le dernier arc sur le chemin de r vers x est y x alors y est le père de x x est un fils de y. Si deux nreuds ont le même père ils sont frères. Un nreud sans fils est une feuille. Un noeud qui n est pas une feuille est dit un noeud interne. La longueur du chemin entre r et x est la profondeur de x dans T. Truong My Dung Mail tmdung@fit.hcmuns.edu.vn 15 Chapitre 2. Structures Arborescentes La hauteur d un noeud x est definie recursivement de la I aqon suivante h x 0 si x est la racine. h x 1 h y si y est le pere de x. Degre d un noeud Degre d une aborescence. Degre d un noeud est le nombre de ses sous-aborescences. Degre d une aborescence est le degre maximal des noeuds. Si une aborescence T a le degre m T est dit l aborescence a m- aires. Si chaque nreud a au maximum deux fils on parle d arborescence binaire. EXEMPLE. Arborescence 3-aires de 8 nreuds de hauteur 4 avec la racine. Niveau 0. ----------------------Gb 1 3 Niveau 1. Niveau 2. Niveau 3. Niveau 4. FIG.2.2. 2.1.4. EXEMPLE. On peut parfois representer une relation d inclusion entre plusieurs ensembles par une aborescence B C D c A. E F G H c B. M N c D. I c E. J K c F. L c H. Truong My Dung 16 Mail tmdung@fit.hcmuns.edu.vn Chapitre 2. Structures Arborescentes Une variable structuree .