数据结构（六）：树与二叉树
一、树的基本概念
树的定义
树（Tree）是由 n（n ≥ 0）个节点组成的有限集合，当 n = 0 时称为空树。非空树中：有且仅有一个根节点（Root）；
其余节点可以划分为若干个互不相交的子树，每个子树本身也是一棵树。
树的节点与术语
节点包含数据和若干分支；
度（Degree）：节点拥有的子树数量；
叶子节点：度为 0 的节点；
非终端节点：度不为 0 的节点（又称分支节点）；
孩子（Child）与双亲（Parent）：节点间的直接连接关系；
兄弟节点（Sibling）：同一双亲下的节点；
祖先与子孙：从根到某节点的路径上所有节点为祖先，某节点下所有子节点为子孙。
其他概念
层次（Level）：根为第一层，孩子为第二层，以此类推；
深度（Depth）或高度：节点最大层次；
有序树与无序树：若子树顺序不能交换则为有序树，否则为无序树。
二、树的存储结构
树的存储可分为：
顺序结构（如数组）；
链式结构（如链表）；
实际开发中，树通常采用链式结构实现。
三、二叉树的基本概念
定义
二叉树是每个节点最多有两个子树（左子树和右子树）的树结构。这两个子树有先后顺序，不能颠倒。二叉树可能为空，也可能只有一个根节点。特点
节点度最大为 2；
必须区分左子树和右子树，即使只有一个孩子；
子树顺序不可交换。
二叉树的五种基本形态
空二叉树；
只有根节点；
只有左子树；
只有右子树；
同时有左右子树。
四、特殊的二叉树
斜树
左斜树：每个节点只有左子树；
右斜树：每个节点只有右子树。
满二叉树
满足：所有非叶子节点都有左右两个子树；
所有叶子节点都在同一层；
特点：整棵树结构完全对称，节点数最多。
完全二叉树
满足：叶子只出现在最下两层；
最下层叶子靠左连续；
最后一层若不满，叶子也必须靠左；
同样节点数下，深度最小。
五、二叉树的性质（重点公式）
第
i层最多有2^(i-1)个节点（i≥1）深度为
k的二叉树最多有2^k - 1个节点叶子数 = 度为 2 的节点数 + 1
n 个节点的完全二叉树深度为
log₂(n) + 1编号为
i的节点：若
i=1，它是根节点；左孩子编号为
2i；右孩子编号为
2i + 1（若存在）；双亲编号为
i / 2（i > 1 时）。
六、二叉树的遍历方式
前序遍历：根 → 左 → 右
中序遍历：左 → 根 → 右
后序遍历：左 → 右 → 根
注：遍历时虽然“根”在描述中写在前面，但实际执行顺序是递归的，需要先进入子树再处理根节点。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef char DataType;typedef struct BiTNode
{DataType data;struct BiTNode *lchild;struct BiTNode *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(*root == NULL){printf("malloc errror\n");*root = NULL;return ;}(*root)->data = c;CreateTree(&(*root)->lchild);CreateTree(&(*root)->rchild);}return ;
}
//根左右
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 ;}else{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;
}int main(int argc, char const *argv[])
{BiTNode *root;CreateTree(&root);PreOrderTraverse(root);printf("\n");InOrderTraverse(root);printf("\n");PostOrderTraverse(root);printf("\n");DestroyTree(root);root = NULL;return 0;
}