数据结构（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的结点有n₀个，度数为1的结点有n₁个，度数为2的结点有n₂个，度数为3的结点有n₃个，度数为4的结点有n₄个

n=n₀+n₁+n₂+n₃+n₄

123=n₀+10+1+10+20

性质二：对于度为m的树，第i层上最多m^i-1个结点

性质二：对于高度为h的树，度为m的树，最多有（m_h-1）/（m-）个结点

二叉树

二叉树（Binary Tree）是n(n>=0)个结点所构成的集合，它或为空树（n=0），或为非空树。对于非空树T：

有且仅有一个称为根的结点。
除根节点以外的其余结点分为两个互不相交的子集T₁和T₂，分别称为T的左子树和右子树，且T₁和T₂本身又都是二叉树。
二叉树的每个结点至多只有两棵子树。
二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树基本形态

二叉树的性质

性质一：二叉树的第i层最多有2^i-1（i>=1）个结点。

性质二：深度为k的二叉树最多有2^k-1（k>=1）个结点。

性质三：对于任何非空二叉树T，如果叶子结点的个数为n₀，而度数为2的节点数为n₂，则n₀=n₂+1。

特殊二叉树

满二叉树
完全二叉树
斜树
二叉排序树
二叉搜索树

满二叉树

所有层的节点数都达到最大值（2^k-1，k 为层数）

所有的叶子结点只能出现在最后一层

对于同样深度的二叉树，满二叉树的结点个数最多，叶子结点的数量也是最多的。

如果对满二叉树进行编号，根节点从1开始，从上到下，从左到右，对于编号为i的结点，若存在孩子，则左孩子的编号为2i，有孩子的编号为2i+1.（如图）

完全二叉树

深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，成为完全二叉树。

除最后一层外，其余层节点全满，最后一层节点靠左排列

叶子结点只可能在层数最大的两层上出现
对任一结点，若其右分支下的子孙最大层数为I，则其左分支下的子孙的最大层次必为I或I+1。

练习

习题一

解答：c

可能出现叶子结点的地方在哪些层？———最后两层当前完全二叉树最多到第7层

第6层共有多少个结点？ ———二叉树的第i层最多有2^i-1（i>=1）个结点。32个

第6层共有多少个非叶节点？———32-8=24个

第7层最多有多少个结点？———48个

前6层最多有多少个结点？———深度为k的二叉树最多有2^k-1（k>=1）个结点。63个

63+48=111

习题二

解答：C

n=n₀+n₁+n₂

对于任何非空的二叉树T，如果叶子结点的个数为n₀，而度为2的结点数为n₂，则，n₀=n₂+1

n=n₂+1+n₁+n₂

当前二叉树共有偶数个结点，说明，有1个度为1的结点

n=n₂+1+1+n₂

768=2n₂+2 ==> n₂=383

n₁=n₂+1=384

习题三

解答：A

所有叶结点均位于同一层，且每个非叶结点都有 2 个子结点” 的完全二叉树，实际是满二叉树

满二叉树的叶子节点数k等于最后一层的节点数，设层数为 h，则 k = 2^(h-1)==> 2k=2^h

满二叉树的总节点数为 2^h- 1，将 2k=2^h代入，可得总节点数 = 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

2^k-1=2⁵-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;}