数据结构（C语言版）树 二叉树
树
一、树的核心定义与特征
树是一个或多个结点的有限集合
空树：n=0；非空树有且仅有 1 个根节点，其余节点分属若干互不相交的子树（子树也遵循树的规则）；
核心特征：无环、节点间唯一父节点（根节点无父节点）、一对多的层次关系。
二、树的基础术语
结点：树中的一个独立单元
结点的度：结点拥有的子树树称为结点的度
树的度：树内各结点的最大值
叶子：度为0结点或终端结点
非终端结点：度不为0的结点
父 / 子 / 兄弟结点：直接上层为父，直接下层为子，同父结点的子结点互为兄弟
层次：根结点为第 1 层，子结点为第 2 层，依此类推；
深度：从根到该结点的层次数（根深度 = 1）；
高度：从该结点到最远叶子结点的最大层次数（叶子高度 = 1）；
森林：m（m≥0）棵互不相交的树的集合；
路径：从一个结点到另一结点的结点序列（唯一路径）。
三、基本性质
性质一：树中所有结点数等于所有结点的度数加1
练习：
解答：B
当前树的所有结点数为：20* 4+10* 3+1*2+10 *1+1=123
假设树的总结点数为n，度数为0的结点有n0个，度数为1的结点有n1个，度数为2的结点有n2个，度数为3的结点有n3个，度数为4的结点有n4个
n=n0+n1+n2+n3+n4
123=n0+10+1+10+20
性质二：对于度为m的树，第i层上最多mi-1个结点
性质二：对于高度为h的树，度为m的树，最多有（mh-1）/（m-）个结点
二叉树
二叉树（Binary Tree）是n(n>=0)个结点所构成的集合，它或为空树（n=0），或为非空树。对于非空树T：
- 有且仅有一个称为根的结点。
- 除根节点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。
- 二叉树的每个结点至多只有两棵子树。
- 二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树基本形态
二叉树的性质
性质一：二叉树的第i层最多有2i-1（i>=1）个结点。
性质二：深度为k的二叉树最多有2k-1（k>=1）个结点。
性质三：对于任何非空二叉树T，如果叶子结点的个数为n0，而度数为2的节点数为n2，则n0=n2+1。
特殊二叉树
- 满二叉树
- 完全二叉树
- 斜树
- 二叉排序树
- 二叉搜索树
满二叉树
所有层的节点数都达到最大值（2k-1，k 为层数）
所有的叶子结点只能出现在最后一层
对于同样深度的二叉树，满二叉树的结点个数最多，叶子结点的数量也是最多的。
如果对满二叉树进行编号，根节点从1开始，从上到下，从左到右，对于编号为i的结点，若存在孩子，则左孩子的编号为2i，有孩子的编号为2i+1.（如图）
完全二叉树
深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，成为完全二叉树。
除最后一层外，其余层节点全满，最后一层节点靠左排列
- 叶子结点只可能在层数最大的两层上出现
- 对任一结点，若其右分支下的子孙最大层数为I，则其左分支下的子孙的最大层次必为I或I+1。
练习
习题一
解答：c
可能出现叶子结点的地方在哪些层？———最后两层当前完全二叉树最多到第7层
第6层共有多少个结点？ ———二叉树的第i层最多有2i-1（i>=1）个结点。32个
第6层共有多少个非叶节点？———32-8=24个
第7层最多有多少个结点？———48个
前6层最多有多少个结点？———深度为k的二叉树最多有2k-1（k>=1）个结点。63个
63+48=111
习题二
解答：C
n=n0+n1+n2
对于任何非空的二叉树T，如果叶子结点的个数为n0，而度为2的结点数为n2，则，n0=n2+1
n=n2+1+n1+n2
当前二叉树共有偶数个结点，说明，有1个度为1的结点
n=n2+1+1+n2
768=2n2+2 ==> n2=383
n1=n2+1=384
习题三
解答：A
所有叶结点均位于同一层，且每个非叶结点都有 2 个子结点” 的完全二叉树，实际是满二叉树
满二叉树的叶子节点数k等于最后一层的节点数，设层数为 h，则 k = 2(h-1)==> 2k=2h
满二叉树的总节点数为 2h- 1，将 2k=2h代入，可得总节点数 = 2k - 1
二叉树的存储结构
顺序结构（数组存储）
基于完全二叉树的节点编号规则，将二叉树节点按层序遍历顺序存入数组，通过下标映射父子节点关系
链式结构
typedefcharElemType;typedefstruct{ElemType data;// 节点数据TreeNode*lchild;// 左子节点指针TreeNode*rchild;// 右子节点指针}TreeNode;//将TreeNode*的指针重命名为BiTreetypedefTreeNode*BiTree;创建二叉树
charstr[]="ABDH#K###E##CFI###G#J##";intidx=0;voidcreateTree(BiTree*T){ElemType ch;ch=str[idx++];// 取当前字符并移动索引if(ch=='#'){*T=NULL;}else{*T=(BiTree)malloc(sizeof(TreeNode));(*T)->data=ch;// 赋值节点数据createTree(&(*T)->lchild);// 递归创建左子树createTree(&(*T)->rchild);// 递归创建右子树}}二级指针
#include<stdio.h>intmain(){charch='A';char*p=&ch;//p是一个指针变量，一级指针变量char**pp=&p;//pp是用来存放p的地址的，pp是一个二级指针变量//将ch里面的值改为B//pp要找到ch需要进行两次解引用//*pp是解引用一次，找到p**pp='B';//解引用2次printf("%c\n",ch);//运行结果：Breturn0;}对于二级指针的运算有：
*pp通过对pp中的地址进行解引用，这样 找到的是p，*pp其实访问的就是p
char*pa='B';*pp=&p;//等价于 p = &a;pp先通过*pp找到p,然后对p进行解引用操作：*p，那找到的是 ``
**pp=B;//等价于*pa = B;//等价于a = B;遍历
如图：
前序遍历
根 → 左子树 → 右子树
//前序遍历：根 → 左子树 → 右子树voidpreOrder(BiTree T){if(T==NULL){return;}printf("%c",T->data);preOrder(T->lchild);preOrder(T->rchild);}前序遍历：A B D H K E C F I G J
中序遍历
左子树 → 根 → 右子树
//中序遍历：左子树 → 根 → 右子树voidinOrder(BiTree T){if(T==NULL){return;}inOrder(T->lchild);printf("%c",T->data);inOrder(T->rchild);}中序遍历: H K D B E A I F C G J
后序遍历
左子树 → 右子树→根
//后序遍历voidlaOrder(BiTree T){if(T==NULL){return;}inOrder(T->lchild);inOrder(T->rchild);printf("%c ",T->data);}后序遍历: K H D E B I F J G C A
二叉树遍历性质
- 已知前序遍历和中序遍历，可以唯一确定一颗二叉树。
- 已知中序遍历和后序遍历，可以唯一确定一颗二叉树。
- 已知前序遍历和后序遍历，是不能确定一颗二叉树。
例如：前序序列是ABC，后序序列是CBA
练习
习题一：
解答：C
习题2：
解答：B
习题三：
解答：A
2k-1=25-1=31
释放内存
//释放二叉树内存voidfreeTree(BiTree T){if(T==NULL)return;freeTree(T->lchild);// 递归释放左子树freeTree(T->rchild);// 递归释放右子树free(T);// 释放当前节点}完整代码
#include<stdio.h>#include<stdlib.h>#include<string.h>typedefcharElemType;//定义typedefstructTreeNode{ElemType data;structTreeNode*lchild;structTreeNode*rchild;}TreeNode;typedefTreeNode*BiTree;//将TreeNode*的指针重命名为BiTreecharstr[]="ABDH#K###E##CFI###G#J##";intidx=0;// 创建二叉树（前序递归）voidcreateTree(BiTree*T){ElemType ch;ch=str[idx++];// 取当前字符并移动索引if(ch=='#'){*T=NULL;}else{*T=(BiTree)malloc(sizeof(TreeNode));(*T)->data=ch;// 赋值节点数据createTree(&(*T)->lchild);// 递归创建左子树createTree(&(*T)->rchild);// 递归创建右子树}}//前序遍历：根 → 左子树 → 右子树；voidpreOrder(BiTree T){if(T==NULL){return;}printf("%c ",T->data);// 访问根节点preOrder(T->lchild);// 遍历左子树preOrder(T->rchild);// 遍历右子树}//中序遍历voidinOrder(BiTree T){if(T==NULL){return;}inOrder(T->lchild);printf("%c ",T->data);inOrder(T->rchild);}//后序遍历voidpostOrder(BiTree T){if(T==NULL){return;}postOrder(T->lchild);postOrder(T->rchild);printf("%c ",T->data);}//释放二叉树内存voidfreeTree(BiTree T){if(T==NULL)return;freeTree(T->lchild);// 递归释放左子树freeTree(T->rchild);// 递归释放右子树free(T);// 释放当前节点}intmain(){BiTree T=NULL;idx=0;// 重置索引createTree(&T);printf("前序遍历结果：");preOrder(T);printf("\n中序遍历结果：");inOrder(T);printf("\n后序遍历结果：");postOrder(T);freeTree(T);// 释放内存return0;}