下载文档原格式
完全二叉树叶子结点计算公式
对于完全二叉树，假设叶子结点数为n，节点总数为m，则有以下计
算公式：
1.若n为偶数，则有：
$n = \frac{m}{2}+1$。
2.若n为奇数，则有：
$n = \frac{m+1}{2}$。
这两个公式的推导如下：
首先，完全二叉树的定义是除最后一层外，每层节点都是满的，并且
最后一层的节点从左到右排列。
因此，对于一个完全二叉树，最后一层的
节点数n一定小于等于2的h次方（h为树的高度）。
而根据完全二叉树
的性质，倒数第二层节点数是最后一层节点数的两倍或一倍加一，即：n=2n（n为偶数）。
或。
n=2n+1（n为奇数）。
因此，节点总数m可以表示为：
当n为偶数时。
m=2n+m'，其中m'为倒数第二层节点数。
而根据倒数第二层节点数是最后一层节点数的两倍或一倍加一，可得：m'=2(n/2)。
代入上式，可得：
m=n+2(n/2)=m/2+n。
移项可得：
n=m/2+1。
当n为奇数时。
同理可得：
m=2n-1+m'。
m'=2((n-1)/2)+1=n-1。
代入上式，可得：
m=n+(n-1)=2n-1。
移项可得：
n=(m+1)/2。
因此，对于完全二叉树，叶子结点数n可以通过以上公式计算得到。
完全二叉树的节点数计算公式
在计算完全二叉树的节点数时，可以分为两种情况进行讨论：假设树的高度为H。
第一种情况是当完全二叉树的高度为H-1时，除去最后一层，其他层的节点都是满的。
此时，完全二叉树的节点数可以通过公式计算得出：
2^(H-1)-1
第二种情况是当完全二叉树的最后一层不满时，假设最后一层的节点数为N。
在最后一层的节点中，从左到右依次编号为1,2,3,...,N。
对于第一种情况下的每个节点，其左子节点的编号为2x，右子节点的编号为2x+1、那么对于第二种情况下的每个节点，其编号将会超过
2^(H-1)。
因此，第二种情况下的节点数可以通过公式计算得出：2^(H-1)-1+N。
综上所述，对于一棵完全二叉树，其节点数的计算公式为：
节点数=2^(H-1)-1，当最后一层为空
节点数=2^(H-1)-1+N，当最后一层不为空
其中H为完全二叉树的高度，N为最后一层的节点数。
举个例子来说明这个公式的计算过程：
假设完全二叉树的高度为3，最后一层的节点数为3、那么根据公式可以算出：
节点数=2^(3-1)-1+3=2^2-1+3=4-1+3=6
也就是说，这个完全二叉树共有6个节点。
二叉树遍历典型例题正文:二叉树的遍历是指按照某种顺序访问二叉树中的所有节点。
常见的二叉树遍历方式有三种：前序遍历、中序遍历和后序遍历。
下面将以一个典型的例题来介绍这三种遍历方式的应用。
假设有一个二叉树如下所示：```1/2 3/4 5 6```首先介绍前序遍历。
前序遍历的顺序是先访问根节点，然后分别遍历左子树和右子树。
对于上面的二叉树，前序遍历的结果是1, 2, 4, 3, 5, 6。
接下来是中序遍历。
中序遍历的顺序是先遍历左子树，然后访问根节点，最后遍历右子树。
对于上面的二叉树，中序遍历的结果是2, 4, 1, 5, 3, 6。
最后是后序遍历。
后序遍历的顺序是先遍历左子树，然后遍历右子树，最后访问根节点。
对于上面的二叉树，后序遍历的结果是4, 2, 5, 6, 3, 1。
以上就是三种常见的二叉树遍历方式。
在实际应用中，二叉树的遍历经常用于查找、删除、插入等操作。
例如，在前序遍历中，可以用来复制一棵二叉树；在中序遍历中，可以用来对树进行排序；在后序遍历中，可以用来释放二叉树的内存等。
除了以上介绍的三种遍历方式，还存在一种更特殊的遍历方式，即层序遍历。
层序遍历是逐层访问二叉树节点的方式，从上到下、从左到右。
对于上面的二叉树，层序遍历的结果是1, 2, 3, 4, 5, 6。
在实际应用中，根据具体的问题要求，选择合适的遍历方式能够更加高效地解决问题。
因此，对于二叉树的遍历问题，我们需要熟练掌握各种遍历方式的特点和应用场景，以便于在实际问题中灵活运用。
完全二叉树结点计算方法
1.定义
(1)二叉树中所有叶子节点都在同一层；
(2)除了叶子节点外的每一层上，节点都从左到右完全填充；
(3)树中每个节点的孩子数总是相同的，或者是0，1，2三种情况。
2.计算结点数
（1）若完全二叉树为奇数层的完全二叉树，则树中结点数可以由下式计算：
N=(2^H-1)
其中，N表示结点个数，H表示树的高度。
（2）若完全二叉树为偶数层的完全二叉树，则树中结点数可以由下式计算：
N=(2^(H-1)-1)+2^(H-2)
其中，N表示结点个数，H表示树的高度。
3.应用
完全二叉树在数据结构中的应用比较广泛，常用在实现二叉堆，希尔排序，二叉树等中。
完全二叉树有把满二叉树转换为完全二叉树的性质，所以它比满二叉树更有利于表示和存储，可以把它存储在一维数组中，这是满二叉树所不能相比的。
完全二叉树也应用在了计算机科学中，如字符匹配，编码，词典等方面。
另外，定义完全二叉树及其结点的计算也有实际应用。
数据结构与算法系列研究五——树、⼆叉树、三叉树、平衡排序⼆叉树AVL树、⼆叉树、三叉树、平衡排序⼆叉树AVL⼀、树的定义树是计算机算法最重要的⾮线性结构。
树中每个数据元素⾄多有⼀个直接前驱，但可以有多个直接后继。
树是⼀种以分⽀关系定义的层次结构。
a.树是n(≥0)结点组成的有限集合。
{N.沃恩}(树是n(n≥1)个结点组成的有限集合。
{D.E.Knuth})在任意⼀棵⾮空树中：⑴有且仅有⼀个没有前驱的结点----根(root)。
⑵当n>1时，其余结点有且仅有⼀个直接前驱。
⑶所有结点都可以有0个或多个后继。
b. 树是n(n≥0)个结点组成的有限集合。
在任意⼀棵⾮空树中：⑴有⼀个特定的称为根（root）的结点。
⑵当n>1时，其余结点分为ｍ（ｍ≥0）个互不相交的⼦集T1，T2，…，Tm。
每个集合本⾝⼜是⼀棵树，并且称为根的⼦树（subtree）树的固有特性---递归性。
即⾮空树是由若⼲棵⼦树组成，⽽⼦树⼜可以由若⼲棵更⼩的⼦树组成。
树的基本操作1、InitTree(&T) 初始化2、DestroyTree(&T) 撤消树3、CreatTree(&T,F) 按F的定义⽣成树4、ClearTree(&T) 清除5、TreeEmpty(T) 判树空6、TreeDepth(T) 求树的深度7、Root(T) 返回根结点8、Parent(T,x) 返回结点 x 的双亲9、Child(T,x,i) 返回结点 x 的第i 个孩⼦10、InsertChild(&T,&p,i,x) 把 x 插⼊到 P的第i棵⼦树处11、DeleteChild(&T,&p,i) 删除结点P的第i棵⼦树12、traverse(T) 遍历树的结点：包含⼀个数据元素及若⼲指向⼦树的分⽀。
●结点的度: 结点拥有⼦树的数⽬●叶结点: 度为零的结点●分枝结点: 度⾮零的结点●树的度: 树中各结点度的最⼤值●孩⼦: 树中某个结点的⼦树的根●双亲: 结点的直接前驱●兄弟: 同⼀双亲的孩⼦互称兄弟●祖先: 从根结点到某结点j 路径上的所有结点（不包括指定结点）。
二叉树算结点的公式
在二叉树中，节点是二叉树的基本组成单元之一。
计算二叉树中节点的数量是二叉树问题中最基本的问题之一。
如果我们知道二叉树的深度，那么可以通过一个公式来计算出二叉树中节点的数量。
二叉树中节点数量的公式为：N = 2^h - 1，其中 N 表示节点数量，h 表示二叉树的深度。
深度为 0 的二叉树只有一个根节点，深度为 1 的二叉树有一个根节点和两个子节点，深度为 2 的二叉树有一个根节点、两个子节点和四个孙子节点。
可以看出，每增加一层深度，节点数量就会翻倍。
因此，在任意深度的二叉树中，我们都可以通过这个公式来计算出节点数量。
例如，如果一个二叉树的深度为 3，那么它的节点数量为：
N = 2^3 - 1 = 7
这个公式虽然简单，但是非常实用。
我们可以用它来快速计算二叉树中节点的数量，从而更好地理解二叉树的结构和性质。
- 1 -。
树和二叉树的计算公式
树和二叉树是计算机科学中重要的数据结构，它们可以用于各种算法和数据处理应用。
在计算树和二叉树的性质和操作时，需要使用一些计算公式。
一、树的计算公式
1. 节点总数公式：假设一棵树有n个节点，那么它的节点总数
为n=1+r1+r2+...+rk，其中r1、r2、...、rk分别表示每个节点的
子节点数。
2. 叶子节点数公式：一棵树的叶子节点数等于每个非叶节点子
节点数之和加1，即l=r1+r2+...+rk+1。
3. 深度公式：一棵树的深度为从根节点到最深叶子节点的路径
长度，可以用递归的方式计算：d(T)=max{d(T1),d(T2),...,d(Tk)}+1，其中T1、T2、...、Tk是根节点的子树，d(Ti)表示第i个子树的深度。
二、二叉树的计算公式
1. 节点总数公式：假设一棵二叉树有n个节点，那么它的节点
总数为n=2^h-1，其中h为树的高度。
2. 叶子节点数公式：一棵二叉树的叶子节点数等于度数为2的
节点数加1，即l=n/2+1。
3. 深度公式：一棵二叉树的深度为从根节点到最深叶子节点的
路径长度，可以用递归的方式计算：d(T)=max{d(T1),d(T2)}+1，其
中T1、T2是根节点的左右子树，d(Ti)表示第i个子树的深度。
以上是树和二叉树的一些常用计算公式，可以用于分析和设计算法，帮助开发人员更好地理解和应用这些数据结构。
二叉树知识点总结二叉树是一种常见的数据结构，它由节点和边组成，每个节点最多有两个子节点。
以下是关于二叉树的知识点总结。
1. 二叉树的基本概念二叉树是一种树形结构，它由节点和边组成。
每个节点最多有两个子节点，分别称为左子节点和右子节点。
如果一个节点没有子节点，则称其为叶子节点。
二叉树可以为空。
2. 二叉树的遍历方式遍历是指按照一定顺序访问二叉树中的所有节点。
常见的遍历方式有前序遍历、中序遍历和后序遍历。
前序遍历：先访问当前节点，然后递归访问左子树和右子树。
中序遍历：先递归访问左子树，然后访问当前节点，最后递归访问右子树。
后序遍历：先递归访问左子树和右子树，最后访问当前节点。
3. 二叉搜索树二叉搜索树（Binary Search Tree）也称为有序二叉树或排序二叉树。
它是一种特殊的二叉树，在满足以下条件的情况下被称为“搜索”：对于任意节点，其左子树中的所有节点的值都小于该节点的值。
对于任意节点，其右子树中的所有节点的值都大于该节点的值。
左右子树也分别为二叉搜索树。
二叉搜索树支持快速查找、插入和删除操作。
它还有一些变种，如平衡二叉搜索树（AVL Tree）和红黑树（Red-Black Tree）等。
4. 二叉堆二叉堆是一种特殊的完全二叉树，它分为最大堆和最小堆两种类型。
最大堆满足父节点的值大于等于其子节点的值，最小堆满足父节点的值小于等于其子节点的值。
在最大堆中，根节点是整个堆中最大的元素；在最小堆中，根节点是整个堆中最小的元素。
二叉堆常用来实现优先队列（Priority Queue），即按照一定优先级顺序处理元素。
5. 二叉树常见问题5.1 判断是否为平衡二叉树平衡二叉树（Balanced Binary Tree）是指任意节点左右子树高度差不超过1的二叉搜索树。
判断一个二叉搜索树是否为平衡二叉树可以通过递归遍历每个节点，计算其左右子树的高度差。
5.2 判断是否为完全二叉树完全二叉树（Complete Binary Tree）是指除了最后一层外，其他层都是满的，并且最后一层的节点都靠左排列的二叉树。
n个节点的二叉树个数 公式 二叉树是一种常见的数据结构，它由n个节点组成，每个节点最多有两个子节点。在计算机科学中，二叉树被广泛应用于搜索、排序、编码和解码等领域。在本文中，我们将探讨如何计算n个节点的二叉树的个数。
我们需要了解一些基本概念。在二叉树中，每个节点都有一个唯一
的父节点，除了根节点。根节点是二叉树的顶部节点，它没有父节点。叶子节点是没有子节点的节点。内部节点是有子节点的节点。深度是从根节点到节点的路径长度。高度是从节点到最远叶子节点的路径长度。
现在，我们来看一下如何计算n个节点的二叉树的个数。假设我们
有n个节点，我们可以将它们分成两个部分：左子树和右子树。左子树和右子树都是二叉树，它们的节点数之和等于n-1。因此，我们可以使用递归的方法来计算n个节点的二叉树的个数。
具体来说，我们可以定义一个函数f(n)，它表示n个节点的二叉树
的个数。对于任意一个节点i，它可以作为根节点，左子树有i-1个节点，右子树有n-i个节点。因此，f(n)可以表示为：
f(n) = ∑f(i-1) * f(n-i) (i=1,2,...,n)
这个公式的意思是，对于每个节点i，它的左子树和右子树的个数
相乘，然后将所有节点的结果相加。这个公式可以用来计算任意数量的节点的二叉树的个数。
例如，当n=3时，我们可以得到：
f(3) = f(0) * f(2) + f(1) * f(1) + f(2) * f(0)
= 1 * 2 + 1 * 1 + 2 * 1 = 5
因此，当有3个节点时，有5个不同的二叉树。
当n=4时，我们可以得到：
f(4) = f(0) * f(3) + f(1) * f(2) + f(2) * f(1) + f(3) * f(0)
= 1 * 5 + 1 * 2 + 2 * 1 + 5 * 1 = 14
因此，当有4个节点时，有14个不同的二叉树。
我们可以使用递归的方法来计算n个节点的二叉树的个数。这个公
二叉树的深度计算方法二叉树是一种常见的树形数据结构，在二叉树中，每个节点最多有两个子节点，分别称为左子节点和右子节点。
深度是指从根节点到最远叶子节点的路径的长度，或者是从根节点到一些节点的路径的长度。
计算二叉树的深度有多种方法，下面将介绍几种常用的方法。
方法一：递归法递归法是最常用的计算二叉树深度的方法之一、对于一个二叉树来说，它的深度等于左子树的深度和右子树的深度中的较大值加1、递归地计算左子树和右子树的深度，然后取较大值加1即可得到二叉树的深度。
具体的实现过程如下：1.如果二叉树为空，返回0；2. 否则，递归计算左子树的深度，记为left_depth；3. 递归计算右子树的深度，记为right_depth；4. 返回left_depth和right_depth中的较大值加1代码实现如下：```pythondef maxDepth(root):if root is None:return 0leftDepth = maxDepth(root.left)rightDepth = maxDepth(root.right)return max(leftDepth, rightDepth) + 1```方法二：层序遍历法层序遍历法是另一种计算二叉树深度的常用方法。
通过层序遍历二叉树，每一层遍历完后层数加1，直到遍历到最后一层为止，即可得到二叉树的深度。
具体的实现过程如下：1.定义一个队列，将根节点入队；2.初始化深度为0；3.循环直到队列为空：-获取当前队列中的节点数，记为当前层的节点数；-循环当前层的节点数次：-将当前节点出队；-将当前节点的左子节点和右子节点入队；-深度加1；4.返回深度。
代码实现如下：```pythondef maxDepth(root):if root is None:return 0queue = [root]depth = 0while queue:num = len(queue)for _ in range(num):node = queue.pop(0)if node.left:queue.append(node.left)if node.right:queue.append(node.right)depth += 1return depth```方法三：迭代法迭代法是另一种计算二叉树深度的常用方法。
二叉树基本运算算法的实现
二叉树是一种常见的数据结构，基本运算算法包括二叉树的遍历、查找、插入、删除等操作。
下面是这些算法的实现：
1. 二叉树遍历：二叉树遍历有三种方式，分别是前序遍历、中序遍历和后序遍历。
其中，前序遍历先访问根节点，再访问左子树和右子树；中序遍历先访问左子树，再访问根节点和右子树；后序遍历先访问左子树，再访问右子树和根节点。
遍历可以使用递归算法或栈实现。
2. 二叉树查找：二叉树查找可以使用递归算法或循环算法实现。
递归算法通过比较节点值实现查找，如果查找值小于当前节点值，则在左子树中查找，否则在右子树中查找。
循环算法使用二叉树的特性，比较查找值和当前节点值的大小，根据大小关系不断移动到左子树或右子树中进行查找，直到找到目标节点或遍历到叶子节点为止。
3. 二叉树插入：二叉树插入需要先查找到插入位置，然后在该位置插入一个新节点。
插入操作可以使用递归算法或循环算法实现。
4. 二叉树删除：二叉树删除分为三种情况：删除叶子节点、删除只有一个孩子的节点和删除有两个孩子的节点。
删除叶子节点很简单，只需要将其父节点的指针设为NULL即可。
删除只有一个孩子的节点需要将父节点的指针指向该节点的
孩子节点。
删除有两个孩子的节点需要找到该节点的后继节点（或前驱节点），将后继节点的值复制到该节点中，然后删除后继节点。
上述算法的实现需要根据具体的编程语言进行调整和实现。
二叉树算结点的公式二叉树是一种最常用的数据结构之一，它由根节点、左子树、右子树构成。
在二叉树中，每个节点最多有两个子节点，一个是左子节点，一个是右子节点。
在计算二叉树的结点数时，我们需要运用以下公式：设该二叉树的结点数为n，叶子结点数为m，则有：n = m + 1 + 度为2的非叶子结点数由此可以看出，在二叉树中，结点的数量与叶子结点和度为2的非叶子结点数量有直接关系。
以下是二叉树结点计算公式的详细解释：1. 叶子结点的个数叶子结点是没有子节点的结点，因此当我们需要计算二叉树的结点数时，首先需要得到叶子结点的数量。
计算叶子结点数量的方法很简单，只要按照以下公式进行计算即可：m = $n_0$其中，m代表叶子结点数量，$n_0$代表度为0的结点数量。
在计算二叉树结点数时，度为0的结点数量即为叶子结点数量。
2. 度为2的非叶子结点数量度为2的非叶子结点是有两个子节点的结点，它们是连接二叉树的关键节点。
由于它们都有两个子节点，因此度为2的非叶子结点数量对整个二叉树的结构和大小都有很大的影响。
计算方法如下：设度为2的非叶子结点数量为k，则有：$k = n_2$其中，$n_2$代表度为2的结点数量。
3. 二叉树结点数量当我们得到了叶子结点和度为2的非叶子结点数量后，就可以按照公式计算整个二叉树的结点数量了。
如下所示：$n = m + 1 + k$其中，n代表二叉树的结点数量，m代表叶子结点数量，k代表度为2的非叶子结点数量。
最终得到的n就是整个二叉树的结点数量。
综上所述，二叉树的结点数量与叶子结点数量和度为2的非叶子结点数量有关。
要计算二叉树的结点数量，我们需要先计算叶子结点和度为2的非叶子结点数量，再按照公式进行计算。
二叉树的结点数量公式可以为我们快速、准确地计算二叉树中的结点数量提供帮助。
}
}
return count;
}
main()
{ NODE *T;
int left_number;
printf("请输入一棵树:\n" );
T=create();
printf("\n");
if(!T) printf("This is a empty binary tree.");
else{
left_number=run(T);
printf("\n这棵树共有%d 个子叶. \n", left_number);
}
printf("\n");}
四、实验结果与分析
（2）习题1：注意叶子结点是指该结点既没有左孩子又没有右孩子，采用递归算法就很容易计算出其数目。
实验结果如图：
五、实验心得及体会
本次实验加深了我对树的各种遍历方法。
尤其是先序遍历。
在建立树的过程中更是采取了递归的方法。
有的算法用递归表示要比用循环表示简洁精练[如二叉树的遍历]，代码更简洁清晰，可读性更好有的算法递归能实现循环不一定能实现，递归的内部实现要消耗额外的空间和时间。
所以说循环的效率更高。
二叉树结点计算公式一、二叉树的结点计算公式1. 结点数计算公式二叉树的结点数可以通过递归计算的方式得到。
对于一个二叉树，其结点数等于左子树的结点数加上右子树的结点数再加1（根结点）。
2. 叶子结点数计算公式叶子结点是指没有子结点的结点。
二叉树的叶子结点数可以通过递归计算的方式得到。
对于一个二叉树，如果根结点为空，则叶子结点数为0；否则，叶子结点数等于左子树的叶子结点数加上右子树的叶子结点数。
3. 二叉树的深度计算公式二叉树的深度是指从根结点到叶子结点的最长路径长度。
可以通过递归计算的方式得到二叉树的深度。
对于一个二叉树，如果根结点为空，则深度为0；否则，深度等于左子树的深度和右子树的深度中的较大值加1。
4. 二叉树的高度计算公式二叉树的高度是指从叶子结点到根结点的最长路径长度。
可以通过递归计算的方式得到二叉树的高度。
对于一个二叉树，如果根结点为空，则高度为0；否则，高度等于左子树的高度和右子树的高度中的较大值加1。
5. 二叉树的平衡因子计算公式二叉树的平衡因子是指一个结点的左子树的高度减去右子树的高度。
可以通过递归计算的方式得到二叉树的平衡因子。
对于一个二叉树，如果根结点为空，则平衡因子为0；否则，平衡因子等于左子树的高度减去右子树的高度。
1. 计算二叉树的结点数假设有一棵二叉树，根结点是A，左子树是B，右子树是C。
根据结点计算公式，结点数等于左子树的结点数加上右子树的结点数再加1，即结点数=结点数(B) + 结点数(C) + 1。
2. 计算二叉树的深度假设有一棵二叉树，根结点是A，左子树是B，右子树是C。
根据结点计算公式，深度等于左子树的深度和右子树的深度中的较大值加1，即深度=MAX(深度(B), 深度(C)) + 1。
3. 计算二叉树的平衡因子假设有一棵二叉树，根结点是A，左子树是B，右子树是C。
根据结点计算公式，平衡因子等于左子树的高度减去右子树的高度，即平衡因子=高度(B) - 高度(C)。
实用标准 文档大全 /*一下总结一些二叉树的常见操作：包括建立二叉树 先/中/后序遍历二叉树 求二叉树的叶子节点个数 求二叉树的单分支节点个数 计算二叉树双分支节点个数 计算二叉树的高度 计算二叉树的所有叶子节点数*/ #include //c语言的头文件 #include//c语言的头文件 stdlib.h千万别写错了 #define Maxsize 100 /*创建二叉树的节点*/ typedef struct BTNode //结构体 struct 是关键字不能省略 结构体名字可以省略（为无名结构体） //成员类型可以是基本型或者构造形，最后的为结构体变量。 { char data; struct BTNode *lchild,*rchild; }*Bitree; /*使用先序建立二叉树*/ Bitree Createtree() //树的建立 { char ch; Bitree T; ch=getchar(); //输入一个二叉树数据 if(ch==' ') //' '中间有一个空格的。
T=NULL; else { T=(Bitree)malloc(sizeof(Bitree)); //生成二叉树 (分配类型 *)malloc(分配元素个数 *sizeof(分配类型)) T->data=ch; T->lchild=Createtree(); //递归创建左子树 T->rchild=Createtree(); //地柜创建右子树 } return T;//返回根节点 }
/*下面先序遍历二叉树*/ 实用标准
文档大全 /*void preorder(Bitree T) //先序遍历 { if(T) { printf("%c-",T->data); preorder(T->lchild); preorder(T->rchild); } } */
/*下面先序遍历二叉树非递归算法设计*/ void preorder(Bitree T) //先序遍历非递归算法设计 { Bitree st[Maxsize];//定义循环队列存放节点的指针 Bitree p; int top=-1; //栈置空 if(T) { top++; st[top]=T; //根节点进栈 while(top>-1) //栈不空时循环 { p=st[top]; //栈顶指针出栈 top--; printf("%c-",p->data ); if(p->rchild !=NULL) //右孩子存在进栈 { top++; st[top]=p->rchild ; } if(p->lchild !=NULL) //左孩子存在进栈 { top++; st[top]=p->lchild ; } } printf("\n"); } } 实用标准 文档大全 /*下面中序遍历二叉树*/ /*void inorder(Bitree T) //中序遍历 { if(T) { inorder(T->lchild); printf("%c-",T->data); inorder(T->rchild); } } */
/*下面中序遍历二叉树非递归算法设计*/ void inorder(Bitree T) //中序遍历 { Bitree st[Maxsize]; //定义循环队列，存放节点的指针 Bitree p; int top=-1; if(T) { p=T; while (top>-1||p!=NULL) //栈不空或者*不空是循环 { while(p!=NULL) //扫描*p的所有左孩子并进栈 { top++; st[top]=p; p=p->lchild ; } if(top>-1) { p=st[top]; //出栈*p节点，它没有右孩子或右孩子已被访问。 top--; 实用标准 文档大全 printf("%c-",p->data ); //访问 p=p->rchild ; //扫描*p的右孩子节点 } } printf("\n"); } }
/*下面后序遍历二叉树*/ /*void postorder(Bitree T) //后序遍历 { if(T) { postorder(T->lchild); postorder(T->rchild); printf("%c-",T->data); } } */
/*二叉树后序遍历非递归算法设计*/ void postorder(Bitree T) //后序遍历非递归 { Bitree st[Maxsize]; Bitree p=T,q; int flag; //作为一个标志处理栈定时候用 int top=-1; //栈置空 if(T) { do { while(p) //将*p所在的左节点进栈 { top++; 实用标准 文档大全 st[top]=p; p=p->lchild ; } q=NULL; flag=1; //设置flag=1表示处理栈顶节点 while(top!=-1&&flag==1) { p=st[top]; if(p->rchild==q) //右孩子不存在或者右孩子已被访问，访问之 { printf("%c-",p->data ); top--; q=p; //让q指向刚被访问的节点 } else { p=p->rchild ; //p指向右孩子 flag=0; //设置flag=0表示栈顶节点处理完毕 } } }while(top!=-1) ;//栈不空是循环 printf("\n"); } }
/*下面层序遍历二叉树*/ //（层序遍历的模板） void levelorder(Bitree T) //层序遍历二叉树 { Bitree p; Bitree qu[Maxsize]; //定义一个循环队列 int front, rear; //定义队头队尾指针 front=0; //队列置空 rear=0; rear++; //根节点进队 qu[rear]=T; while(front!=rear) //队列不空 实用标准 文档大全 { front=(front+1)%Maxsize; //对头出队列 p=qu[front]; printf("%C-",p->data ); //访问对头节点 if(p->lchild !=NULL) //左子树不空进队 { rear=(rear+1)%Maxsize; qu[rear]=p->lchild ; } if(p->rchild !=NULL) //右子树不空进队 { rear=(rear+1)%Maxsize; qu[rear]=p->rchild ; } } }
/*计算二叉树节点数*/ /*方法一*/ /*int num(Bitree T) { if(T==NULL) return 0; else { return num(T->lchild )+num(T->rchild )+1; } }
*/
/*方法二*/ int num (Bitree T) 实用标准 文档大全 { if(T!=NULL) return num(T->lchild )+num(T->rchild )+1; return 0; }
/*下面程序段计算二叉树的叶子节点个数*/ int countleaf(Bitree T) { if(T==NULL) //如果节点为空，则返回0 return 0; else if((T->lchild==NULL) && (T->rchild==NULL))//否则如果节点左右孩子有一个为空，另一个存在，则返回1 return 1; else return(countleaf(T->lchild)+countleaf(T->rchild));//否则返回左右子树叶子节点之和 }
/*下面程序段计算二叉树的单分支节点个数*/ int Sfenzhi(Bitree T) { if(T==NULL) return 0; else if (T->lchild==NULL&&T->rchild!=NULL||T->lchild!=NULL&&T->rchild==NULL) //为单分支节点 return Sfenzhi(T->lchild )+Sfenzhi(T->rchild )+1; else return Sfenzhi(T->lchild )+Sfenzhi(T->rchild ); }
/*下面程序段计算二叉树的双分支节点个数*/ int Dfenzhi(Bitree T) { if(T==NULL) return 0;
