|
代码实现分析 代码步骤分析： 1.判断根节点是不是空，是空就返回NULL 2.不是NULL，就判断该节点的数据是不是要找的数据，是—>（找到了，一层一层返回上去） 3.不是要找的数据，就开始调用左子树（如果左子树一直没找到），从最后递归到的NULL开始返回，返回到调用的地方，然后开始调用最后一层的右子树,如果左子树和右子树都递归完了，还没找到就返回NULL 4.如果一颗二叉树左子树和右子树都有要找的值，只要先找到其中一个，该值就会被一层一层的返回上去，剩下相同的值就不会找找了 代码实现 //二叉树查找值为x的结点BTNode*TreeFind(BTNode*root,BTDataTypex){if(root==NULL)returnNULL;if(root->data==x)returnroot;BTNode*ret1=TreeFind(root->left,x);if(ret1)returnret1;BTNode*ret2=TreeFind(root->right,x);if(ret2)returnret2;returnNULL;} 递归展开图 举例：假设我们这里找5这个节点 注意：我这里把5的位置换了下，让他在左子树就可以被找到（还是画出的左子树的递归图） 过程讲解：1.一直递归调用左边，递归到3的左儿子是NULL，返回到调用NULL的地方，开始调用3的右儿子，发现也是NULL 2.这时返回到调用3的地方，3是被2的左边调用的，返回后，开始递归2的右儿子 3.这时要找的数据x和data相同，if条件符合，执行return，然后就开始返回上去 4.首先返回到2调用右儿子的地方，if语句为真，继续返回，返回到2被1调用的地方 5.还是if条件为真，返回出去了，这时整个递归就结束了  点击加载图片 2.求二叉树层数  点击加载图片 代码思路分析 代码实现分析： 1.先判断根节点是不是为空，为空就返回NULL，就结束了 2.走到这里那根节点就不是空，不是空就开始一直递归树的左边，递归到3的左儿子，左儿子是空，这时if条件判断成立，就返回0，开始递归3的右儿子，右儿子也为NULL，这时左返回的层数和右返回的层数比较，由于左边和右边一样都为0，那就随便返回一个+1 3.节点3的左右儿子都返回完了，这时开始递归调用2的右子树，右子树为空，和3返回的作比较，3返回的值大，那就返回层数2 4.后面和3的逻辑差不多，最后就是比较节点2返回的层数和4返回的层数谁大，然会就返回给1，节点1再+1，然会就返回出去，结束整个递归 通过上面的分析可以看出，这个是二叉树遍历顺序中的后序遍历 代码实现 intTreeDepth(BTNode*root){if(root==NULL){return0;}intleftDepth=TreeDepth(root->left);intrightDepth=TreeDepth(root->right);returnleftDepth>rightDepth?leftDepth+1:rightDepth+1;} 3.二叉树的销毁  点击加载图片 代码思路分析 前中后序遍历，哪个更适合这里的二叉树销毁呢？ 如果采用前序遍历去销毁，一进来就销毁根节点，节点中存着的左孩子和右孩子的指针，如果我们一进来就销毁根节点，这时的左右孩子指针就也被销毁了，不能遍历下去了 中序遍历也一样 后序遍历访问根的顺序——左子树—>右子树—>根，所以我们使用后序遍历可以轻松的避免上面的问题发生 代码实现 通过上面可以知道是后续遍历，代码步骤分析如下 1.还是一开始就递归调用左边，递归到NULL就返回，开始递归调用右边，右边到NULL，然后就释放节点，这时就回到2，先不销毁2，先递归2的右边，是NULL，然后就销毁节点2 2.节点2销毁后，就返回1的右边，开始递归调用1的右孩子》》》（原理和左边相同） voidTreeDestroy(BTNode*root){if(root==NULL){return;}TreeDestroy(root->left);TreeDestroy(root->right);free(root);} 运行结果 注意点：一般递归不好调试，我们可以借助打印，来理解 由于我们使用的是后序遍历，所以我们这里打印的销毁节点的顺序，就是后序遍历的顺序  点击加载图片 4.二叉树的一些OJ题目 下面是一些Leetcode上的一些二叉树练习题，价值还是蛮高的，可以点击OJ链接跳转去做题 后面小余也会出这些题目的题解和做题心得，大家可以关注下哦！ 1.单值二叉树OJ链接跳转 2.检查两颗树是否相同OJ链接跳转 3.对称二叉树OJ链接跳转 4.二叉树的前序遍历OJ链接跳转 5.二叉树中序遍历OJ链接跳转 6.二叉树的后序遍历OJ链接跳转 7.另一颗树的子树OJ链接跳转 如果觉得文章不错，期待你的一键三连哦，你个鼓励是我创作的动力之源，让我们一起加油，顶峰相见！！！ |
|
|
