nas做流媒体网站,电话销售做网站打官司,wordpress发布文章附件,网站建站北京文章目录1 树的基本概念1.1 树的形式定义1.2 树的递归定义1.3 树的基本术语1.4 二叉树的递归定义1.5 存储方法1.6 满二叉树VS完全二叉树2 二叉树的性质3 代码实现1 树的基本概念
1.1 树的形式定义 T{D#xff0c;R} D为树T中包含n个结点的有限集合#xff0c;R为树中结点之间…
文章目录1 树的基本概念1.1 树的形式定义1.2 树的递归定义1.3 树的基本术语1.4 二叉树的递归定义1.5 存储方法1.6 满二叉树VS完全二叉树2 二叉树的性质3 代码实现1 树的基本概念
1.1 树的形式定义
T{DR} D为树T中包含n个结点的有限集合R为树中结点之间关系的集合。当n0时树为空树当n0时R是D上某个二元关系的集合满足以下条件 有且仅有一个结点称为根结点该结点没有直接前驱结点除根结点外每个结点有且仅有一个前驱结点D中每个结点可以有零个或多个后继结点 1.2 树的递归定义
树是由nn≥0个结点组成的有限集T。当n0时它是一个空树当n0时它满足两个条件 有且仅有一个特定的结点称为根结点。除根结点以外的其余结点分为m个m≥0互不相交的有限集T1、T2、……Tm其中每个集合又都是一棵树称T1、T2、……Tm为根结点的子树。 1.3 树的基本术语 结点树的数据元素结点的度该结点的分支的个数树的度树中所有结点的度的最大值结点的层次从根到该结点的层数根结点算第一层树的深度所有结点的层次的最大值根结点在非空树中无前驱结点的结点分支结点度不为0的结点叶结点度为0的结点孩子结点结点的子树的根双亲结点孩子结点的根结点兄弟结点具有共同双亲的结点堂兄弟结点双亲互为兄弟的结点祖先结点从根到该结点的所经历的所有结点子孙结点以某结点为根的子树中的任一结点 1.4 二叉树的递归定义 二叉树是结点的有限集合这个有限集或为空集或由一个根结点及两棵互不相交的分别叫作这个根的左子树和右子树的二叉树组成。 【注意】二叉树不是树的特殊情况。
1.5 存储方法 双亲表示法——求父结点方便 孩子表示法——求子结点方便 双亲孩子表示法—求父结点和子结点方便 二叉树表示法——把一个普通树转化成二叉树来存储 1.6 满二叉树VS完全二叉树
满二叉树 定义深为k且有2k−12^k-12k−1个结点的二叉树。编号约定编号从根开始自上而下自左而右给二叉树中的每个结点一个从1开始的连续的编号。 完全二叉树 定义深为k且有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。 满二叉树是完全二叉树反之则不一定
2 二叉树的性质
在二叉树的第 i 层上至多有 2i−12^{i-1}2i−1个结点 (i≥1i\geq1i≥1) 证明 1i1时只有一个根结点2i−12^{i-1}2i−1 202^020 1结论正确 2假设nk-1命题成立即第k-1层上至多有 2k−22^{k-2}2k−2 个结点则当nk时每个结点至多有两棵子树 则k层结点最多为k-1层的2倍故s2∗2k−22k−1s2*2^{k-2}2^{k-1}s2∗2k−22k−1第i层至多有 2i−12^{i-1}2i−1 个结点 3由归纳法即得证。 深度为 k 的二叉树至多有2k−12^k-12k−1个节点(k≥1k\geq1k≥1) 2021…2k-12k-1利用等比数列求和公式得到结果 对任何一颗二叉树 T如果其终端结点树为 n0n_0n0度为 2 的结点数为 n2n_2n2则 n0n_0n0 n2n_2n21 证明 终端结点数就是叶结点数了而一颗二叉树除了叶结点外剩下的就是度为 1 和 2 的结点数了我们设 n1n_1n1 为度是 1 的结点数则树 T 的总结点数为 n n0n_0n0 n1n_1n1 n2n_2n2 再换一个角度数一下二叉树中连接线的总数由于根节点没有双亲所以一个二叉树中连接线数等于结点树-1n1n_1n1 的度为 1 所以它仅有一条连接线n2n_2n2同理代数表达式就是 n−1n-1n−1 n1n_1n1 2n22n_22n2 再结合等式 n n0n_0n0 n1n_1n1 n2n_2n2 推导出 n0n_0n0 n1n_1n1 n2n_2n2-1 n1n_1n1 2n22n_22n2 所以 n0n_0n0 n2n_2n2 1 具有 n 个结点的完全二叉树的深度为 [log2n][\log_2 n][log2n] 1 ,[x]代表不大于 x 的最大整数 证明 1对于满二叉树深度为 k 的满二叉树至多有2k−12^k-12k−1个节点(k≥1k\geq1k≥1) 那么由 n2k−1n2^k-1n2k−1 可以倒推 klog2(n1)k\log_2(n1)klog2(n1) 2对于完全二叉树它的结点数一定少于等于同样深度的满二叉树 2k−12^k-12k−1但一定多于 2i−1−12^{i-1}-12i−1−1即 2i−1−1n≤2k−12^{i-1}-1n\leq2^k-12i−1−1n≤2k−1 所以 2i−1≤n2k2^{i-1}\leq n 2^k2i−1≤n2k 两边取对数 2i−1≤n2k2^{i-1}\leq n 2^k2i−1≤n2k 而 k 又是整数 k[log2n]1k [\log_2 n] 1k[log2n]1 对于一个有 n 个结点的完全二叉树或满二叉树的结点按层序顺序从左到右编号对任意结点 i 有 1如果 i 1那么结点 i 为该树的根无双亲若 i 1 则其双亲是结点 [i/2] 2如果 2i n则结点无左孩子结点 i 为叶子结点否则其左孩子结点是 2i 3如果 2i 1 n则结点 i 无右孩子否则其右孩子是结点 2i 1 3 代码实现
创建二叉树
#include stdio.h
#include stdlib.htypedef char ElementType;
typedef struct Binary {ElementType data;struct Binary *lchild;struct Binary *rchild;
} *BinaryTree;/* Recursive implementation 1 */
BinaryTree CreateBinaryTree_1(void)
{BinaryTree bt;char ch;scanf(%c, ch);if (ch #) {bt NULL;} else {bt (BinaryTree)malloc(sizeof(struct Binary));bt-data ch;bt-lchild CreateBinaryTree_1();bt-rchild CreateBinaryTree_1();}return bt;
}/* Recursive implementation 2 */
void CreateBinaryTree_2(BinaryTree *bt)
{char ch;scanf(%c, ch);if (ch #) {*bt NULL;} else {*bt (BinaryTree)malloc(sizeof(struct Binary));(*bt)-data ch;CreateBinaryTree_2(((*bt)-lchild));CreateBinaryTree_2(((*bt)-rchild));}
}void PreviousOrderTraverse(BinaryTree T)
{if (T NULL) {return;}printf(%c, T-data);PreviousOrderTraverse(T-lchild);PreviousOrderTraverse(T-rchild);
}int main(void)
{BinaryTree bt;// bt CreateBinaryTree_1();CreateBinaryTree_2(bt);PreviousOrderTraverse(bt);return 0;
}运行结果
