数据结构实验四：二叉树的遍历

清疚 2022-12-23 15:29 181阅读 0赞

实验要求  
1、建立二叉树；  
2、递归和非递归的遍历算法，要求先序和后序采用递归遍历，中序采用非递归遍历；  
3、实验报告格式及图表清晰；  
4、如有雷同，均算抄袭，按零分处理。

#include<iostream>
    #include<queue>
    #include<stack>
    using namespace std;
    
    struct node {
        
    	char data;
    	node* left;
    	node* right;
    };
    
    void prev_iterate(node* r) {
        
    	if (r == NULL)
    		return;
    	cout << r->data << ' ';
    	prev_iterate(r->left);
    	prev_iterate(r->right);
    }
    
    void next_itertor(node* r) {
        
    	if (r == NULL)
    		return;
    	next_itertor(r->left);
    	next_itertor(r->right);
    	cout << r->data << ' ';
    }
    
    void mid_itertor(node* r) {
        
    	stack<node*> sta;
    	node* n = r;
    	while (n || !sta.empty()) {
        
    		while (n) {
        
    			sta.push(n);
    			n = n->left;
    		}
    		if (!sta.empty()) {
        
    			n = sta.top();
    			sta.pop();
    			cout << n->data << ' ';
    			n = n->right;
    		}
    	}
    }
    
    node* Creat_Tree(node* r) {
        
    	char x;
    	cin >> x;
    	if (x == '#') {
        
    		r = NULL;
    	}
    	else {
        
    		r = (node*)malloc(sizeof node);
    		r->data = x;
    		r->left = Creat_Tree(r->left);
    		r->right = Creat_Tree(r->right);
    	}
    	return r;
    }
    
    int main()
    {
        
    	cout << "输入要插入的数据：" << endl;
    	node* root = NULL;
    	root = Creat_Tree(root);
    	cout << "前序遍历：" << endl;
    	prev_iterate(root);
    	putchar(10);
    	putchar(10);
    	cout << "后序遍历：" << endl;
    	next_itertor(root);
    	putchar(10);
    	putchar(10);
    	cout << "中序遍历：" << endl;
    	mid_itertor(root);
    	putchar(10);
    	putchar(10);
    }