链式二叉树的基本操作，前序、中序以及后序遍历（递归实现，非递归实现）【有图解】
结点设置
既然是链式二叉树，那必须得有自己的结点类型，以下是链式二叉树结点类型的定义，为了避免过多重复的代码，下面的问题都统一使用该结点类型。
typedef char BTDataType;//结点中存储的元素类型（以char为例）
typedef struct BTNode
{
BTDataType data;//结点中存储的元素类型
struct BTNode* left;//左指针域（指向左孩子）
struct BTNode* right;//右指针域（指向右孩子）
}BTNode;
二叉树的遍历
前序、中序以及后序遍历 递归实现
所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。
遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
- 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
- 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
// 二叉树前序遍历
void PreOrder(BTNode* root)
{
if (root == nullptr)
{
return;
}
//根->左子树->右子树
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
// 二叉树中序遍历
void InOrder(BTNode* root)
{
if (root == nullptr)
{
return;
}
//根->左子树->右子树
PreOrder(root->left);
printf("%c ", root->data);
PreOrder(root->right);
}
// 二叉树后序遍历
void PostOrder(BTNode* root)
{
if (root == nullptr)
{
return;
}
//根->左子树->右子树
PreOrder(root->left);
PreOrder(root->right);
printf("%c ", root->data);
}
前序遍历递归图解
前序、中序以及后序遍历 非递归实现
思路：
- 根节点入栈.
- 栈顶元素入存入vector,根节点出栈.
- 右孩子入栈
- 左孩子入栈
因为我们要求:
先访问左孩子,再访问右孩子.
而栈是后进先出的结构,所以:
右孩子先入栈,左孩子后入栈.
步骤示例图:
代码：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> s;
if(root == nullptr)
return {};
s.push(root);//根节点先入栈
while(!s.empty())//当栈为空时,结束
{
TreeNode* ret = s.top();
v.push_back(ret->val);//出栈前,先将栈顶元素存入vector
s.pop();//栈顶元素出栈
//栈顶元素的右左子树入栈
if(ret->right)
s.push(ret->right);
if(ret->left)
s.push(ret->left);
}
return v;
}
};
思路:
有了前面的前序遍历的思想,对于中序遍历,需要注意的是存入容器(这里是vector)的时机.
左路节点依次入栈.(与前序对比:此时入栈并没有入容器.)
栈顶元素入容器,栈顶元素出栈,栈顶元素的右子树子问题解决.
代码：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s1;
vector<int> v1;
TreeNode* cur=root;
while(cur||!s1.empty()){
//沿着左子树一直入节点
while(cur){
s1.push(cur);
cur=cur->left;
}
TreeNode* top = s1.top();
if(top==nullptr)break;
v1.push_back(top->val);
//栈顶元素出栈
s1.pop();
//右子树 以子问题的方式解决
if(top->right)
cur=top->right;
}
return v1;
}
};
思路 ：
对于后序遍历,同样注意存入容器的时机,应当是左子树和右子树都访问完毕,才能够访问根节点.
注意点:
(1)访问结点之前,需要先判断右子树是否已经被访问.
如何判断根节点的右子树已经有没有访问?
答案: 上一个存入的结点是自己右子树,则右子树已经被访问.
上一个结点不是自己的右子树,则右子树未被访问.
代码：
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> v;
TreeNode* prev = nullptr;
TreeNode* cur = root;
while(cur || !s.empty())
{
while(cur)
{
s.push(cur);
cur = cur->left;
}
TreeNode* top = s.top();
//top的结点右为空 or 上一个访问的结点是他的右孩子
//说明不用访问 或者 已经访问过了
if(top->right == nullptr || top->right == prev)
{
s.pop();
prev = top;
v.push_back(top->val);
}
else
{
cur = top->right;
}
}
return v;
}
};
层序遍历
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。
设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
思路（借助一个队列）：
1.先把根入队列，然后开始从队头出数据。
2.出队头的数据，把它的左孩子和右孩子依次从队尾入队列（NULL不入队列）。
3.重复进行步骤2，直到队列为空为止。
// 层序遍历
void LevelOrder(BTNode* root)
{
std::queue<BTNode*> q;
if (root != nullptr)
q.push(root);
while (q.empty())
{
BTNode* front = q.front();
q.pop();
printf("%c ", front->data);//打印出队的元素
if (front->left)
{
q.push(front->left);
}
if (front->right)
{
q.push(front->right);
}
}
}
结点的个数
求解树的结点总数时，可以将问题拆解成子问题：
1.若为空，则结点个数为0。
2.若不为空，则结点个数 = 左子树结点个数 + 右子树结点个数 + 1（自己）。
代码：
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
return root == nullptr ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
叶子结点的个数
子问题拆解：
1.若为空，则叶子结点个数为0。
2.若结点的左指针和右指针均为空，则叶子结点个数为1。
3.除上述两种情况外，说明该树存在子树，其叶子结点个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数。
代码：
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == nullptr)//空树无叶子结点
return 0;
if (root->left == nullptr && root->right == nullptr)//是叶子结点
return 1;
//叶子结点的个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
第k层结点的个数
思路：
相对于根结点的第k层结点的个数 = 相对于以其左孩子为根的第k-1层结点的个数 + 相对于以其右孩子为根的第k-1层结点的个数。
代码：
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (k < 1 || root == nullptr)//空树或输入k值不合法
return 0;
if (k == 1)//第一层结点个数
return 1;
//相对于父结点的第k层的结点个数 = 相对于两个孩子结点的第k-1层的结点个数之和
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
值为x的结点
子问题：
1.先判断根结点是否是目标结点。
2.再去左子树中寻找。
3.最后去右子树中寻找。
代码：
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == nullptr)
return nullptr;
if (root->data == x)
return root;
BTNode* rleft = BinaryTreeFind(root->left, x);//在左子树中找
if (rleft)
return rleft;
BTNode* rright = BinaryTreeFind(root->right, x);//在右子树中找
if (rright)
return rright;
return nullptr;//根结点和左右子树中均没有找到
}
树的最大深度
子问题：
1.若为空，则深度为0。
2.若不为空，则树的最大深度 = 左右子树中深度较大的值 + 1。
代码：
//树的最大深度
int BinaryTreeMaxDepth(BTNode* root)
{
//树的最大深度 = 左右子树中深度较大的值 + 1
return root == nullptr ? 0 : (std::max(BinaryTreeMaxDepth(root->left) + 1, BinaryTreeMaxDepth(root->right) + 1));
}
二叉树的销毁
二叉树的销毁，与其他数据结构的销毁类似，都是一边遍历一边销毁。但是二叉树需要注意销毁结点的顺序，遍历时我们应该选用后序遍历，也就是说，销毁顺序应该为：左子树->右子树->根。
我们必须先将左右子树销毁，最后再销毁根结点，若先销毁根结点，那么其左右子树就无法找到，也就无法销毁了。
代码：
//二叉树销毁
void BinaryTreeDestroy(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeDestroy(root->left);//销毁左子树
BinaryTreeDestroy(root->right);//销毁右子树
free(root);//释放根结点
}
原文地址：https://blog.csdn.net/weixin_74461263/article/details/144784898
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！