下载文档原格式
二叉树知识点总结1. 二叉树的性质1.1 二叉树的性质一：二叉树的深度二叉树的深度是指从根节点到叶子节点的最长路径长度。
对于一个空树而言，它的深度为0；对于只有一个根节点的树而言，它的深度为1。
根据定义可知，深度为k的二叉树中，叶子节点的深度值为k。
由此可知，二叉树的深度为所有叶子节点深度的最大值。
1.2 二叉树的性质二：二叉树的高度二叉树的高度是指从根节点到叶子节点的最短路径长度。
对于一个空树而言，它的高度为0；对于只有一个根节点的树而言，它的高度为1。
由此可知，二叉树的高度总是比深度大一。
1.3 二叉树的性质三：二叉树的节点数量对于一个深度为k的二叉树而言，它最多包含2^k - 1个节点。
而对于一个拥有n个节点的二叉树而言，它的深度最多为log2(n+1)。
1.4 二叉树的性质四：满二叉树满二叉树是一种特殊类型的二叉树，它的每个节点要么是叶子节点，要么拥有两个子节点。
满二叉树的性质是：对于深度为k的满二叉树而言，它的节点数量一定是2^k - 1。
1.5 二叉树的性质五：完全二叉树完全二叉树是一种特殊类型的二叉树，它的所有叶子节点都集中在树的最低两层，并且最后一层的叶子节点从左到右依次排列。
对于一个深度为k的完全二叉树而言，它的节点数量一定在2^(k-1)和2^k之间。
2. 二叉树的遍历二叉树的遍历是指按照一定的顺序访问二叉树的所有节点。
二叉树的遍历主要包括前序遍历、中序遍历和后序遍历三种。
2.1 前序遍历（Pre-order traversal）前序遍历的顺序是：根节点 -> 左子树 -> 右子树。
对于一个二叉树而言，前序遍历的结果就是按照“根-左-右”的顺序访问所有节点。
2.2 中序遍历（In-order traversal）中序遍历的顺序是：左子树 -> 根节点 -> 右子树。
对于一个二叉树而言，中序遍历的结果就是按照“左-根-右”的顺序访问所有节点。
2.3 后序遍历（Post-order traversal）后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
基本二叉树知识讲解一、有关二叉树的学习性质1：二叉树上叶子结点数等于度为2的结点数加1。
性质2：二叉树的第i层上至多有2的i次方减1个结点（i>=1）。
性质3：深度为h的二叉树至多有2的h次方减1个结点。
满二叉树：在一棵二叉树中，当第i层的结点树为2的i次方减1个时，称此层的结点数是满的。
当一棵二叉树中的每一层都满时，称此树为满二叉树。
特性：除叶子结点以外的其他的结点的度皆为2，且叶子结点在同一层上。
深度为h的满二叉树中的结点数为2的h次方减1。
性质4：设含有n个结点的完全二叉树的深度为k，则k=(int)(log2n)+1,即深度k等于log2n的整数部分再加1。
二叉树的存储结构1：顺序存储结构二叉树的顺序存储结构类型定义如下：#define TREEMINSIZE 10typedef struct{BTreeDT(数据类型) *base;int spacesize;BTreeDT nullvalue;}SeqTree;2：链式存储结构（一般的二叉树主要采用链式存储结构通常有二叉链表和三叉链表两种形式）1>二叉链表存储结构二叉链表中的每个结点由data，lchild和rchild三个域组成，定义如下：typedef struct bkbtnode{BTreeDT data;struct bkbtnode *lchild;struct bkbtnode *rchild;}BTNode,*BKBTree;在二叉链表中，查找某结点的孩子很容易实现，但查找某结点的双亲不方便。
一棵喊有n个结点的二叉树采用二叉链表存储时，将有2n-（n-1）=n+1个指针域是空的。
2>三叉链表存储结构typedef struct tkbtnode{BTreeDT data;struct tkbtnode *lchild;struct tkbtnode *rchild;struct tkbtnode *parent;}TKBTNode,*TKBTree;其中，parent域存放该结点双亲的指针。
二叉树的广义表表示法概述及解释说明1. 引言1.1 概述二叉树是一种常见的数据结构，在计算机科学中广泛应用。
为了有效地表示和操作二叉树，人们提出了各种表示方法。
其中，二叉树的广义表表示法是一种常用且灵活的方式。
1.2 文章结构本文将首先介绍二叉树的广义表表示法的定义和特点。
然后，我们将详细讨论广义表的表示方法，并解释广义表与二叉树之间的关系。
接下来，我们将介绍如何使用广义表表示方法构建二叉树，并讨论相应的转换方法。
最后，我们将探讨在广义表表示法下如何进行遍历和操作二叉树，并提供相应的实现方法和示例场景。
1.3 目的本文的目标是全面而清晰地介绍二叉树的广义表表示法，使读者对该方法有深入理解。
通过学习本文，读者将能够掌握如何使用广义表表示法构建和操作二叉树，并能够在实际问题中应用相关技巧。
同时，本文还旨在帮助读者提高对数据结构和算法相关知识的理解水平，并培养解决实际问题时分析和抽象的能力。
这样，我们完成了“1. 引言”部分的详细撰写。
2. 二叉树的广义表表示法2.1 定义和特点二叉树是一种常用的数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉树的广义表表示法是一种将二叉树以字符串形式进行表示的方法。
在广义表中，以括号形式将二叉树的节点和子树进行包裹，并使用逗号分隔各个元素。
2.2 广义表的表示方法广义表由以下部分组成：- 括号：用来包裹二叉树的节点和子树。
- 节点值：表示该节点存储的数据值。
- 逗号：用于分隔各个元素。
- 空格：可选，用于提高可读性。
例如，假设有一个二叉树如下所示：```A/ \B C/ \D E```它可以表示为广义表形式为：`(A, (B, (), ()), (C, (D, (), ()), (E, (), ())))`解释上述广义表：- `(A`代表当前节点的值为A。
- `(B, (), ())`代表当前节点的左子节点为空并且右子节点为空。
- `(C, (D, (), ()), (E, (), ()))`代表当前节点的左子节点为D、右子节点为E。
