数据结构----树

        一对多，每个节点最多有一个前驱，但可以有多个后继（根节点无前驱，叶节点无后继）

二丶二叉树

1.概念

        二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。

2.性质

     (1)  二叉树第k（k>=1）层上的节点最多为2的k-1次幂 // 2^(k-1)

3.满二叉树和完全二叉树

4.二叉树的遍历

5.2链式存储

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{int data;            // 数据域struct node *lchild; // 左子树struct node *rchild; // 右子树
} node_t, *node_p;
node_p CreateBitTree(int i, int n) // i为根节点编号，n为节点数
{node_p p = (node_p)malloc(sizeof(node_t)); // 开辟空间if (NULL == p)                             // 容错判断{printf("Create err");return NULL;}p->data = i;                             // 初始化数据域if (2 * i <= n)                          // 判断有无左子树p->lchild = CreateBitTree(2 * i, n); // 利用递归函数创建树elsep->lchild = NULL;if (2 * i + 1 <= n) // 判断有无右子树p->rchild = CreateBitTree(2 * i + 1, n);elsep->rchild = NULL;
}
int Perorder(node_p p)//前序遍历
{if (NULL == p)return 0;printf("%d ", p->data);if (NULL != p->lchild)Perorder(p->lchild);if (NULL != p->rchild)Perorder(p->rchild);
}
int Midorder(node_p p)//中序遍历
{if (NULL == p)return 0;if (NULL != p->lchild)Midorder(p->lchild);printf("%d ", p->data);if (NULL != p->rchild)Midorder(p->rchild);
}
int Rearorder(node_p p)//后序遍历
{if (NULL == p)return 0;if (NULL != p->lchild)Rearorder(p->lchild);if (NULL != p->rchild)Rearorder(p->rchild);printf("%d ", p->data);
}
int Release(node_p p)//释放树
{if (NULL == p)return 0;if (p->lchild != NULL)Release(p->lchild);if (p->rchild != NULL)Release(p->rchild);free(p);p = NULL;
}
int main(int argc, char const *argv[])
{node_p p = CreateBitTree(1, 5);printf("前序遍历\n");Perorder(p);printf("中序遍历\n");Midorder(p);printf("后序遍历\n");Rearorder(p);printf("\n");return 0;
}

6.层次遍历

三丶哈夫曼树