学习用品

二叉树的创建以及以序列创建

1.前序创建

#include<stdlib.h>
#include<malloc.h>
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
typedef  char ElemType;
typedef struct  BtNode
{
	BtNode *leftchild;
	BtNode *rightchild;
	ElemType data;
}BtNode,*BinaryTree;
//购买结点
BtNode *Buynode()
{
	BtNode *p=(BtNode *)malloc(sizeof(BtNode));
	if(NULL==p)  exit(1);
	memset(p,0,sizeof(BtNode));
	return p;
}
void *Freenode(BtNode *ptr)
{
	free(ptr);
}

第一种建树方法(通过结点进行创建二叉树)

//方法一
//前序创建二叉树
void *PreCreateTree(BinaryTree  *ptr)
{
	char ch;
	cin>>ch;
	if(ch!='#'||ptr!=NULL)
        {
		*ptr=Buynode();
		(*ptr)->data=ch;
		PreCreateTree(&(*ptr)->leftchild);
		PreCreateTree(&(*ptr)->rightchild);
	}
}
int main()
{
	BinaryTree root=NULL;
	PreCreateTree(&root);
}

只是空行用

2.用前序和中序创建二叉树

//用前序和中序创建二叉树
*BtNode* CreateTreePI(char ps[],char is[],int n )
{
	if(n<=0)
	{
		return NULL;
	}
	BtNode* p=(BtNode*)malloc(sizeof(BtNode));
	int i=0;
	int m;
	while(i<n)
	{
		if(ps[0]==is[i])
		{
			m=i;
			break;
		}
		++i;
	}
	if(i>=n)
	{
		return NULL;
	}
	p->data=ps[0];
	p->leftchild=CreateTreePI(ps+1,is,m);
	p->rightchild=CreateTreePI(ps+m+1,is+m+1,n-m-1);
	return p;
}

只是空行用

3.用中序和后序创建二叉树

//用中序和后序创建二叉树
BtNode* CreateTreeIL(char is[],char ls[],int n)
{
	if(n<=0)
	{
		return NULL;
	}
	BtNode *p=(BtNode*)malloc(sizeof(BtNode));
	int i=0;
	int m;
	while(i<n)
	{
		if(ls[n-1]==is[i])
		{
			m=i;
			break;
		}
		++i;
	}
	if(i>=n)
	{
		return NULL;
	}
	p->data=ls[n-1];
	p->leftchild= CreateTreeIL(is,ls,m);
	p->rightchild= CreateTreeIL(is+m+1,ls+m,n-m-1);
	return p;
}

只是空行用

文章节选自 https://blog.csdn.net/lingling_nice/article/details/80960439

发表评论

电子邮件地址不会被公开。 必填项已用*标注