清华机试oj——二叉树遍历

傷城~ 2022-05-23 00:49 237阅读 0赞

## 题目描述 ##

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串：ABC\#\#DE\#G\#\#F\#\#\#其中“\#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

##### **输入描述:** #####

输入包括1行字符串，长度不超过100。

##### **输出描述:** #####

可能有多组测试数据，对于每组数据，
    输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
    每个输出结果占一行。

示例1

## 输入 ##

abc##de#g##f###

## 输出 ##

c b e g d f a

## 解题思路 ##

首先建立一个结构体用来存储结点，其中包括结点的值（字符型）、左子树（指针）、右子树（指针），然后按照先序遍历顺序建树（此时若为空就是‘\#’），最后中序遍历输出结果。

## 代码实现 ##

#include<bits/stdc++.h>
    using namespace std;
    
    string str;
    int i;
    
    struct TreeNode{
    	char val;//结点的值（字符） 
    	struct TreeNode *lchild, *rchild;//以指针方式存储 
    	TreeNode(char c):val(c), lchild(NULL), rchild(NULL){};
    };
    
    TreeNode* createTree(){	//按照前序建树 
    	char c = str[i++];
    	if(c == '#') return NULL;
    	TreeNode *root = new TreeNode(c);
    	root->lchild = createTree();
    	root->rchild = createTree();
    	return root;
    }
    
    void inOrderTraversal(TreeNode* root){	//中序遍历 
    	if(!root) return;
    	inOrderTraversal(root->lchild);	//左子树 
    	cout << root->val << " ";		//根节点 
    	inOrderTraversal(root->rchild);	//右子树 
    }
    
    int main(){
    	while(cin >> str){
    		i = 0;
    		TreeNode *root = createTree();	//建树 
    		inOrderTraversal(root);			//中序遍历 
    		cout << endl;
    	}
    	return 0;
    }

关于指针和二叉树的应用一直是我的弱项，以后还需要多加总结和运用，这个代码较符合模板形式，很有借鉴意义。

继续加油吧(\#^.^\#)