tree-test

benbenlzw / 2023-07-03 / 原文

#include <iostream>
#include <stack>

using namespace std;

typedef struct BiTNode{
	char data;
	struct BiTNode* lchild;
	struct BiTNode* rchild;
}BiTNode,*BiTree;

void CreateTree(BiTree* Tree){
	char ch;
	ch=getchar();
	if(ch=='.')	*Tree=NULL;
	else{
		*Tree = (BiTree)malloc(sizeof(BiTNode));
		(*Tree)->data=ch;
		CreateTree(&(*Tree)->lchild);
		CreateTree(&(*Tree)->rchild);
	}
} 

void Preorder(BiTree t){
	if(t==NULL)	return;
	cout<<t->data;
	Preorder(t->lchild);
	Preorder(t->rchild);
}

void Inorder(BiTree t){
	if(t==NULL)	return;
	stack<BiTree> s;
	BiTree p=t;
	while(p!=NULL || !s.empty()){
		if(p!=NULL){
			s.push(p);
			p=p->lchild;
		}else{
			p=s.top();
			cout<<p->data<<" ";
			s.pop();
			p=p->rchild; 
		}
	}
} 

void Postorder(BiTree root){
	stack<BiTree> s;
	BiTree p=root,r=NULL;
	while(p!=NULL || !s.empty()){
		while(p!=NULL){
			s.push(p);
			p=p->lchild;
		}
		if(!s.empty()){
			p=s.top();
			if(p==NULL || p->rchild==r){
				cout<<p->data<<" ";
				r=p;
				p=NULL;
				s.pop();
			}else{
				p=p->rchild;
			}
		}
	} 
}

int PostTreeDepth(BiTree root){
	if(root==NULL)	return 0;
	int l,r,res;
	l=PostTreeDepth(root->lchild);
	r=PostTreeDepth(root->rchild)；
	res=(l>r)?l:r;
	return res+1; 
}

int main(){
	BiTree t=NULL;
	CreateTree(&t);
	Preorder(t);
	return 0;
}