兰州市城乡建设局网站官网,佛山移动网站设计,海南城乡和住房建设厅网站,网站制作出租文章目录前言一、求二叉树节点个数二、求树的叶子结点个数三、求树的高度四、二叉树查找值为x的结点总结前言
笔者整理出了一些关于萌新在入门二叉树时容易犯的一些错误#xff0c;你也来试试自己会不会掉到这些坑里把~ 一、求二叉树节点个数
错误示例#xff1a;
int Tre…
文章目录前言一、求二叉树节点个数二、求树的叶子结点个数三、求树的高度四、二叉树查找值为x的结点总结前言
笔者整理出了一些关于萌新在入门二叉树时容易犯的一些错误你也来试试自己会不会掉到这些坑里把~ 一、求二叉树节点个数
错误示例
int TreeSize(BTNode* root)
{if(root NULL)return ;int size 0;size;TreeSize(root-left);TreeSize(root-right);return Size;
}这里的错误是每当递归一次时其实是在函数栈帧中另外开辟了一个变量size每次size都是在新开辟的变量size上。并没有影响到最开始的变量size。
正确示例
int TreeSize(BTNode* root)
{if(root NULL)return 0;static int size 0;size;TreeSize(root-left);TreeSize(root-right);return size;
}在这个示例中size将在静态区开辟并且只会初始化一次不用担心每次递归时会将size重新初始化为0。这样size每次都可以正确的1 另外的方法就是创建一个全局变量并将整型变量的地址传入函数通过变量的地址改变变量的大小。但是这样需要注意的是需要每次要计数的时候手动将全局变量置为0。 二、求树的叶子结点个数
错误示例
int TreeLeafSize(BTNode* root)
{if(root-left NULLroot-right NULL){return 1;}return TreeLeafSize(root-left)TreeLeafSize(root-right);
}那么这里错在哪呢 其实这里错在缺少一个前置判断
if(root NULL)
{return 0;
}如果没有这个判断条件的话就会出现访问空指针的情况。
三、求树的高度
错误示例
int TreeHeight(BTNode* root)if(root NULL){return 0;}return TreeHeight(root-left)TreeHeight(root-right)?TreeHeight(root-left)1 :TreeHeight(root-right)1;这段代码逻辑上没有错但是其中有一个非常大的诟病。当函数在递归时会反复调用TreeHeight。因为之前的调用没有将结果记下来就导致每当需要上一次函数调用的结果时又再次去调用函数。 改进
int TreeHeight(BTNode* root)
{if(root NULL){return 0;}int leftHeight TreeHeight(root-left);int rightHeight TreeHeigt(root-right);return leftHeightrightHeight?leftHeight1:rightHeight1
}四、二叉树查找值为x的结点
错误示例
BTNode* TreeFind(BTNode* root,BTDataType x)
{if(root NULL)return NULL;if(root-data x){return root;}TreeFind(root-left,x);TreeFind(root-right,x);
}这段代码逻辑看起来非常的自洽但事实上逻辑上并不自洽。 首先要问自己一个问题最下面的两次TreeFind的目的是什么 事实上最下面两次TreeFind没有任何作用因为你没有用到TreeFind的结果。 正确代码
BTNode* TreeFind(BTNode* root,BtDataType x)
{if(root NULL){return NULL;}if(root-data x){return root;}BTNode* ret1 TreeFind(root-left,x);if(ret1){return ret1;}BTNode* ret2 TreeFind(root-left,x);if(ret2){return ret2;}}总结 以上就是笔者对二叉树递归里的一些易错点的记录。代码纯手打可能存在漏洞、瑕疵。如发现欢迎指正!
