[数据结构]#6 树

树是一种非线性的数据结构，它由节点组成，并且这些节点之间通过边连接。树的每个节点可以有一个或多个子节点，并且有一个特殊的节点叫做根节点（没有父节点）。

树在计算机科学中应用广泛，尤其是在数据库索引、编译器设计和搜索算法等方面。

树的基本知识点

节点

包含数据以及指向其子节点的引用或链接。

边

连接两个节点之间的关系。

根节点

树的最顶端节点，唯一没有父节点的节点。

叶子节点

没有子节点的节点。

父节点与子节点

直接相连的上下层节点间的关系。

深度

从根到某个节点的路径长度。

高度

从某节点到叶子节点的最大路径长度。树的高度是指根节点的高度。

子树

由一个节点及其所有后代节点组成的树。

遍历

访问树中所有节点的过程，常见的遍历方法包括前序遍历、中序遍历、后序遍历和层次遍历。

常见类型的树

二叉树

每个节点最多有两个子节点。

二叉查找树（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);  // 右孩子入队}}
}