嵌入式第二十三课 ！！！树结构与排序（时间复杂度）
二叉树
树
概念
树是 n(n >= 0) 个结点的有限集合。若 n=0 ，为空树。
在任意一个非空树中：
（1）有且仅有一个特定的根结点；
（2）当 n>1 时，其余结点可分为 m 个互不相交的有限集合T1、T2......Tm，其中每一个集合又是一个树，并且称为子树。
度、度数、深度
结点拥有子树的个数称为结点的度。度为 0 的结点称为叶结点；度不为 0 称为分支结点。
树的度数：指在这颗树中，最大的结点的度数，称为树的度数。
树的深度（高度）：指从根开始，根为第一层，根的孩子为第二层，即树的层数，称为树的深度。
树的存储：顺序结构、链表结构。
二叉树（binary tree）
概念
二叉树是 n 个结点的有限集合，集合要么为空树，要么由一个根节点和两棵互不相交的树组成，这两棵树分别称为根节点的左子树和右子树。
特点
（1）每个结点最多两个子树。
（2）左子树和右子树是有顺序的，次序不能颠倒。
（3）如果某个结点只有一个子树，也要区分左、右子树。
特殊的二叉树
（1）斜树
斜树分为两种，一种是所有的结点都只有左子树，称为左斜树；另一种是所有的结点都只有右子树，称为右斜树。
（2）满二叉树
满二叉树是指所有的分支结点都存在左右子树，并且叶子都在同一层上。
（3）完全二叉树
完全二叉树是指：对于一颗具有 n 个结点的二叉树按照层序编号，如果编号 i( 1<= i <= n )的结点于同样深度的满二叉树中编号为 i 的结点在二叉树中的位置完全相同，则此树称为完全二叉树。
特性
（1）在二叉树的第 i 层上最多有 2^(i-1) 个结点，i >= 1。
（2）深度为 k 的二叉树至多有 2^k-1 个结点，k >= 1。
（3）任意一个二叉树T，如果其叶子结点的个数为 N，度数为 M，则 N=M+1。
（4）有 n 个结点的完全二叉树深度为（logn / log2）+ 1。
层序
前序：根左右。先访问根结点，再访问左结点，最后访问右结点。
中序：左根右。先从根结点开始（不是先访问根结点），从左结点开始访问，再访问根结点，最后访问右结点。
后序：左右根。先从根结点开始（不是先访问根结点），从左结点开始访问，再访问右结点，最后访问根结点。
二叉树结构的程序编写
1.创建二叉树
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef char DATATYPE;
typedef struct BiTNode /* 结点结构 */
{DATATYPE data; /* 结点数据 */struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
} BiTNode;char data[] = "Abd#g###ce#h##fi###";
int ind = 0;
void CreateTree(BiTNode **root)
{char c = data[ind++];if ('#' == c){*root = NULL;return;}else{*root = malloc(sizeof(BiTNode));if (NULL == *root){printf("malloc error\n");*root = NULL;return;}(*root)->data = c;CreateTree(&(*root)->lchild);CreateTree(&(*root)->rchild);}return;
}2.三种不同的遍历方式
根左右
void PreOrderTraverse(BiTNode *root)
{if (NULL == root){return;}else{printf("%c", root->data);PreOrderTraverse(root->lchild);PreOrderTraverse(root->rchild);}return;
}左根右
void InOrderTraverse(BiTNode *root)
{if (NULL == root){return;}InOrderTraverse(root->lchild);printf("%c", root->data);InOrderTraverse(root->rchild);return;
}左右根
void PostOrderTraverse(BiTNode *root)
{if (NULL == root){return;}PostOrderTraverse(root->lchild);PostOrderTraverse(root->rchild);printf("%c", root->data);return;
}销毁树结构
void DestroyTree(BiTNode *root)
{if (NULL == root){return;}DestroyTree(root->lchild);DestroyTree(root->rchild);free(root);root = NULL;return;
}