编写程序实现二叉树的基本运算:创建二叉树、销毁二叉树、查找节点、求二叉树的高度、输出二叉树
时间: 2024-06-20 13:02:49 浏览: 109
编写程序实现二叉树的基本运算包括:
1. 创建二叉树:二叉树可以通过前序遍历、中序遍历或后序遍历的序列来创建,这里以前序遍历为例。具体方法是:先读入一个节点的值,如果该节点值不为0,则新建一个节点,并将读入的值赋给该节点;如果该节点值为0,则直接返回NULL。然后递归调用创建二叉树函数,分别创建该节点的左子树和右子树。
2. 销毁二叉树:递归地销毁左子树和右子树,并释放每个节点的内存空间,最后将根节点设置为NULL。
3. 查找节点:从根节点开始,如果当前节点的值等于查找值,则返回该节点;如果当前节点的值大于查找值,则递归地在左子树中查找;如果当前节点的值小于查找值,则递归地在右子树中查找。
4. 求二叉树的高度:递归地求左子树和右子树的高度,然后将其较大值加1即为整棵二叉树的高度。
5. 输出二叉树:可以通过前序遍历、中序遍历或后序遍历的方式输出二叉树。这里以前序遍历为例。具体方法是:先输出当前节点的值,然后递归地输出左子树和右子树。
阅读全文