二叉树创建与销毁操作详解

本文主要是介绍二叉树创建与销毁操作详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、通过前序遍历的数组构建二叉树

1.1 递归思路

1.2 递归分支图

1.3 递归栈帧图

1.4 C语言实现

二、二叉树的销毁

2.1 递归思路

2.2 递归分支图

2.3 递归栈帧图

2.4 C语言实现

---

一、通过前序遍历的数组构建二叉树

牛客网链接：二叉树遍历_牛客题霸_牛客网
以"ABD##E#H##CF##G##"为例；“#”代表空树

1.1 递归思路

考虑特殊情况：

1. 如果为#，则返回NULL
2. 如果不为#，则创建一个结点

考虑一般情况：

1. 前序遍历先构建左数再构建右树

2. 递归将每个结点都看作是根节点来构建二叉树

1.2 递归分支图

1.3 递归栈帧图

1.4 C语言实现

注意事项：递归会创建栈帧，栈帧间的变量值互不影响，所以要想每次调用函数都要改变数组的下标，就要使用指针的方法去修改变量。

BTNode* CreateTree(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc");exit(1);}root->data = a[(*pi)++];root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;
}

二、二叉树的销毁

2.1 递归思路

不可以用循环原因：销毁根节点后无法找到左右子树的结点。即便保存了左右子树的结点后无法找到下一层的结点。

使用递归的特性：从叶子节点开始释放空间，从而达到销毁的目的

2.2 递归分支图

2.3 递归栈帧图

2.4 C语言实现

void BinaryTreeDestory(BTNode* root)
{//判空if (root == NULL){return NULL;}//释放左子树BinaryTreeDestory(root->left);//释放右子树BinaryTreeDestory(root->right);//释放本身结点free(root);
}

这篇关于二叉树创建与销毁操作详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---