二叉树的创建+递归遍历+非递归遍历

落日映苍穹つ 2022-05-19 01:58 323阅读 0赞

#include<iostream>
    #include<stdlib.h>
    #define MAXSIZE 100
    typedef char ElementType; 
    using namespace std;
    
    typedef struct BTNode{
    	ElementType data;
    	struct BTNode *lChild;
    	struct BTNode *rChild;
    }BTNode;
    void createBinaryTree(BTNode *&bt)
    {
    	ElementType data;
    	bt = (BTNode *)malloc(sizeof(BTNode));
    	cin>>data;
    	if(data == '#')
    	{
    		bt = NULL;
    	}
    	else
    	{
    		bt->data = data;
    		createBinaryTree(bt->lChild);
    		createBinaryTree(bt->rChild);
    	}
    }
    void preOrderRecursionVisit(BTNode *bt)
    {
    	if(bt == NULL)
    		return;
    	else
    	{
    		cout<<bt->data<<" ";
    		preOrderRecursionVisit(bt->lChild);
    		preOrderRecursionVisit(bt->rChild);
    	}
    }
    
    void preOrderNonRecursionVisit(BTNode *bt)
    {
    	if(bt == NULL)
    		return;
    	BTNode *stack[MAXSIZE], *tNode;
    	int top = -1;
    	stack[++top] = bt;
    	while(top != -1)
    	{
    		tNode = stack[top--];
    		cout<<tNode->data<<" ";
    		if(tNode->rChild != NULL)
    			stack[++top] = tNode->rChild;
    		if(tNode->lChild != NULL)
    			stack[++top] = tNode->lChild;
    	}
    	cout<<endl; 
    }
    
    void inOrderRecursionVisit(BTNode *bt)
    {
    	if(bt == NULL)
    		return;
    	else
    	{
    		inOrderRecursionVisit(bt->lChild);
    		cout<<bt->data<<" ";
    		inOrderRecursionVisit(bt->rChild);
    	}
    }
    void inOrderNonRecursionVisit(BTNode *bt)
    {
    	if(bt == NULL)
    		return;
    	BTNode *stack[MAXSIZE], *tNode;
    	int top = -1;
    	tNode = bt;
    	while(top != -1 || tNode != NULL)
    	{
    		while(tNode != NULL)
    		{
    			stack[++top] = tNode; 
    			tNode = tNode->lChild; 
    		}
    		if(top != -1)
    		{
    			tNode = stack[top--];
    			cout<<tNode->data<<" ";
    			if(tNode->rChild != NULL)
    				tNode = tNode->rChild;
    			else
    				tNode = NULL;
    		}
    	}
    	cout<<endl; 
    } 
    
    
    void postOrderRecursionVisit(BTNode *bt)
    {
    	if(bt == NULL)
    		return;
    	else
    	{
    		postOrderRecursionVisit(bt->lChild);
    		postOrderRecursionVisit(bt->rChild);
    		cout<<bt->data<<" ";
    	}
    }
    void postOrderNonRecursionVisit(BTNode *bt)
    {
    	if(bt == NULL)
    		return;
    	
    	BTNode *tNode, *stack1[MAXSIZE], *stack2[MAXSIZE];
    	int top1 = -1, top2 = -1;
    	stack1[++top1] = bt;
    	while(top1 != -1)
    	{
    		tNode = stack1[top1--];
    		stack2[++top2] = tNode;
    		if(tNode->lChild != NULL)
    			stack1[++top1] = tNode->lChild;
    		if(tNode->rChild != NULL)
    			stack1[++top1] = tNode->rChild;
    	}
    	while(top2 != -1)
    	{
    		tNode = stack2[top2--];
    		cout<<tNode->data<<" ";
    	}
    	cout<<endl;
    }
    int main()
    {
    	BTNode *bt = NULL;
    	//124##57##8##3#69###
    	createBinaryTree(bt);
    	preOrderRecursionVisit(bt);
    	cout<<endl; 
    	preOrderNonRecursionVisit(bt);
    	
    	inOrderRecursionVisit(bt);
    	cout<<endl;
    	inOrderNonRecursionVisit(bt);
    	postOrderRecursionVisit(bt);
    	cout<<endl;
    	postOrderNonRecursionVisit(bt);
    	
    }