二叉树四种遍历，根据前中，后中遍历序列求二叉树

废江_小江

发布于 2022-09-05 13:41:55

3480

文章被收录于专栏：总栏目总栏目

二叉树代码

#include <stdio.h>
#include <malloc.h>
#include <iostream>
#define MaxSize 100
using namespace std;
typedef int ElemType;
typedef struct node
{
	ElemType data;			//数据元素
	struct node* lchild;	//指向左孩子节点
	struct node* rchild;	//指向右孩子节点
} BTNode;
 
//二叉树本身有节点，是无形的树（因为链表节点结构）
//，创建以及输出二叉树，则是为了视觉效果 ，但反过来没有了创建，也不行 
void CreateBTree(BTNode*& b, char* str)	//创建二叉树
{
	BTNode* St[MaxSize], * p = NULL;
	int top = -1, k, j = 0;
	char ch;
	b = NULL;				//建立的二叉树初始时为空
	ch = str[j];
	while (ch != '\0')  	//str未扫描完时循环
	{
		switch (ch)
		{
		case '(':top++; St[top] = p; k = 1; break;		//为左孩子节点
		case ')':top--; break;
		case ',':k = 2; break;                      		//为孩子节点右节点
		default:p = (BTNode*)malloc(sizeof(BTNode));
			p->data = ch; p->lchild = p->rchild = NULL;
			if (b == NULL)                    	 	//*p为二叉树的根节点
				b = p;
			else  								//已建立二叉树根节点
			{
				switch (k)
				{
				case 1:St[top]->lchild = p; break;
				case 2:St[top]->rchild = p; break;
				}
			}
		}
		j++;
		ch = str[j];
	}
}
void DestroyBTree(BTNode*& b)
{
	if (b != NULL)
	{
		DestroyBTree(b->lchild);
		DestroyBTree(b->rchild);
		free(b);
	}
}
 
//查找某个节点 
BTNode* FindNode(BTNode* b, ElemType x)
{
	BTNode* p;
	if (b == NULL)
		return NULL;
	else if (b->data == x)
		return b;
	else
	{
		p = FindNode(b->lchild, x);
		if (p != NULL)
			return p;
		else
			return FindNode(b->rchild, x);
	}
}
 
//返回某个节点的左节点 
BTNode* LchildNode(BTNode* p)
{
	return p->lchild;
}
//返回某个节点的右节点 
BTNode* RchildNode(BTNode* p)
{
	return p->rchild;
}
//返回树的高度 
int BTHeight(BTNode* b)
{
	int lchildh, rchildh;
	if (b == NULL) return(0); 				//空树的高度为0
	else
	{
		lchildh = BTHeight(b->lchild);	//求左子树的高度为lchildh
		rchildh = BTHeight(b->rchild);	//求右子树的高度为rchildh
		return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);
	}
}
void DispBTree(BTNode* b)
{
	if (b != NULL)
	{
		/*printf("%c", b->data);*/
		cout << b->data;
		if (b->lchild != NULL || b->rchild != NULL)
		{
			printf("(");						//有孩子节点时才输出(
			DispBTree(b->lchild);				//递归处理左子树
			if (b->rchild != NULL) printf(",");	//有右孩子节点时才输出,
			DispBTree(b->rchild);				//递归处理右子树
			printf(")");						//有孩子节点时才输出)
		}
	}
}
 
void PreOrder(BTNode* b)  		//先序遍历的递归算法
{
	if (b != NULL)
	{
		//printf("%c ", b->data);	//访问根结点
		cout << b->data << " ";
		PreOrder(b->lchild);	//先序遍历左子树
		PreOrder(b->rchild);	//先序遍历右子树
	}
}
void InOrder(BTNode* b)   		//中序遍历的递归算法
{
	if (b != NULL)
	{
		InOrder(b->lchild);		//中序遍历左子树
		//printf("%c ", b->data);	//访问根结点
		cout << b->data << " ";
		InOrder(b->rchild);		//中序遍历右子树
	}
}
void PostOrder(BTNode* b) 		//后序遍历的递归算法
{
	if (b != NULL)
	{
		PostOrder(b->lchild);	//后序遍历左子树
		PostOrder(b->rchild);	//后序遍历右子树
		//printf("%c ", b->data);	//访问根结点
		cout << b->data << " ";
	}
}
 
 
//--------------------------------------------------------
//--循环队列基本运算算法----------------------------------
//--------------------------------------------------------
typedef struct
{
	BTNode* data[MaxSize];				//存放队中元素
	int front, rear;						//队头和队尾指针
} SqQueue;								//顺序队类型
void InitQueue(SqQueue*& q)				//初始化队列
{
	q = (SqQueue*)malloc(sizeof(SqQueue));
	q->front = q->rear = 0;
}
void DestroyQueue(SqQueue*& q)			//销毁队列
{
	free(q);
}
bool QueueEmpty(SqQueue* q)				//判断队列是否为空
{
	return(q->front == q->rear);
}
bool enQueue(SqQueue*& q, BTNode* e)		//进队列
{
	if ((q->rear + 1) % MaxSize == q->front)	//队满上溢出
		return false;
	q->rear = (q->rear + 1) % MaxSize;
	q->data[q->rear] = e;
	return true;
}
bool deQueue(SqQueue*& q, BTNode*& e)	//出队列
{
	if (q->front == q->rear)				//队空下溢出
		return false;
	q->front = (q->front + 1) % MaxSize;
	e = q->data[q->front];
	return true;
}
//--------------------------------------------------------
 
 //层次遍历输出二叉树 
void LevelOrder(BTNode* b)
{
	BTNode* p;
	SqQueue* qu;
	InitQueue(qu);					//初始化队列
	enQueue(qu, b);					//根结点指针进入队列
	while (!QueueEmpty(qu))			//队不为空循环
	{
		deQueue(qu, p);				//出队节点p
		printf("%c ", p->data);		//访问节点p
		if (p->lchild != NULL)		//有左孩子时将其进队
			enQueue(qu, p->lchild);
		if (p->rchild != NULL)		//有右孩子时将其进队
			enQueue(qu, p->rchild);
	}
}
 
/**
	根据先序遍历和中序遍历求出二叉树
 
	扩展知识：这里理解一下指针就是数组的：
	int a[3] ={1,2,3};
	int *b =a;
	int *c =a+2;
	cout<<a<<endl;//0x6ffe00
	cout<<*b<<endl;//1
	cout<<*c<<endl;	//3
	//指向指针的指针，和链表那样，d指针和b指针指向同一个地址 
	int *d = b;
	cout<<d<<endl;//0x6ffdf0 
	cout<<*d<<endl;//1
	//指针和指针相减：只有当两个指针指向同一数组，才有意义，相减等于其他元素个数，
	int count =c-b;
	cout<<count<<endl;
*/
BTNode* ConstructByPreAndIn(ElemType* preorder, ElemType* inorder, int length);
BTNode* ConstructCoreByPreAndIn(ElemType* startPreOrder, ElemType* endPreOrder, ElemType* startInOrder, ElemType* endInOrder);
 
 
BTNode* ConstructByPreAndIn(ElemType* preorder, ElemType* inorder, int length)
{
	if (preorder == NULL || inorder == NULL || length <= 0)
	{
		return NULL;
	}
	return ConstructCoreByPreAndIn(preorder, preorder + length - 1, inorder, inorder + length - 1);
}
 
//startPreOrder表示PreOrder的起始地址，endPreOrder表示PreOrder的结束地址
BTNode* ConstructCoreByPreAndIn(ElemType* startPreOrder, ElemType* endPreOrder, ElemType* startInOrder, ElemType* endInOrder)
{	
	//rootVal表示跟节点数据
	ElemType rootVal = *startPreOrder;//{ 1, 2, 4, 7, 3, 5, 6, 8 };
	// 前序遍历的第一个数字为根节点
	BTNode* root = new BTNode();
	root->data = rootVal;
	root->lchild = NULL;
	root->rchild = NULL;
	// 如果输入的只有一个数字,这里是把地址作比较！
	if (startPreOrder == endPreOrder)
	{
		// 如果中序遍历也只有一个数字并且这两个数字相等
		if (startInOrder == endInOrder && *startPreOrder == *startInOrder)
		{
			return root;
		}
		else
		{
			//throw exception("Invalid input");
			cout << "Invalid Input" << endl;
			return NULL;
		}
	}
	// 在中序遍历中找到根节点位置
	ElemType* rootInOrder = startInOrder;
	while (rootInOrder <= endInOrder && *rootInOrder != rootVal)
	{
		rootInOrder++;
	}
	if (rootInOrder > endInOrder || *rootInOrder != rootVal)
	{
		//throw exception("Invalid Input");
		cout << "Invalid Input" << endl;
		return NULL;
	}
	//{ 1, 2, 4, 7, 3, 5, 6, 8 };
	//{ 4, 7, 2, 1, 5, 3, 8, 6 };rootInOrder 1
	//lefyLength = 3 - 0;
	//leftPreOrderEnd = 0 + 3;
	//在中序遍历中找到根节点，根据中序遍历计算左子树长度
	//
	int leftLength = rootInOrder - startInOrder;
	int* leftPreOrderEnd = startPreOrder + leftLength;
 
	//从广度思考去想，root=1的左右子树就是这两个（247）（3568）
	//那么直接root->lchild和root->rchild给他们和下面main中这句
	//BTNode* root = Construct(preOrder, inOrder, 8);
	//是一样的，这点理解后，就只有一个目的，找出（247）（3568）！
	//这就很简单了，后序遍历大同小异
	if (leftLength > 0)
	{	
		//2,4,7 || 4,7,2
		root->lchild = ConstructCoreByPreAndIn(startPreOrder + 1, leftPreOrderEnd, startInOrder, rootInOrder - 1);
	}
	if (leftLength < endPreOrder - startPreOrder)
	{	
		//3,5,6,8 || 5,3,8,6
		root->rchild = ConstructCoreByPreAndIn(leftPreOrderEnd + 1, endPreOrder, rootInOrder + 1, endInOrder);
	}
	return root;
}
 
 
/**
	根据中序遍历和后序遍历求出二叉树
*/
BTNode* ConstructByPostAndIn(ElemType* postorder, ElemType* inorder, int length);
BTNode* ConstructCoreByPostAndIn(ElemType* startPostOrder, ElemType* endPostOrder, ElemType* startInOrder, ElemType* endInOrder);
 
BTNode* ConstructByPostAndIn(ElemType* postorder, ElemType* inorder, int length)
{
	if (postorder == NULL || inorder == NULL || length <= 0)
	{
		return NULL;
	}
	return ConstructCoreByPostAndIn(postorder, postorder + length - 1 , inorder, inorder + length - 1);
}
 
 
BTNode* ConstructCoreByPostAndIn(ElemType* startPostOrder, ElemType* endPostOrder, ElemType* startInOrder, ElemType* endInOrder)
{
	//rootVal表示跟节点数据
	ElemType rootVal = *endPostOrder;//1
	// 调试： cout << "k: "<< rootVal << endl;
	// 后序遍历的最后一个数字为根节点
	BTNode* root = new BTNode();
	root->data = rootVal;
	root->lchild = NULL;
	root->rchild = NULL;
	// 如果输入的只有一个数字
	if (startPostOrder == endPostOrder)
	{
		// 如果中序遍历也只有一个数字并且这两个数字相等
		if (startInOrder == endInOrder && *startPostOrder == *startInOrder)
		{
			return root;
		}
		else
		{
			cout << "Invalid Input" << endl;
			return NULL;
		}
	}
	// 在中序遍历中找到根节点位置
	ElemType* rootInOrder = startInOrder;
	while (rootInOrder <= endInOrder && *rootInOrder != rootVal)
	{
		rootInOrder++;
	}
	if (rootInOrder > endInOrder || *rootInOrder != rootVal)
	{
		cout << "xxxInvalid Input" << endl;
		return NULL;
	}
	/**
	*
		endPostOrder会每次-1，当兵临到全部递归完跟节点的左子树时，endPostOrder再减去1就会越界了，
		leftLength就是左子树的长度，在前序和中序遍历时，当其大于0遍历左子树，当其，小于，。。。
		对于前序和中序遍历，逼近根节点的左子树时候，是start在逼近，end不动，一步步逼近
		对于后续和中序遍历，逼近根节点的左子树时候，是start不动，end在逼近，
		这就会出现一个不同的判断现象，start逼近，不会越界，临界值是0；end逼近，会越界，临界值指向-4123123213xxx
 
	*/
 
	//leftLength左子树的长度,leftPostOrderEnd后序遍历中左子树结束的地址
	int leftLength = rootInOrder - startInOrder;//3
	//int* leftPreOrderEnd = startPreOrder + leftLength;
	int* leftPostOrderEnd = startPostOrder + leftLength ;//0+3
	if (leftLength > 0)
	{	
		//传入后序遍历中，左子树起始地址，左子树结束地址，中序遍历中起始地址，中子树中根节点-1的地址（即根节点中左子树结束地址）
		root->lchild = ConstructCoreByPostAndIn(startPostOrder , leftPostOrderEnd - 1, startInOrder, rootInOrder - 1);
	}
	
	//rigthLength = end - start -leftLength
	//rightLength > 0 等价于
	//leftLength <end - start
	if (leftLength < endPostOrder - startPostOrder)
	{	
		//cout << *leftPostOrderEnd << *endPostOrder << *rootInOrder << *endInOrder << endl;
		root->rchild = ConstructCoreByPostAndIn(leftPostOrderEnd , endPostOrder - 1, rootInOrder + 1, endInOrder);
 
		
	}
	return root;
}
 
 
int main()
{
	BTNode* b;
	CreateBTree(b, "A(B(D(,G)),C(E,F))");
	printf("b:"); DispBTree(b); printf("\n");
	printf("先序遍历序列:"); PreOrder(b); printf("\n");
	printf("中序遍历序列:"); InOrder(b); printf("\n");
	printf("后序遍历序列:"); PostOrder(b); printf("\n");
	printf("层次遍历序列:"); LevelOrder(b); printf("\n");
	DestroyBTree(b);
 
	//
	ElemType preOrder[8] = { 1, 2, 4, 7, 3, 5, 6, 8 };
	ElemType inOrder[8] = { 4, 7, 2, 1, 5, 3, 8, 6 };
	ElemType postOrder[8] = {  7, 4, 2, 5, 8, 6, 3, 1 };
	BTNode* root = ConstructByPreAndIn(preOrder, inOrder, 8);
	DispBTree(root); cout << endl;
 
	BTNode* root2 = ConstructByPostAndIn(postOrder, inOrder, 8);
	DispBTree(root); cout << endl;
	
 
 
	return 0;
}

代码讲解

存储结构

typedef struct node
{
	ElemType data;			//数据元素
	struct node* lchild;	//指向左孩子节点
	struct node* rchild;	//指向右孩子节点
} BTNode;
 
typedef struct linknode{
	int data;
	struct linknode *next;
}sqstack;

采用指针+结点来存储二叉树，链表栈也是如此， BTNode本身也是一个指针节点，可以指向和其一样结构的地址，所以，struct结构体中的结点也是struct结构体类型

根据中后序遍历求树思路

ElemType preOrder[7] = { 'A','B','D','G','C','E','F' };
ElemType inOrder[7] = { 'D','G','B','A','E','C','F' };
ElemType postOrder[7] = { 'G','D','B','E','F','C','A' };

先观察后序遍历和中序遍历的数组分析一下，可以发现，后序遍历的最后一个值就是根节点，又可以从中序遍历中找出根节点，中序遍历的根节点前面都是左子树，根节点的后面都是右子树；这里所说的左右子树是相对于根节点A的。那么，现在我们得到的数据有，根节点A，根节点A左边的所有左子树x，根节点A右边的所有右子树y。对于x，y两棵树，就是和总树一样。又可以使用同样的方法去求根节点和左右子树。这就是递归方法了。如何把求出的根节点存到结点表示的树中？在使用函数求出根节点A后，在使用函数递归调用，求出的A的左边的左子树的根节点，不就是根结点A的左结点吗？

//传入后序遍历中，左子树起始地址，左子树结束地址，中序遍历中起始地址，中子树中根节点-1的地址（即根节点中左子树结束地址）
root->lchild = ConstructCoreByPostAndIn(startPostOrder , leftPostOrderEnd - 1, startInOrder, rootInOrder - 1);

root->rchild = ConstructCoreByPostAndIn(leftPostOrderEnd , endPostOrder - 1, rootInOrder + 1, endInOrder);

这个问题也解决了，最终函数会返回一个头结点root给我们，并且已经帮我们拼接好了root结点下面的所有结点。

指针与数组知识

	int a[3] ={1,2,3};
	int *b =a;
	int *c =a+2;
	cout<<a<<endl;//0x6ffe00
	cout<<*b<<endl;//1
	cout<<*c<<endl;	//3
	//指向指针的指针，和链表那样，d指针和b指针指向同一个地址 
	int *d = b;
	cout<<d<<endl;//0x6ffdf0 
	cout<<*d<<endl;//1
	//指针和指针相减：只有当两个指针指向同一数组，才有意义，相减等于其他元素个数，
	int count =c-b;
	cout<<count<<endl;
//	重合指针相减为0
	cout<<"d-b: "<<d-b<<endl; 
	
 
	cout<<"------------------------"<<endl;
	char p[4] = {'a','b','c','d'};
	char *q = p;
	cout<<q<<endl;//abcd
	cout<<q+2<<endl;//cd

运行结果： 0x6ffdd0 1 3 0x6ffdd0 1 2 d-b: 0 ———————— abcd cd

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-05-09)，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

登录后参与评论

0 条评论

热度