【中等】保研/考研408机试-二叉树相关

目录

一、基本二叉树

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(root==NULL){return;}Visit(root->data);PreOrder(root->leftChild);PreOrder(root->rightChild);return ;
}

1.2中序遍历

左-中-右

void InOrder(TreeNode* root){if(root==NULL){return ;}InOrder(root->leftChild);Visit(root->data);InOrder(root->rightChild);return ;
}

1.3后序遍历

左-右-根

void PostOrder(TreeNode* root){if(root==NULL){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 c=s[index];index++;if(c=='#'){return NULL;}TreeNode* root=new TreeNode(c);root->leftChild=PreBuild(index,s);root->rightChild=PreBuild(index,s);return root;
}void InOrder(TreeNode* root){if(root==NULL){return ;}InOrder(root->leftChild);cout<<root->data<<" ";InOrder(root->rightChild);return ;
}int main() {string s;while(cin>>s){int index=0;TreeNode* root=PreBuild(index,s);InOrder(root);}return 0;
}

2.2KY212 二叉树遍历二叉树遍历（华中科技大学复试题）【中等】

二叉树遍历_牛客题霸_牛客网

描述

二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树； 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

输入描述：

两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出描述：

输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。

示例1

输入：

ABC
BAC
FDXEAG
XDEFAG

复制输出：

BCA
XEDGAF

总结：我感觉这个建树比上一个难许多，整道题就是考察建树。

根据先序遍历的性质，第一个节点就是根节点，根据这个入手。（做题时一定要结合数据结构的特性） 

再根据中序遍历的性质，找到根节点索引位置的话，左边的就是左子树，右边的就是右子树。再递归处理。

这个根节点索引位置，前序遍历字符串和中序遍历字符串都能用，都是分块节点。

递归停止的标志就是先序遍历字符串长度为0，返回NULL（空节点）。

函数解释：sub = str.substr(7, 5); // 从索引为7的位置提取长度为5的子字符串

sub = str.substr(7);代表从索引7开始到末尾的所有字符串 。

#include<bits/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 c=s1[0];TreeNode* root=new TreeNode(c);int index=s2.find(c);root->leftChild=Build(s1.substr(1,index),s2.substr(0,index));root->rightChild=Build(s1.substr(index+1),s2.substr(index+1));return root; 
}void PostOrder(TreeNode* root){if(root==NULL){return;}PostOrder(root->leftChild);PostOrder(root->rightChild);cout<<root->data;return ;
}int main() 
{string s1,s2,s3,s4;cin>>s1>>s2>>s3>>s4;TreeNode* root=Build(s1,s2);PostOrder(root);cout<<endl;TreeNode* root2=Build(s3,s4);PostOrder(root2);return 0;
}