帮助做APP的网站公司,主流搭建网站,wordpress fly主题,wordpress上传图片会缩小目录 一、基本二叉树
1.1结构
1.2前序遍历#xff08;注意三种遍历中Visit所在的位置#xff09;
1.2中序遍历
1.3后序遍历
二、真题实战
2.1KY11 二叉树遍历#xff08;清华大学复试上机题#xff09;【较难】
2.2KY212 二叉树遍历二叉树遍历#xff08;华中科技大…目录 一、基本二叉树
1.1结构
1.2前序遍历注意三种遍历中Visit所在的位置
1.2中序遍历
1.3后序遍历
二、真题实战
2.1KY11 二叉树遍历清华大学复试上机题【较难】
2.2KY212 二叉树遍历二叉树遍历华中科技大学复试题【中等】 一、基本二叉树
1.1结构
首先定义二叉树的结构
struct TreeNode{//数据类型 变量;char data;TreeNode *leftChild; //左子树 TreeNode *rightChild; //右子树 TreeNode(char x) : data(x), leftChild(NULL), rightChild(NULL) {}
};关于建树看玩遍历后看题解。
1.2前序遍历注意三种遍历中Visit所在的位置 Visit是访问格式比如print输出不一定是函数 访问根节点-左子树-右子树遍历过程可以想成逆时针。如图所示。 void PreOrder(TreeNode* root){if(rootNULL){return;}Visit(root-data);PreOrder(root-leftChild);PreOrder(root-rightChild);return ;
}1.2中序遍历
左-中-右 void InOrder(TreeNode* root){if(rootNULL){return ;}InOrder(root-leftChild);Visit(root-data);InOrder(root-rightChild);return ;
}
1.3后序遍历
左-右-根 void PostOrder(TreeNode* root){if(rootNULL){return ;}PostOrder(root-leftChild);PostOrder(root-rightChild);Visit(root-data);return ;
}1.4层次遍历
暂时没有遇到先不更需要用到 队列辅助更新。
二、真题实战
2.1KY11 二叉树遍历清华大学复试上机题【较难】
二叉树遍历_牛客题霸_牛客网
描述
编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。
输入描述
输入包括1行字符串长度不超过100。
输出描述
可能有多组测试数据对于每组数据 输出将输入字符串建立二叉树后中序遍历的序列每个字符后面都有一个空格。 每个输出结果占一行。
示例1 输入 abc##de#g##f###复制输出 c b e g d f a 总结注意建立树的顺序和所需变量root-leftChild或者root-rightChild的赋值。异常情况返回NULL以及最后返回root。整体就是确定结构-建树方法-遍历方法-主程序。
#include bits/stdc.h
using namespace std;
struct TreeNode{//数据类型 变量;char data;TreeNode *leftChild; //左子树 TreeNode *rightChild; //右子树 TreeNode(char x) : data(x), leftChild(NULL), rightChild(NULL) {}
};//建树 先序遍历 中-左-右
TreeNode* PreBuild(int index,string s ){char cs[index];index;if(c#){return NULL;}TreeNode* rootnew TreeNode(c);root-leftChildPreBuild(index,s);root-rightChildPreBuild(index,s);return root;
}void InOrder(TreeNode* root){if(rootNULL){return ;}InOrder(root-leftChild);coutroot-data ;InOrder(root-rightChild);return ;
}int main() {string s;while(cins){int index0;TreeNode* rootPreBuild(index,s);InOrder(root);}return 0;
}2.2KY212 二叉树遍历二叉树遍历华中科技大学复试题【中等】
二叉树遍历_牛客题霸_牛客网
描述
二叉树的前序、中序、后序遍历的定义 前序遍历对任一子树先访问根然后遍历其左子树最后遍历其右子树 中序遍历对任一子树先遍历其左子树然后访问根最后遍历其右子树 后序遍历对任一子树先遍历其左子树然后遍历其右子树最后访问根。
给定一棵二叉树的前序遍历和中序遍历求其后序遍历提示给定前序遍历与中序遍历能够唯一确定后序遍历。
输入描述
两个字符串其长度n均小于等于26。 第一行为前序遍历第二行为中序遍历。 二叉树中的结点名称以大写字母表示ABC....最多26个结点。
输出描述
输入样例可能有多组对于每组测试样例 输出一行为后序遍历的字符串。
示例1 输入 ABC
BAC
FDXEAG
XDEFAG复制输出 BCA
XEDGAF 总结我感觉这个建树比上一个难许多整道题就是考察建树。
根据先序遍历的性质第一个节点就是根节点根据这个入手。做题时一定要结合数据结构的特性
再根据中序遍历的性质找到根节点索引位置的话左边的就是左子树右边的就是右子树。再递归处理。
这个根节点索引位置前序遍历字符串和中序遍历字符串都能用都是分块节点。
递归停止的标志就是先序遍历字符串长度为0返回NULL空节点。 函数解释sub str.substr(7, 5); // 从索引为7的位置提取长度为5的子字符串 sub str.substr(7);代表从索引7开始到末尾的所有字符串 。 #includebits/stdc.h
using namespace std;
struct TreeNode{char data;TreeNode* leftChild;TreeNode* rightChild;TreeNode(char c):data(c),leftChild(NULL),rightChild(NULL){}
};
TreeNode* Build(string s1,string s2){if(s1.size()0){return NULL;}char cs1[0];TreeNode* rootnew TreeNode(c);int indexs2.find(c);root-leftChildBuild(s1.substr(1,index),s2.substr(0,index));root-rightChildBuild(s1.substr(index1),s2.substr(index1));return root;
}void PostOrder(TreeNode* root){if(rootNULL){return;}PostOrder(root-leftChild);PostOrder(root-rightChild);coutroot-data;return ;
}int main()
{string s1,s2,s3,s4;cins1s2s3s4;TreeNode* rootBuild(s1,s2);PostOrder(root);coutendl;TreeNode* root2Build(s3,s4);PostOrder(root2);return 0;
}
