bitree.cpp

来自「交换二叉数的左右孩子,如果只有一个孩子则把它移到另一边」· C++ 代码 · 共 85 行

#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}JD;
JD* CreateBitree(JD *bt)
{
	char ch;
	printf("ch=");
	scanf("%c",&ch);
	getchar();
	if(ch==' ') bt=NULL;
	else
	{
		bt=(JD *)malloc(sizeof (JD));
		printf("左孩子:");
		bt->lchild=CreateBitree(bt->lchild);
		bt->data=ch;
		printf("右孩子:");
		bt->rchild=CreateBitree(bt->rchild);
	}
	return(bt); 
}
void PostOrder(JD *root)
{
	JD *p;
	p=root;
    if(p!=NULL)
	{
		PostOrder(p->lchild);
		cout<<p->data<<" ";
		PostOrder(p->rchild);
	}
}
void ChangeTree(JD* root)
{
	JD* p;
	p=root; 
	if(p->lchild!=NULL&&p->rchild!=NULL)
	{
		JD* q;
		q=p->lchild;
		p->lchild=p->rchild;
		p->rchild=q;
	}
	else if(p->lchild!=NULL&&p->rchild==NULL)
	{
		JD* q1=(JD *)malloc(sizeof (JD));
		p->rchild=q1;
		p->rchild=p->lchild;
	    p->lchild=NULL;
	}
	else if(p->lchild==NULL&&p->rchild!=NULL)
	{
		JD* q2=(JD *)malloc(sizeof (JD));
		p->lchild=q2;
		p->lchild=p->rchild;
		p->rchild=NULL;
	}
}
void XChange(JD* root)
{
	JD* p=root;
	if(p!=NULL)
	{
	ChangeTree(p);
	XChange(p->lchild);
	XChange(p->rchild);
	}
}
void main()
{
	JD* head=NULL;
    head=CreateBitree(head);
	JD* q=head;
	PostOrder(head);
	XChange(q);
	cout<<endl;
	PostOrder(q);
	cout<<endl;
}