binarytree.cpp

二叉树的建立与二叉树遍历 非递归的先序

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 50
typedef struct node
{
	char data;
	struct node *lchild;
	struct node *rchild;
}node,*Blink;
Blink BT;
Blink createbitree(Blink t)
{
	char ch;
	scanf("%c",&ch);
	if(ch==' ')
		t=NULL;
	else
	{
		t=(Blink)malloc(sizeof(node));
        if(!t)
			exit(1);
		t->data=ch;
		t->lchild=createbitree(t->lchild);
		t->rchild=createbitree(t->rchild);	
	}
	return t;
}
int findleaf(Blink t)
{
	if(!t)
		return 0;
	else if(!(t->lchild) && !(t->rchild))
		return 1;
	else
		return findleaf(t->lchild)+findleaf(t->rchild);	
}

void preorder(Blink t)
{
	if(t)
	{
		printf("%c ",t->data);
		preorder(t->lchild);
		preorder(t->rchild);
	}
}
void inorder(Blink t)
{
	if(t)
	{
		inorder(t->lchild);
		printf("%c ",t->data);
		inorder(t->rchild);
	}
}
void lastorder(Blink t)
{
	if(t)
	{
		lastorder(t->lchild);
		lastorder(t->rchild);
		printf("%c ",t->data);
	}
}
void displayleaf(Blink t)
{
	if(t)
	{
		if(!(t->lchild) && !(t->rchild))
		   printf("%c ",t->data);
		displayleaf(t->lchild);
		displayleaf(t->rchild);
	}
}
void levelorder(Blink t)
{
	Blink s[N],q;
	int front=0,rear=0;
	if(t)
	{
		s[rear]=t;
		rear=(rear+1)%N;
	}
	while(front!=rear)
	{
		q=s[front];
		printf("%c ",q->data);
		front=(front+1)%N;
		if(q->lchild!=NULL)
		{
			s[rear]=q->lchild;
			rear=(rear+1)%N;
		}
        if(q->rchild!=NULL)
		{
			s[rear]=q->rchild;
			rear=(rear+1)%N;
		}
	}
	printf("\n");
}
int preorder2(Blink T)
{
	int top=0,m=0;
	Blink s[N],t;
	t=T;
	if(t)
	{
		while(t || top)
		{
			while(t)
			{
				printf("%c ",t->data);
                if(!(t->lchild) && !(t->rchild))
                    m++;
				s[top]=t;
				top++;
				t=t->lchild;
			}
			if(top)
			{ 
			  top--;
		    	t=s[top]->rchild;
			}
		}
	}
	else
		printf("此树为空树!\n");
	return m;
}
void inorder2(Blink T)
{
    int top=0;
	Blink s[N],t;
	t=T;
	while(t || top)
	{
		if(t)
		{
			s[top]=t;
			top++;
			t=t->lchild;
		}
		else
		{
			top--;
			t=s[top];
			printf("%c ",t->data);
			t=t->rchild;
		}
	}
}
void lastorder2(Blink T)
{
	int top=0;
    Blink s[N],t,p;
	t=T;
	while(t || top)
	{	
		while(t)
		{
			s[top]=t;
			top++;
			t=t->lchild;
		}
		while(top)
		{
			t=s[top-1];
			if(t->rchild == NULL || t->rchild == p)
			{
				printf("%c ",t->data);
				p=s[--top];
			}
			else
			{
				t=t->rchild; 
				break;
			}
		
		}
		if(!top)
			break;
		
	}
}
void main()
{
	Blink T=NULL;
	int m;
	printf("输入你所要创建的树;\n");
	T=createbitree(T);
	printf("该二叉树的各结点为(递归前序遍历):\n");
	preorder(T);
	printf("\n");
	printf("该二叉树的各结点为(递归中序遍历):\n");
    inorder(T);
	printf("\n");
	printf("该二叉树的各结点为(递归后序遍历):\n");
	lastorder(T);
	printf("\n");
	printf("该二叉树的各结点为(非递归前序遍历):\n");
	preorder2(T);
	printf("\n");
	printf("该二叉树的各结点为(非递归中序遍历):\n");
    inorder2(T);
	printf("\n");
	printf("该二叉树的各结点为(非递归后序遍历):\n");
	lastorder2(T);
	printf("\n");
	printf("该二叉树的各结点为(层次遍历):\n");
    levelorder(T);
	printf("该二叉树叶子结点数=%d\n",m=findleaf(T));
	printf("叶子结点为:\n");
	displayleaf(T);
	printf("\n");
}