樹是一種非線性的數據結構，它由節點組成，并且這些節點之間通過邊連接。樹的每個節點可以有一個或多個子節點，并且有一個特殊的節點叫做根節點（沒有父節點）。

樹在計算機科學中應用廣泛，尤其是在數據庫索引、編譯器設計和搜索算法等方面。

樹的基本知識點

節點

包含數據以及指向其子節點的引用或鏈接。

邊

連接兩個節點之間的關系。

根節點

樹的最頂端節點，唯一沒有父節點的節點。

葉子節點

沒有子節點的節點。

父節點與子節點

直接相連的上下層節點間的關系。

深度

從根到某個節點的路徑長度。

高度

從某節點到葉子節點的最大路徑長度。樹的高度是指根節點的高度。

子樹

由一個節點及其所有后代節點組成的樹。

遍歷

訪問樹中所有節點的過程，常見的遍歷方法包括前序遍歷、中序遍歷、后序遍歷和層次遍歷。

常見類型的樹

二叉樹

每個節點最多有兩個子節點。

二叉查找樹（BST）

左子樹上所有節點的值都小于它的根節點的值；右子樹上所有節點的值都大于它的根節點的值。

平衡二叉樹

如AVL樹或紅黑樹，它們通過某些機制保持樹的平衡，確保基本操作的時間復雜度為O(log n)。

堆

一種特殊的完全二叉樹，分為最大堆和最小堆。

---

具體的代碼框架如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef char DATATYPE;
typedef struct BiTNode  /* 結點結構 */
{DATATYPE data;		/* 結點數據 */struct BiTNode *lchild,*rchild; /* 左右孩子指針 */
}BiTNode;char dat[]="abd##eh###c#fi###";
int ind;void CreateTree(BiTNode**root)
{char c = dat[ind++];if('#'==c){*root = NULL;}else  {*root = malloc(sizeof(BiTNode));if(NULL == *root ){printf("malloc error\n");return ;}(*root)->data = c;CreateTree(& (*root)->lchild);CreateTree(& (*root)->rchild);}return ;
}/*** @brief  根左右   前序* * @param root */
void PreOrderTraverse(BiTNode*root)
{if(NULL==root ){return ;}else  {printf("%c",root->data);//root PreOrderTraverse(root->lchild);// liftPreOrderTraverse(root->rchild);// right}}
/*** @brief 左根右   中序* * @param root */
void InOrderTraverse(BiTNode* root)
{if(NULL == root){return ;}InOrderTraverse(root->lchild);printf("%c",root->data);InOrderTraverse(root->rchild);
}/*** @brief 左右根    后序* * @param root */
void PostOrderTraverse(BiTNode* root)
{if(NULL == root){return ;}PostOrderTraverse(root->lchild);PostOrderTraverse(root->rchild);printf("%c",root->data);
}void DestroyBiTree(BiTNode*root)
{if(NULL ==root){return ;}DestroyBiTree(root->lchild);DestroyBiTree(root->rchild);free(root);}int	main(int argc, char **argv)
{BiTNode* root=NULL;CreateTree(&root);PreOrderTraverse(root);printf("\n");InOrderTraverse(root);printf("\n");PostOrderTraverse(root);printf("\n");DestroyBiTree(root);// system("pause");return 0;
}

//層序遍歷
#define MAX_QUEUE_SIZE 100typedef struct {BiTNode* data[MAX_QUEUE_SIZE];int front;int rear;
} Queue;// 初始化隊列
void InitQueue(Queue* q) {q->front = 0;q->rear = 0;
}// 判斷隊列是否為空
int IsQueueEmpty(Queue* q) {return q->front == q->rear;
}// 入隊
void EnQueue(Queue* q, BiTNode* node) {if ((q->rear + 1) % MAX_QUEUE_SIZE == q->front) {printf("Queue is full\n");return;}q->data[q->rear] = node;q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
}// 出隊
BiTNode* DeQueue(Queue* q) {if (IsQueueEmpty(q)) {return NULL;}BiTNode* node = q->data[q->front];q->front = (q->front + 1) % MAX_QUEUE_SIZE;return node;
}// 層序遍歷
void LevelOrderTraverse(BiTNode* root) {if (NULL == root) {return;}Queue queue;InitQueue(&queue);EnQueue(&queue, root);while (!IsQueueEmpty(&queue)) {BiTNode* node = DeQueue(&queue);if (node != NULL) {printf("%c", node->data);  // 訪問當前節點EnQueue(&queue, node->lchild);  // 左孩子入隊EnQueue(&queue, node->rchild);  // 右孩子入隊}}
}