目录
1.树的概念及结构
1.1树的概念
1.2树的相关概念
编辑
1.3树的表示
1.4树在实际中的运用（表示文件系统的目录树结构）
2.二叉树概念及结构
2.1二叉树的概念
2.2现实中的二叉树
编辑
2.3特殊的二叉树
2.4二叉树的性质
2.5二叉树的存储结构
3 .二叉树链式结构的实现
3.1二叉树的创建
3.2二叉树的遍历
3.21前序、中序以及后序遍历
3.22层序遍历
1.树的概念及结构
1.1树的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
- 有一个特殊的结点，称为根结点，根节点没有前驱结点
- 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(10，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1=n否则无左孩子
3. 若2i+2=n否则无右孩子
2.5二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
1. 顺序存储 ：顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们前面的章节有专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
2. 链式存储 ：二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面会学到高阶数据结构如红黑树等会用到三叉链。
typedef int BTDataType; // 二叉链 struct BinaryTreeNode { struct BinTreeNode* _pLeft; // 指向当前节点左孩子 struct BinTreeNode* _pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 } // 三叉链 struct BinaryTreeNode { struct BinTreeNode* _pParent; // 指向当前节点的双亲 struct BinTreeNode* _pLeft; // 指向当前节点左孩子 struct BinTreeNode* _pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 }；3 .二叉树链式结构的实现
3.1二叉树的创建
首先，我们这里先简单创建一个以中序遍历的二叉树结构，可以使用前序，中序，后序，下面会具体讲到遍历。
typedef struct BTNode { char _data; struct BTNode* _left; struct BTNode* _right; }BTNode; //中序遍历 void Inorder(BTNode* root) { if(root) { Inorder(root->_left); printf("%c ", root->_data); Inorder(root->_right); } } BTNode* CreatBTree(char* str, int* pi) { if(str[*pi]!= '#') { //当前节点非空，则创建当前节点 BTNode*root=(BTNode*)malloc(sizeof(BTNode)); root->_data = str[*pi]; //字符位置向后移动一个位置 ++(*pi); //创建左子树 root->_left=CreatBTree(str,pi); //字符位置向后移动一个位置 ++(*pi); //创建右子树 root->_right=CreatBTree(str,pi); return root; } else return NULL; //如果是空节点，则返回NULL } int main() { char str[101]; int i = 0; //读入字符串 scanf("%s", str); //创建二叉树 BTNode* root = CreatBTree(str, &i); //中序打印二叉树 Inorder(root); printf("\n"); return 0; }3.2二叉树的遍历
3.21前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
// 二叉树前序遍历 void PreOrder(BTNode* root); // 二叉树中序遍历 void InOrder(BTNode* root); // 二叉树后序遍历 void PostOrder(BTNode* root);
前序，中序和后序遍历图解：
3.22层序遍历
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
// 层序遍历 void LevelOrder(BTNode* root);
