数据结构——链式二叉树（2）

目录

接上篇文章，我们接着学习关于链式二叉树的几种操作。

🍁一、二叉树的销毁

//销毁
void FreeDestroy(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	FreeDestroy(root->left);
	FreeDestroy(root->right);
	free(root);
}

对于销毁，使用前序或者后序遍历都可以，但前序需要在销毁根结点的之前用临时指针保存根节点的左右子树，这样比较麻烦，所以最合适的还是后序，先销毁左右子树，然后才销毁根节点，这样按顺序的来就可以了。而我们使用递归最重要的是如何转换为子问题以及最小子递归的返回条件问题，这里很显然我们访问到NULL时就可以返回了，然后在依次销毁。

🍁二、在二叉树中查找某个数，并返回该结点

//在二叉树中找某个数的结点
BTNode* TreeFind(BTNode* root,int x)
{
	if (root == NULL)
		return NULL;
	if (root->val == x)
		return root;
	BTNode* tmp = TreeFind(root->left, x);
	if (tmp)
		return tmp;
	tmp = TreeFind(root->right, x);
	if (tmp)
		return tmp;
	return NULL;
}

①：依然是遍历的思路，这里我们选择前序遍历，先将根节点比较了再去左右子树比较；

②：然后最小子递归返回条件也是当root为空时，返回NULL，表示该条路径中没有找到数x；

③：若当前结点的数据等于x，表示找到了，就返回该结点；

④：若没找到，就先去左子树找，若左子树返回值不为NULL，说明找到了，返回左孩子结点；若左子树没找到，则返回NULL，不进如if语句；

⑤：左子树没找到，就开始找右子树，和左子树同样的道理，找到返回右子树结点，没找到返回NULL；

🍁三、LeetCode——检查两棵二叉树是否相等

🌕（一）、题目链接：100. 相同的树 – 力扣（LeetCode）

🌕（二）、解答：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //两个树都为NULL
    if(p==NULL&&q==NULL)
    return true;
    //其中一个为NULL
    if(p==NULL||q==NULL)
    return false;
    //都不为NULL，则比较数据
    if(p->val!=q->val)
    //到这里说明该结点数据相同，则比较左子树，然后比较右子树
    return false;
    return isSameTree(p->left,q->left)&&
            isSameTree(p->right,q->right);
}

①：若两棵树都为NULL，则代表此结点的数据相同，返回ture；

②：若其中一个为NULL，另一个不为NULL，则两结点数据不同，返回false；

③：若两个都不为NULL，则比较数据，若数据不相同，则两结点数据不同，返回false；

④：若不为上述三种情况，则说明该结点相同，则比较其左子树，然后比较其右子树；

🍁四、LeetCode——二叉树的前序遍历（与上一篇文章不太一样）

🌕（一）、题目链接：144. 二叉树的前序遍历 – 力扣（LeetCode）

🌕（二）、解答：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

 //手动写的计算树的结点个数函数
 int TreeSize(struct TreeNode*root)
 {
     return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
 }

 //手动写的遍历函数
void preorder(struct TreeNode* root,int* a,int* pi)
{
    if(root==NULL)
    return;
    a[(*pi)++]=root->val;
    preorder(root->left,a,pi);
    preorder(root->right,a,pi);
}

//LeetCode给定函数
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int n=TreeSize(root);
    int* a=(int*)malloc(sizeof(int)*n);

    int j=0;
    preorder(root,a,&j);

    *returnSize=n;
    return a;
}

二叉树的前序遍历，我们在上一篇文章已经讲解了，是一个很简单的过程；但这道题不一样，不一样在这里存在一些OJ题的技巧解释；

①：这道题的意思是叫我们把树的前序遍历的结果，存放在一个数组中，最后在返回该数组的起始地址；

②：我们看到LeetCode给定的函数接口中有两个形参，一个是待操作的树，另一个是整形指针，但我们看整形指针字面意思，应该知道我们应该返回一个数组的个数，那为什么会是一个整形指针呢？因为在接口外部传的是该变量地址，我们要在函数接口中根据待测树的结点数，去解引用整形指针改变函数外部的数组个数，所以使用了传址调用。

③：所以我们手动写了一个函数，计算出待测树的结点个数，然后解引用returnSize，将树的结点数赋值给它。

④：又因为我们要用到递归的思路，所以又手动写了一个函数，进行前序遍历及其将数据存到数组中的操作，又因为数组需要用到下标，为了下标j能在任意递归栈帧中改变，所以我们使用了传址调用，将下标j的地址传进去，这样，我们每赋值一次，就解引用后加1，这样下标就能动态改变；

⑤：接着便是前序遍历的算法，只是将打印换成了赋值给数组这一操作；

本次知识到此结束，希望对你有所帮助！