手机网站开发 图库类,济南网站建设公司-远大云.,企业建设网站好吗,wordpress每页显示数量二叉树的遍历
1. 二叉树的前序、中序、后序遍历
前、中、后序遍历又叫深度优先遍历 注#xff1a;严格来说#xff0c;深度优先遍历是先访问当前节点再继续递归访问#xff0c;因此#xff0c;只有前序遍历是严格意义上的深度优先遍历 首先需要知道下面几点#xff1a; …二叉树的遍历
1. 二叉树的前序、中序、后序遍历
前、中、后序遍历又叫深度优先遍历 注严格来说深度优先遍历是先访问当前节点再继续递归访问因此只有前序遍历是严格意义上的深度优先遍历 首先需要知道下面几点
任何一颗二叉树都由根节点、左子树、右子树构成。
如图 分治算法分而治之。大问题分成类似的子问题子问题再分成子问题……直到子问题不能再分割。对树也可以做类似的处理对一棵树不断地分割直到子树为空时分割停止。关于二叉树的许多问题我们都要利用分治思想将一棵完整的树分解成根和左右两棵子树然后再对这两棵子树进行相同的递归处理最后得到结果。如果对递归的过程想的不太清楚建议画递归展开图来辅助理解。 1.1 前序先根遍历 遍历顺序根- 左子树 - 右子树即先访问根再访问左子树最后在访问右子树 如上图中A - B - C - NULL - NULL - D - NULL - NULL - E - NULL - NULL
typedef char BTDataType;
typedef struct BinaryTreeNode
{struct BinaryTreeNode *left; //指向左子树struct BinaryTreeNode *right; //指向右子树BTDataType data;
}BTNode;void PrevOrder(BTNode * root) //前序遍历
{if (!root)return;printf(%d ,root-data); //根PrevOrder(root-left); //左子树PrevOrder(root-right); //右子树return;
}递归顺序图 递归展开图: 1.2 中序中根遍历 遍历顺序左子树 - 根 - 右子树即先访问左子树再访问根最后在访问右子树 如上图中NULL - C - NULL - B - NULL - D - NULL - A - NULL - E - NULL
void InOrder(BTNode* root)
{if (!root)return;InOrder(root-left); //左子树printf(%c , root-data); //根InOrder(root-right); //右子树return;
}递归顺序图 1.3 后序后根遍历 遍历顺序左子树 - 右子树 - 根即先访问左子树再访问左右子树最后在访问根 如上图中NULL - NULL - C - NULL - NULL - D - B - NULL - NULL - E - A
void PostOrder(BTNode* root)
{if (!root){printf(NULL );return;}PostOrder(root-left); //左子树PostOrder(root-right); //右子树printf(%c , root-data); //根
}递归顺序图 2. 二叉树前中后序的非递归遍历
在利用递归来进行二叉树的前中后序遍历时我们通常将一棵二叉树看成三部分根、左子树、右子树。但是对于前中后序的非递归遍历我们需要转变思路应当将一棵二叉树看成两部分左路节点、左路节点的右子树 2.1 前序非递归
前序遍历的顺序是根 - 左子树 - 右子树。
具体到一棵二叉树就是自顶向下将左路节点遍历完再自底向上遍历左路节点的右子树。如图 为了能够在遍历完左路节点后还能得到这个节点从而得到这个节点的右子树我们需要利用栈来对左路节点进行存储。
实现代码
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint ret;stackTreeNode* st;TreeNode* cur root;while (cur || !st.empty()){//遍历左路节点将左路节点的值打印的同时将节点入栈while (cur){ret.push_back(cur-val);st.push(cur);cur cur-left;}TreeNode* tmp st.top();st.pop();//此时cur即为左路节点的右子树//将这棵右子树看成一颗完整的二叉树进行相同的操作cur tmp-right;}return ret;}
};2.2 中序非递归
中序遍历的顺序是左子树 - 根 - 右子树
具体到一棵二叉树即从左路节点的最深处开始先遍历这个节点再遍历这个节点的右子树自底向上。 同样为了能够找到之前的左路节点也需要一个栈来对左路节点进行保存
实现代码
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint ret;stackTreeNode* st;TreeNode* cur root;while (cur || !st.empty()){//遍历左路节点的时候将左路节点入栈//由于左子树先于根因此先不要打印左路节点根的值while (cur){st.push(cur);cur cur-left;}//程序第一次走到这里时tmp就是左路节点的最深处//tmp的左子树为nullptr或已经遍历完tmp的左子树因此打印其根值TreeNode* tmp st.top();st.pop();ret.push_back(tmp-val);//遍历左路节点的右子树cur tmp-right;}return ret;}
};2.3 后序非递归
后序的遍历顺序为左子树 - 右子树 - 根
具体到一棵二叉树即从左路节点的最深处开始先遍历左路节点的右子树再遍历左路节点自底向上。如图 同样也需要一个栈来保存之前的左路节点
此外由于后序遍历的顺序为左子树 - 右子树 - 根需要遍历完根左路节点的左子树和右子树后才能对其值进行打印在这个过程中我们会经过两次根且只能在第二次经过根时才能打印根的值为了确保我们打印根的时机可以利用一个指针prev来记录之前遍历的位置如果prev停留在左路节点的右子树的根节点就说明此时左右子树已经遍历完可以打印根的值
实现代码
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint ret;stackTreeNode* st;TreeNode* cur root;TreeNode* prev nullptr;while (cur || !st.empty()){//将左路节点入栈while (cur){st.push(cur);cur cur-left;}TreeNode* tmp st.top();//如果左路节点的右子树为空或者prev停留在右子树的根//说明根的左子树和右子树都已遍历完//打印根值遍历根同时跟新prev的位置if (tmp-right nullptr || prev tmp-right){ret.push_back(tmp-val);st.pop();prev tmp;}else //否则说明根的右子树没有遍历完遍历右子树cur tmp-right;}return ret;}
};2. 二叉树的层序遍历 层序遍历又叫广度优先遍历。 设二叉树的根节点所在层数为1层序遍历就是从根节点出发首先访问第一层的节点然后从左到右访问第二层上的节点接着访问第三层的节点以此类推自上而下自左往右逐层访问树的结点的过程就是层序遍历。 层序遍历借助队列的先进先出思想来实现。 核心思想上一层带下一层 如图就是对上面那棵树的层序遍历示意图 实现代码
typedef BTNode* QDataType; //队列元素类型
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;
typedef struct Queue //定义存放指向队头队尾指针的结构体
{QueueNode* head; //指向队头QueueNode* tail; //指向队尾
}Queue;//层序遍历
void LevelOrder(BTNode* root)
{Queue *q (Queue *)malloc(sizeof(Queue)); //创建队列QueueInit(q); //初始化队列//如果根节点为空直接退出函数if (!root)return;QueuePush(q, root); //先将根节点入队入队while (!QueueEmpty(q)) //当队列不为空{BTNode* front QueueFront(q); //接收队头元素QueuePop(q); //出队头元素printf(%c , front-data); //访问该节点if (front-left) //如果左子树不为空QueuePush(q, front-left); //左子树入队if (front-right) //如果右子树不为空QueuePush(q, front-right); //右子树入队}printf(\n);QueueDestroy(q); //销毁队列
}3. 二叉树遍历的应用 由二叉树和层序遍历的思想我们可以构造出这棵树 再有前序遍历 根- 左子树 - 右子树 的思想可以知道这棵树的前序序列为A B D H E C F G 这道题是由二叉树的前序序列和中序序列来确定二叉树我们知道中序遍历的思想是 左子树 - 根 - 右子树 根将左子树和右子树分割开来那么我们就可以先用前序序列确定根再用中序序列确定根的左右子树这样就可以将这棵二叉树确定了如图 显然根节点为E 我们同样可以用代码利用一棵二叉树的前序序列和中序序列来将这棵二叉树还原Leetcode - 从前序与中序遍历序列构造二叉树 class Solution {
public://前序序列即为根序列//在中序序列找到根后可以将序列分为左右两部分这两部分分别就是跟的左子树序列和右子树序列TreeNode* _buildTree(vectorint preorder, vectorint inorder, int prei, int inBegin, int inEnd){//区间长度小于1直接返回空if (inBegin inEnd)return nullptr;//前序序列即为根序列TreeNode* root new TreeNode(preorder[prei]);//在中序序列中找到根int pos 0;while (1){if (root-val ! inorder[pos])pos;elsebreak;}//分别前往左子树和右子树进行连接root-left _buildTree(preorder, inorder, prei, inBegin, pos - 1);root-right _buildTree(preorder, inorder, prei, pos 1, inEnd);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i 0;TreeNode* root _buildTree(preorder, inorder, i, 0, inorder.size() - 1);return root;}
};这题和第二题类似同样是先由后序遍历左子树 - 右子树 - 根确定根节点再由中序遍历确定根的左右子树只是用后序遍历确定根节点时要从最后开始。如图 易得前序遍历为a b c d e 我们同样可以用代码利用一棵二叉树的前序序列和中序序列来将这棵二叉树还原Leetcode - 从中序与后序遍历序列构造二叉树 class Solution {
public://思想同前序序列和中序序列确定二叉树类似TreeNode* _buildTree(vectorint inorder, vectorint postorder, int posi, int inBegin, int inEnd){if (inBegin inEnd)return nullptr;TreeNode* root new TreeNode(postorder[posi--]);int pos 0;while (1){if (root-val ! inorder[pos])pos;elsebreak;}root-right _buildTree(inorder, postorder, posi, pos 1, inEnd);root-left _buildTree(inorder, postorder, posi, inBegin, pos - 1);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {int i postorder.size() - 1;TreeNode* root _buildTree(inorder, postorder, i, 0, inorder.size() - 1);return root;}
};总结 由于二叉树的中序遍历可以分割二叉树的左右节点因此 前序序列 中序序列 / 后序序列 中序序列 都可以构建出一棵二叉树而单独序列和 前序序列 后序序列就不行。
