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

目录

一、二叉树的销毁

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

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

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

（二）、解答：

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

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

（二）、解答：

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

一、二叉树的销毁

//销毁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) {//两个树都为NULLif(p==NULL&&q==NULL)return true;//其中一个为NULLif(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" />传址调用。
③：所以我们手动写了一个函数，计算出待测树的结点个数，然后解引用returnSize，将树的结点数赋值给它。
④：又因为我们要用到递归的思路，所以又手动写了一个函数，进行前序遍历及其将数据存到数组中的操作，又因为数组需要用到下标，为了下标j能在任意递归栈帧中改变，所以我们使用了传址调用，将下标j的地址传进去，这样，我们每赋值一次，就解引用后加1，这样下标就能动态改变；
⑤：接着便是前序遍历的算法，只是将打印换成了赋值给数组这一操作；

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