二叉树的遍历与凹入表形式的二叉树打印

悠悠 2023-05-30 09:08 2阅读 0赞

二叉树：

创建二叉树时以先序输入，以空格表示输入结束，用递归和非递归的方式实现了二叉树的先序遍历、中序遍历、后序遍历，同时也实现了以凹入表的形式打印二叉树

#include <iostream>
    #include <stack>
    #include <queue>
    
    typedef char Elemtype;
    constexpr int UNIT = 3;
    
    typedef struct BiTree {
    	Elemtype data;
    	struct BiTree* lchild, * rchild;
    } BiTree;
    
    BiTree* CreateBiTree();				// 以先序方式接收输入
    void preTranverse1(BiTree* t);		// 递归DLR
    void preTranverse2(BiTree* t);		// 非递归DLR
    void inTranverse1(BiTree* t);		// 递归LDR
    void inTranverse2(BiTree* t);		// 非递归LDR
    void postTranverse1(BiTree* t);		// 递归LRD
    void postTranverse2(BiTree* t);		// 非递归LRD
    void print(BiTree* t, int n);		// 以凹入表形式打印二叉树
    void Visit(BiTree* t);				// 访问每个节点
    
    int main() {
    	BiTree* pT = CreateBiTree();
    	std::cout << "先序遍历（递归）的结果是：";
    	preTranverse1(pT);
    	std::cout << std::endl;
    	std::cout << "先序遍历（非递归）的结果是：";
    	preTranverse2(pT);
    	std::cout << std::endl;
    	std::cout << "中序遍历（递归）的结果是：";
    	inTranverse1(pT);
    	std::cout << std::endl;
    	std::cout << "中序遍历（非递归）的结果是：";
    	inTranverse2(pT);
    	std::cout << std::endl;
    	std::cout << "后序遍历（递归）的结果是：";
    	postTranverse1(pT);
    	std::cout << std::endl;
    	std::cout << "后序遍历（非递归）的结果是：";
    	postTranverse2(pT);
    	std::cout << std::endl;
    	std::cout << "二叉树的结构为：" << std::endl;
    	print(pT, 0);
    
    	return 0;
    }
    
    BiTree* CreateBiTree() {
    	BiTree* pT = nullptr;
    	Elemtype a;
    	std::cin.get(a);
    	if (a != ' ') {
    		pT = new BiTree;
    		pT->data = a;
    		//pT->depth = d++;
    		pT->lchild = CreateBiTree();
    		pT->rchild = CreateBiTree();
    	}
    	return pT;
    }
    
    void preTranverse1(BiTree* t) {
    	if (t) {
    		Visit(t);
    		preTranverse1(t->lchild);
    		preTranverse1(t->rchild);
    	}
    }
    
    void preTranverse2(BiTree* t) {
    	std::stack<BiTree*> s;
    	BiTree* p = t;
    	while (p || !s.empty()) {
    		if (p != nullptr) {
    			s.push(p);
    			Visit(p);
    			p = p->lchild;
    		}
    		else {
    			p = s.top();
    			s.pop();
    			p = p->rchild;
    		}
    	}
    }
    
    void inTranverse1(BiTree* t) {
    	if (t) {
    		inTranverse1(t->lchild);
    		Visit(t);
    		inTranverse1(t->rchild);
    	}
    }
    
    void inTranverse2(BiTree* t) {
    	std::stack<BiTree*> s;
    	BiTree* p = t;
    	while (p || !s.empty()) {
    		if (p != nullptr) {
    			s.push(p);
    			p = p->lchild;
    		}
    		else {
    			p = s.top();
    			Visit(p);
    			s.pop();
    			p = p->rchild;
    		}
    	}
    }
    
    void postTranverse1(BiTree* t) {
    	if (t) {
    		postTranverse1(t->lchild);
    		postTranverse1(t->rchild);
    		Visit(t);
    	}
    }
    
    void postTranverse2(BiTree* t) {
    	std::stack<BiTree*> s;
    	BiTree* p = t, * q = nullptr;
    	while (p || !s.empty()) {
    		if (p) {
    			s.push(p);
    			p = p->lchild;
    		}
    		else {
    			p = s.top();
    			if (p->rchild != nullptr && p->rchild != q) {
    				p = p->rchild;
    			}
    			else {
    				s.pop();
    				Visit(p);
    				q = p;
    				p = nullptr;
    			}
    		}
    	}
    }
    
    void print(BiTree* t, int n) {
    	if (t) {
    		print(t->rchild, n + 1);
    		for (int i = 0; i < n * UNIT; i++)
    			std::cout << " ";
    		std::cout << t->data << std::endl;
    		print(t->lchild, n + 1);
    	}
    }
    
    void Visit(BiTree* t) {
    	if (t->data != ' ')
    		std::cout << t->data << " ";
    }