首页 > 试题广场 >

二叉树遍历

[编程题]二叉树遍历
  • 热度指数：60581 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

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


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

输入

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

输出

c b e g d f a
算法知识视频讲解
添加回答
sSTtaArR头像 sSTtaArR
中序建树其实就是个深搜的过程，然后递归中序遍历。 
#include<bits/stdc++.h>

using namespace std;

struct Node
{
    int v;
    struct Node* lchild,* rchild;
};

Node* Create()
{
    char x; cin >> x;
    if(x == '#') return nullptr;
    Node* root = new Node;
    root->v = x;
    root->lchild = Create();
    root->rchild = Create();
    return root;
}

void MidOrder(Node* root)
{
    if(root == nullptr) return ;
    MidOrder(root->lchild);
    cout << (char)root->v << " ";
    MidOrder(root->rchild);
}

int main()
{
    ios::sync_with_stdio(false); 
    MidOrder(Create());
    return 0;
}


发表于 2021-01-18 13:14:59 回复(0)
rayZero头像 rayZero 
#include <iostream>
#include <string>
#include <memory>
using namespace std;
string tmp;
int i;
class TreeNode
{
    public:
    char val;
    TreeNode *lchild,*rchild;
    TreeNode(char c):val(c), lchild(NULL), rchild(NULL){}
};
TreeNode *createTree()
{
    char c=tmp[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);
}
void deleteTree(TreeNode *root)
{
    if(!root) return;
    deleteTree(root->lchild);
    deleteTree(root->rchild);
    delete root;
}
int main()
{
    while(cin >> tmp)
    {
        i=0;
        TreeNode *root=createTree();
        inOrderTraversal(root);
        cout << endl;
        deleteTree(root);
    }
    return 0;
}
发表于 2019-04-25 21:52:52 回复(0)
C/C++
林東宇头像 林東宇 
//考查二叉树的递归遍历，在一次遍历的过程中依次得到先序、中序、后序遍历序列
#include 
char pre[110];
int pt=0;
void Create()
{
    int pos = pt++;
    if(pre[pos]=='#')
        return;
    Create();
    printf("%c ", pre[pos]);
    Create();
}
int main()
{
    while(~scanf("%s", pre))
    {
        pt = 0;
        Create();
        printf("\n");
    }
    return 0;
}

发表于 2019-03-27 19:23:16 回复(0)
C/C++
算法小屁孩头像 算法小屁孩 
#include<bits/stdc++.h>
typedef struct btree{
    char data;
    struct btree *lchild,*rchild;
}node,*tree;//二叉树
void ctree(tree *t){
    char c;
    scanf("%c",&c);
    if(c=='#')
        *t=NULL;
    else{
        *t=(tree)malloc(sizeof(node));
        (*t)->data=c;
        ctree(&(*t)->lchild);
        ctree(&(*t)->rchild);
    }
}//先序遍历建树
void inorder(tree t){
    if(t){
        inorder(t->lchild);
        printf("%c ",t->data);
        inorder(t->rchild);
    }
    return;
}//中序遍历输出
void del(tree t){
    if(t){
        del(t->lchild);
        del(t->rchild);
        free(t);
    }
}//释放节点内存
int main(){
    tree t;
    t=(tree)malloc(sizeof(node));
    ctree(&t);
    inorder(t);
    del(t);
}
编辑于 2019-03-12 13:54:03 回复(0)
Java
成程晨头像 成程晨 
import java.util.*;
public class Main{
    private static List<Character> l = new ArrayList<>();
    public static int index = 1;
    private static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            char[] a = in.nextLine().toCharArray();
            TreeNode root = new TreeNode(a[0]);
            generateTree(a,root);
            inOrder(root);
            for(int i = 0;i < l.size();i++){
                System.out.print(l.get(i) + " ");
            }
            System.out.println();
        }
    }
    public static void generateTree(char[] a,TreeNode r){
        if(r.val != '#'){
            r.left = new TreeNode(a[index++]);
            generateTree(a,r.left);
            r.right = new TreeNode(a[index++]);
            generateTree(a,r.right);
        }
    }
    public static void inOrder(TreeNode r){
        if(r.val == '#') return;
        inOrder(r.left);
        l.add(r.val);
        inOrder(r.right);
    }
}

发表于 2019-01-13 22:43:16 回复(0)
C/C++
hhh哦头像 hhh哦
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct node
{
    char data;
    struct node *lchild,*rchild;
}node,*pinnode;
int createtree(pinnode &L)//前序建树
{
    L=(pinnode)malloc(sizeof(node));
    cin>>L->data;
    if(L->data!='#')
    {
        createtree(L->lchild);
        createtree(L->rchild);
        return 1;
    }
    else return 1;
}
int previsit(pinnode &L)//中序遍历
{
    if(L->data=='#')return 1;
    else 
    {
        previsit(L->lchild);
        cout<<L->data<<' ';
        previsit(L->rchild);
        return 1;
    }

}
int main()//主函数
{
    pinnode L;
    createtree(L);
    previsit(L);
    return 0;
}
发表于 2018-10-29 14:09:07 回复(0)
C/C++
xFayChen头像 xFayChen 
# include <iostream>
using namespace std;
/**
* 使用静态数组构建树，无内存泄漏问题
*/
struct node {
char val;
int lchild;
int rchild;
node() {
val = '#';
lchild = -1;
rchild = -1;
}
}tree[105];
int loc = 0; // loc 表示当前可被分配的节点
int createTree(char* & s) { // 使用前序遍历建立树
if (isalpha(s[0])) {
int tmp = loc;// 分配节点
loc++; //当前可分配节点是下一个节点
tree[tmp].val = s[0];
tree[tmp].lchild = createTree(++s);
tree[tmp].rchild = createTree(++s);
return tmp;
}
else {
return -1;
}
}
void inOrder(int n) { // 中序遍历
if (tree[n].val=='#') {
return;
}
if (tree[n].lchild != -1)inOrder(tree[n].lchild);
cout << tree[n].val << " ";
if (tree[n].rchild != -1) inOrder(tree[n].rchild);
}

int main() {
char buf[105];
while (cin >> buf) {
loc = 0;
char * tmp = buf;
createTree(tmp);
inOrder(0);
cout << endl;
}
}
编辑于 2018-09-09 11:28:48 回复(0)
ASHBRINGER201806271637325头像 ASHBRINGER201806271637325
我要举报题目描述不清晰。说是用#代替空格，所以我的判断条件都是空格。没过还以为是递归导致栈溢出，想改成非递归版本改到怀疑人生。然后来看了眼大家的代码，心凉了~ 
#include<iostream>
#include<string>
using namespace std;
struct BinaryTreeNode{
    BinaryTreeNode(char c='\0'):key(c){}
    char key;
    BinaryTreeNode *lchild=nullptr,*rchild=nullptr;
    ~BinaryTreeNode(){
        delete lchild;
        delete rchild;
    }
};
std::size_t pos;
BinaryTreeNode *construct(string *ps){
    BinaryTreeNode *root=nullptr;
    if((*ps)[pos]!='#'){
        root=new BinaryTreeNode((*ps)[pos]);
        if((*ps)[++pos]!='#')root->lchild=construct(ps);
        if((*ps)[++pos]!='#')root->rchild=construct(ps);
    }
    return root;
}//根据所传递字符串构建二叉树，并返回一个指向根节点的指针
void inorder_traversal(BinaryTreeNode *rt){
    if(rt->lchild)inorder_traversal(rt->lchild);
    cout<<(rt->key)<<" ";
    if(rt->rchild)inorder_traversal(rt->rchild);
}//中序遍历二叉树

int main(){
    string temp;
    while(getline(cin,temp)){
        pos=0;
        BinaryTreeNode *root=construct(&temp);
        inorder_traversal(root);
        delete root;
    }
    return 0;
}

发表于 2018-07-04 23:23:35 回复(1)
C/C++
光眸头像 光眸 
#include<iostream>
#include<cstdlib>

#include<stack>

using namespace std;

string pre;
int i;

typedef struct tnode{
	char key;
	struct tnode *LChild;
	struct tnode *RChild;
}TNode,*TREE;

void InOrder(TREE root){
	stack<TNode *> S;
	TNode *p = root;
	while(p != NULL || !S.empty()){
		if(p != NULL){
			S.push(p);
			p = p->LChild;
		}
		else{
			p = S.top();
			S.pop();
			printf("%c ",p->key);
			p = p->RChild;
		}
	}
	return;
}

TNode* CrtTree(){
	char c = pre[i++];
	if(c == '#'){
		return NULL;
	}
	TNode *root= (TNode*)malloc(sizeof(TNode));
	root->key = c;
	root->LChild = root->RChild = NULL;
	root->LChild=CrtTree();
	root->RChild=CrtTree();
	return root;
}


TNode* CrtTree2(){
	if(i>=pre.length() || pre[i] == '#'){
		return NULL;
	}
	TNode *root= (TNode*)malloc(sizeof(TNode));
	root->key = pre[i++];
	root->LChild = root->RChild = NULL;
	root->LChild=CrtTree2();
	root->RChild=CrtTree2();
	return root;
} //为什么修改成这样就不行了？ 求大神抱抱

int main(){
	TREE T;
	while(cin>>pre){
		i = 0;
		T = CrtTree2();
		InOrder(T);
		free(T);
		T = NULL;
		cout<<endl;	
	}
}

发表于 2017-08-17 23:06:38 回复(0)
梅老板的粉头像 梅老板的粉 
#include<iostream>
#include<string>
using namespace std;
struct BNode{
	BNode(const char d='#'):data(d), left(nullptr), right(nullptr) {};
	char data;
	BNode* left;
	BNode* right;
};
//构建二叉树
BNode* constructBinaryTree(const string& preOrder, unsigned& index){
	if (preOrder.size() == 0 || index == preOrder.size() || preOrder[index] == '#')//若空串或者index超出范围，则返回空指针
		return nullptr;
	BNode* T = new BNode(preOrder[index++]);
	T->left = constructBinaryTree(preOrder, index);
	T->right = constructBinaryTree(preOrder, ++index);
	return T;
}
//中序遍历
void mediaOrder(BNode* T){
	if (T != nullptr){
		mediaOrder(T->left);
		cout << T->data << " ";
		mediaOrder(T->right);
	}
}
int main(){
	string str;
	while (cin >> str){
		unsigned index = 0;
		BNode* root = constructBinaryTree(str, index);
		mediaOrder(root);
		cout << endl;
	}
	return 0;
}
编辑于 2017-04-25 23:15:59 回复(0)
C
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct TreeNode {
  ElemType data;
  struct TreeNode* left;
  struct TreeNode* right;
} TreeNode, *BT;

// =============== function prototype ==============
void CreateTree(BT* bt);
void InOrderTraversal(BT bt, void (*visit) (TreeNode*));
// =============== function prototype ==============

void output(TreeNode* node) {
  fprintf(stdout, "%c ", (*node).data);
}

int main(const int argc, const char** const argv) {
  BT bt = NULL;  
  CreateTree(&bt);
  InOrderTraversal(bt, output);
  return 0;
}

// 只有深入理解二叉树及扩展二叉树, 二级指针和堆栈内存等知识。才能写出这短小精悍的函式！
void CreateTree(BT* bt) {
  char ch;
  fscanf(stdin, "%c", &ch);
  if (ch == '#') {
    *bt = NULL;
    return;
  }
  *bt = (TreeNode*) malloc(sizeof(TreeNode));
  (*bt)->data = ch;
  CreateTree(&(*(*bt)).left);
  CreateTree(&(*(*bt)).right);
}

void InOrderTraversal(BT bt, void (*visit) (TreeNode*)) {
  if (!bt) return;
  InOrderTraversal(bt->left,  visit);
  output(bt);
  InOrderTraversal(bt->right, visit);
}

发表于 2021-07-25 15:42:49 回复(0)
wcz2023头像 wcz2023 
#include <iostream>
#include <string>
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;
}

发表于 2016-08-06 11:05:05 回复(15)
fangqun头像 fangqun 
//这个实际上就是树的遍历的非递归实现，入栈时访问 = 前序， 出栈时访问 = 中序
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{  string pre;  while(cin >> pre){
        stack<char> s;
        for(auto it : pre){
            if(it != '#')
                s.push(it);
            else{
                if(!s.empty()){
                    cout << s.top() << ' ';
                    s.pop();
                }
            }
        }
        cout << '\n';  }
}

编辑于 2018-08-23 13:44:02 回复(9)
263保洁小妹头像 263保洁小妹 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 101

struct Node{
    Node *lchild;
    Node *rchild;
    char c;
};

Node *CreateNode()//创建新节点，返回结点指针
{
    Node *ret=(Node*)malloc(sizeof(Node));
    ret->lchild=NULL;
    ret->rchild=NULL;
    return ret;
}

void InOrder(Node *T)//中序遍历
{
    if(T->lchild!=NULL) InOrder(T->lchild);
    printf("%c ", T->c);
    if(T->rchild!=NULL) InOrder(T->rchild);
}

void Del(Node *T)//删除树
{
    if(T->lchild!=NULL)//删除左子树
    {
        Del(T->lchild);
        T->lchild=NULL;
    }
    if(T->rchild!=NULL)//删除右子树
    {
        Del(T->rchild);
        T->rchild=NULL;
    }
    free(T);//删除根节点
}

unsigned pos;//标记字符串处理到哪了
char str[N];//读取的字符串

Node *BuildTree()//根据字符串创立二叉树，并返回根节点指针
{
    if(pos>=strlen(str)) return NULL;//字符串处理完了就歇着吧
    if(str[pos]=='#')//创建空树，即返回空指针
    {
        pos++;//准备处理下一个字符
        return NULL;
    }
    Node *p=CreateNode();//创建一个空节点
    p->c=str[pos++];//先序，先获取根节点的字符信息
    p->lchild=BuildTree();//创建左子树
    p->rchild=BuildTree();//创建右子树
    return p;//完事，返回根节点指针
}

int main()
{
    while(gets(str))
    {
        pos=0;//标记字符串处理到哪了
        Node *T=BuildTree();//根据字符串构建整棵树
        InOrder(T);//中序遍历并输出
        printf("\n");
        Del(T);//贴心的删除树，释放内存空间
    }
}

发表于 2018-02-25 14:49:39 回复(9)
Benjaminz头像 Benjaminz
例子的二叉树应该是这样的，一开始自己搞错了遍历顺序。 
#include<iostream>
#include<string>
using namespace std;
string str;
int i;
struct treenode
{
	char val;
	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 inorder(treenode *root)
{
	if(!root)
		return;
	else
	{
		inorder(root->lchild);
		cout<<root->val<<" ";
		inorder(root->rchild);
	}
}
int main()
{
	while(cin>>str)
	{
	i=0;
	treenode *root=createtree();
	inorder(root);
	cout<<endl;
	}
	return 0;
}

发表于 2017-07-15 10:37:57 回复(6)
Java
中南的小菜鸡头像 中南的小菜鸡 
//鄙人之见，一个栈可以做到。将输入转为字符数组，依次push入栈，遇到字符#不push而是pop
//结果恰为中序遍历



import java.util.Scanner;

import java.util.Stack;



public class Main{

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()){

            char[] ch = sc.nextLine().toCharArray();

            Stack<Character> st = new Stack<>();

            st.push(ch[0]);

            for(int i=1;i<ch.length-1;i++){

                if(ch[i] == '#'){

                    System.out.print(st.pop()+" ");

                }else{

                        st.push(ch[i]);

                }

            }

            System.out.println();

        }

    }

}

发表于 2018-08-05 01:17:56 回复(2)
Benson666头像 Benson666 
import java.util.Scanner;
public class Main{
    static int i;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String s = in.next();
            i=0;
            Node root = build(s);
            printTree(root);
            System.out.println();
        }
    }
    
    public static Node build(String s){
        Node root = null;
        if(s.charAt(i)!='#'){
            root = new Node(s.charAt(i));
            i++;
            root.left = build(s);
            root.right = build(s);
        }else
            i++;
        return root;
    }
    public static void printTree(Node root){
        if(root == null)
            return;
        printTree(root.left);
        System.out.printf("%c ",root.value);
        printTree(root.right);
    }
}

class Node{
    Node left;
    Node right;
    char value;
    public Node(char value){
        this.value = value;
    }
}

发表于 2018-02-27 15:23:09 回复(0)
C/C++
_stormpang头像 _stormpang 
#include<iostream>
#include<cstdio>
using namespace std;

struct Node
{
    char ch;
    struct Node* left = NULL;
    struct Node* right = NULL;
};

int i;      // 计数器

// 构造二叉树
void buildTree(Node* &node, string str)
{
    if(i == str.length())
        return ;
    if(str[i] == '#')
    {
        ++i;
        return ;
    }
    node = new Node;
    node->ch = str[i++];
    node->left = node->right = NULL;
    buildTree(node->left, str);
    buildTree(node->right, str);
}

// 中序遍历
void inOrderTraverse(Node* T)
{
    if(T != NULL)
    {
        inOrderTraverse(T->left);
        cout << T->ch << " ";
        inOrderTraverse(T->right);
    }
}

int main()
{
    
    string str;
    Node *r;
    while(cin >> str)
    {
        i = 0;
        buildTree(r, str);
        inOrderTraverse(r);
        cout << endl;
    }

    return 0;
}


发表于 2016-08-07 14:32:16 回复(0)
C++
Edward王头像 Edward王
24机试指南 炉灰老师 
#include <iostream>
#include <string>
using namespace std;

struct TreeNode{
    char data;
    struct TreeNode *left,*right;
};

TreeNode * RecursiveBuildTree(int &i,string str){
    char c = str[i];
    ++i;
    if(c == '#'){
        return NULL;
    }else{
        TreeNode *newNode = new TreeNode;
        newNode->data = c;
        newNode->left = RecursiveBuildTree(i,str);
        newNode->right = RecursiveBuildTree(i,str);
        return newNode;
    }
}

void InOrder(TreeNode *T){
    if(T != NULL){
        InOrder(T->left);
        cout << T->data <<" ";
        InOrder(T->right);
    }
}

int main() {
    string str;
    while(cin >> str){
        int i = 0;
        TreeNode *root = RecursiveBuildTree(i,str);
        InOrder(root);
        cout << endl;
    }
    return 0;
}


发表于 2024-03-04 09:36:49 回复(0)
Java
麻辣绿豆糕头像 麻辣绿豆糕

此题最大的难点就在于如何把题目所给的 abc##de#g##f###转换为对应的二叉树，这个步骤涉及到一种经典算法，没接触过的 coder 理解模板代码即可（模板不唯一，但思想大致相同）

private static int index = 0;
private static Tree createTree(String str){
        if(index >= str.length() || str.charAt(index)=='#') {
            index++;
            return null;
        }
        Tree treeNode = new Tree(str.charAt(index++));
        treeNode.left = createTree(str);
        treeNode.right = createTree(str);
        return treeNode;
    }

tips:
部分 coder 初次接触时可能会有疑问：为什么仅凭前序遍历序列就能确定对应的二叉树呢？其实是因为此类前序序列以 '#' 的形式给出了空结点所在的位置，因此可以唯一确定此树形态，若缺少空结点的信息，则单个遍历序列不能唯一确定一颗二叉树，需以前+中，或中+后，或其他组合才能唯一确定树的形态。

当确定出树的结构后，进行简单的中序遍历即可得出答案。

private static void inorderPrintTree(Tree tree){
        if(tree==null) return;
        inorderPrintTree(tree.left);
        System.out.print(tree.value+" ");
        inorderPrintTree(tree.right);
    }

以下是完整代码

import java.util.*;
public class Main {
    static class Tree{
        Tree left;
        Tree right;
        char value;
        Tree(char value){this.value = value;}
    }
    private static int index = 0;

    private static Tree createTree(String str){
        if(index >= str.length() || str.charAt(index)=='#') {
            index++;
            return null;
        }
        Tree treeNode = new Tree(str.charAt(index++));
        treeNode.left = createTree(str);
        treeNode.right = createTree(str);
        return treeNode;
    }

    private static void inorderPrintTree(Tree tree){
        if(tree==null) return;
        inorderPrintTree(tree.left);
        System.out.print(tree.value+" ");
        inorderPrintTree(tree.right);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String str = in.next();
            Tree root = createTree(str);
            inorderPrintTree(root);
        }
    }
}
发表于 2022-01-18 11:27:02 回复(0)
提交观点

问题信息

搜索 树
难度：
198条回答 26934浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉树遍历

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号