二叉树的遍历及相关衍生
- 前言
- 二叉树的遍历
- 建树
- 二叉树的遍历
- 遍历的分类
- 代码部分
- 遍历根的应用
- 打印树中的每个数据
- 代码部分
- 遍历计算树节点个数
- 代码部分
- 计算二叉树的深度
- 思路
- 代码部分
- 第k层个数
- 结束
前言
如标题所示，在这里我们要研究的是二叉树的遍历。
为什么不讲二叉树的增删查改？
在实际使用过程中，二叉树的增删查改没有多大作用，二叉树是作为一种数据结构，不是用来存储数据，更多的是用来进行搜索
赫赫有名的红黑树和B树，都是其的限制优化的产物之一。
但是身为小白的博主现在只能先从最基本的遍历开始玩起。
博主刚学C++一点，为了练习和熟悉，所以用的是C++，但是也没多熟练，还是有C的老习惯，请各位多多海涵
二叉树的遍历
建树
我们想要学习对树的遍历，首先就要有一颗树。
所以我们先要进行一次快速的建树
我们要建立这样一颗树
可以看出我们在设计类的变量时，需要设置三个
1：存储数据的int
2：存放右子节点的指针
3：存放左子节点的指针
class tree
{
public:
tree* inittree(int x, tree* left, tree* right)
{
tree* ptr = (tree*)malloc(sizeof(tree));
assert(ptr);
ptr->_data = x;
ptr->_left = left;
ptr->_right = right;
return ptr;
}
private:
int _data;
tree* _left;
tree* _right;
};
int main()
{
tree t1;
tree* ptr3=t1.inittree(3, nullptr, nullptr);
tree* ptr2=t1.inittree(2, ptr3, nullptr);
tree* ptr6 = t1.inittree(6, nullptr, nullptr);
tree* ptr5 = t1.inittree(5, nullptr, nullptr);
tree* ptr4 = t1.inittree(4, ptr5, ptr6);
tree* ptr1 = t1.inittree(1, ptr2, ptr4);
}
没错，建树就是这么简单直接，因为我们主要来学习他的遍历，所以建树这些繁琐的事情快速解决就好了。
二叉树的遍历
看名字，所谓遍历，就是将二叉树中的数据全部访问一遍
如果我们要实现这颗二叉树的遍历，想必大家都多少听过，二叉树和递归算法脱不了一点关系。
虽然有些人听到递归就有点小怕，但是如果把思路理解了以后，递归可比迭代快太多了。
当我们进行遍历的时候，有这样三种操作
1：访问根，就是遍历的历，对根存储的数据进行访问。
2：走向左子树，
3：走向右子树
设计的都是先访问左子树，再访问右子树
这应该是约定俗成的把，虽然先右到左也没什么区别，但是从左往右还是看着赏心悦目一点。
所以纠结的只有根的访问顺序，这样就牵扯到遍历的差别了。
遍历的分类
前根遍历
顾名思义，就是先根后左右
先根后左右
这里我们先将
1：访问根
2：访问左子树
3：访问右子树
这样设定好
因为递归是对函数的重复调用，作用对象是每一个节点，所以到了左子树的节点后，要对子节点进行同样与根节点的操作
即先访问节点数据，在进行左子树和右子树的访问。
这里为了方便看清，就在第一个第二个第三个节点加了前缀，1.1就是第一个节点访问根。
这里当第三个节点访问左右子树为空后，直接进行返回。
剩下两个遍历类型为
中根遍历
即先访问左子树，访问根，再访问右子树
后根遍历
即先访问左右子树，再访问根。
就不多讲了。
代码部分
void Traversaltree(tree* root)
{
if (root == nullptr)
{
cout << " NULL";
return;
}
//访问根的部分按照遍历存放
//访问根的代码按照具体情况而定
//访问根放这-前根
printtree(root->_left);
//访问根放这-中根
printtree(root->_right);
//访问根放这-后根
}
遍历根的应用
打印树中的每个数据
由于我们这个二叉树不是完全二叉树这种特殊树，所以用数组打印时，就会导致残缺不堪
就比如打印这颗树
代码部分
void printtree(tree* root)
{
if (root == nullptr)
{
cout << " NULL";
return;
}
//前根遍历打印
cout << " " << root->_data;
printtree(root->_left);
printtree(root->_right);
}
遍历计算树节点个数
代码部分
int sizetree(tree* root)
{
if (root == nullptr)
return 0;
return sizetree(root->_left)
+ sizetree(root->_right) + 1;
}
按照代码画图
先是通过sizetree(root->_left)，从根节点不断访问左子树，然后节点继续访问它的左子树,直到节点的左子树为空。
当访问到3节点时，在进行左子树为NULL后返回0
随后执行sizetree(root->_right)，对3节点的右子树进行访问，为空，返0。
执行return sizetree(root->_left) + sizetree(root->_right) + 1;
返回 {（左子树的返回）0+（右子树的返回）0 + 1=1}
这个时候重新返回了2节点，
对于二节点，收到了左子树的返回1，右子树为空，返回0
返回给1节点的访问左子树的返回值为
（2节点访问左子树返回值） 1+（2节点访问左子树返回值） 0 +1=2
解释到这，就可以推测出整个递归运行的逻辑了。
计算二叉树的深度
故名思义，就是计算二叉树的深度。
为了更能体现作用，所以将之前的树重新接了一下
思路
这里我们采用直接思考解决方法，直接写代码
不通过想象它的一次一次递归的执行方式去写代码
这样更加快速，当然等会还是会解释递归的执行思路的。
这里我们先不看整个二叉树，我们先来看，对于单一的一个子节点来说
当它接收到来自左边和右边的深度后
将右边和左边的深度进行比较
如果左边较大，则返回左边深度+1值
如果右边较大，则返回右边深度+1值
为什么要+1？
因为返回深度的话还要把自己的深度+1
这样我们就可以试着写出一个代码了
if (root == nullptr)
return 0;
return heighttree(root->_left) >
heighttree(root->_right)
?
heighttree(root->_left) + 1
:
heighttree(root->_right) + 1;
这样运行一下，发现还真可以计算，但是如果你深度进行观察这个代码，就会发现这个写法太挫了
当我们进行比较后，不停进行右子树和左子树访问后
在进行三目操作符执行后，居然还要进行左子树和右子树的访问，这样时间复杂度直接从On变到了On^2
其实要解决这个问题也很简单，加个计数的就好，接下来的是最优的代码。
代码部分
int heighttree(tree* root)
{
if (root == nullptr)
return 0;
int left=heighttree(root->_left);
int right=heighttree(root->_right);
return left > right ? left + 1 : right + 1;
}
首先不断执行int left=heighttree(root->_left);
不停访问左子树，到节点3时，左子树为空
赋值int left=0，之后执行int right=heighttree(root->_right);
访问到6节点，再执行6的左子树访问，到5节点
5节点左右为空，left right皆为0
进行三目操作符比较后，执行return right+1
此时回到6节点
6节点的左子树访问返回，进行赋值int left=1
右子树为空，所以int right=0
进行三目操作符比较后，执行return left+1
返回到 3节点
得到int right=2
与left=0进行比较，返回right+1
…………
解释了两个三个节点操作过程就可以看出整个的递归逻辑了。
第k层个数
顾名思义，给定一个k，求第k层有几个节点
这里直接上代码了，因为难度和前面大差不差
//第k层个数
int treeklevel(tree* root,int k)
{
if (root == nullptr)
return 0;
if (k == 1)
return 1;
return treeklevel(root->_left,k-1)
+ treeklevel(root->_right,k-1);
}
结束
本人画图和解释的精力和能力有限，可能讲的也不是很清楚，正好又碰上递归这个难题，所以请各位多多海涵
