c語言數據結構樹的原理?樹的基本概念樹是N個結點的有限集合，當N=0的時候呢，稱為空樹這是一種特殊情況，在任意一棵非空樹中，應該滿足，，接下來我們就來聊聊關于c語言數據結構樹的原理?以下内容大家不妨參考一二希望能幫到您!

c語言數據結構樹的原理

樹的基本概念

樹是N個結點的有限集合，當N=0的時候呢，稱為空樹。這是一種特殊情況，在任意一棵非空樹中，應該滿足，

有且僅有一個特定的稱為根的結點。當N>1時，其餘的節點可分為m 個互不相交的有限集合，其中每個集合本身又是一棵樹，并且稱為根節點的子樹。顯然數的定義是遞歸的，是一種遞歸的數據結構。

樹作為一種邏輯結構，同時也是一種分層結構，具有以下兩個特點，樹的根結點沒有前驅結點，除根節點外的所有節點，由且隻有一個前驅節點。樹中所有節點可以有零個或多個後繼結點，适合于表示具有層次結構的數據。樹中的某個節點最多适合上一層的一個節點，有直接關系,跟結點沒有直接上層節點，因此，在N個結點的樹中有N-1條邊，而樹中每個結點于其下一層的0/多個節點有直接關系.

#include<stdlib.h> #include<stdio.h> //二叉鍊表示 struct BiTNode { int data; struct BiTNode *Lchild, *rchild; }; typedef struct BiTNode BiTNode; typedef struct BiTNode* BiTTree; void main() { BiTNode t1, t2, t3, t4, t5; t1.data = 1; t2.data = 2; t3.data = 3; t4.data = 4; t5.data = 5; //建立關系 t1.Lchild = &t2; t1.rchild = &t3; t2.Lchild = &t4; t3.Lchild = &t5; //樹的遍曆 } //三叉鍊表示 void main() { BiTNode *p1, p2, p3, p4, p5; p1 = (BiTNode*)malloc(sizeof(BiTNode)); p2 = (BiTNode*)malloc(sizeof(BiTNode)); p3 = (BiTNode*)malloc(sizeof(BiTNode)); p4 = (BiTNode*)malloc(sizeof(BiTNode)); p5 = (BiTNode*)malloc(sizeof(BiTNode)); p1->data = 1; p2->data = 2; p3->data = 3; p4->data = 4; p5->data = 5; //建立關系 p1->Lchild = p2; p2->rchild = p3; p3->Lchild = p4; p4->Lchild = p5; //樹的遍曆 } //雙親表示法 子結點中保存了雙親的位置信息 #define MAX_TREE_SIZE typedef struct BPTNope { int data; int parentPosition;//指向雙親的指針 char LRTag;//左右孩子标志域 }BPTNope; typedef struct BPTTree//BPTNope這個又被BPTTree包含 { BPTNope nodes[100];//因為節點之間是分散的,需要把節點存儲到數組中 int num_nodes;//節目數目 int root;//根結點的位置 }BPTTree; void main() { BPTTree tree; // tree.nodes[0].parentPosition = 1000; // tree.nodes[1].parentPosition = 0; tree.nodes[1].data = 'B'; tree.nodes[1].LRTag = 1; // tree.nodes[2].parentPosition = 0; tree.nodes[2].data = 'C'; tree.nodes[2].LRTag = 1; }

小結(基本術語):

1)樹中一個結點的子結點個數稱為該節點的度，樹中結點的最大度數稱為樹的度

度>0的結點稱為分支結點;度為0(沒有子女節點)的節點稱為葉子節點或者是終端節點。在分支節點中，每個節點的分支數就是該節點的節點的度

結點的深度、高度和層次。節點的層次從樹根開始定義，根結點為第一層，它的子節點為第二層。以此類推，結點的深度是從根節點開始自頂向下，逐層累加。點點的高度是從葉節點開始，自底向上逐層壘下。樹的高度又稱深度，是樹中結點的最大層數

有序樹和無序樹樹中結點的子樹，從左到右是有次序的，不能交換，這樣的數稱為有序樹。有序數中一個節點的子節點，按從左到右的順序出現是有。還是有關聯的，反之則為無序樹

路徑和路徑，長度，樹中兩個節點之間的路徑是由這兩個節點之間所經過的節點序列構成的，而路徑長度是路徑上所經過的邊的個數

由于術中的分支是有向的，即從雙親結點到指向孩子節點，所以樹中的路徑是從上向下,同一雙親結點的兩個孩子，結點之間不存在路徑

森林，森林是M和互不相交的樹的集合。森林的概念與樹的概念十分相近，因為隻要把樹的根結點删去，就成了森林，反之，隻要給n棵獨立的數加上一個節點，并把。這N棵樹作為該節點的子樹，則森林就變成了樹.