二叉树先中后序遍历代码实现

目录

声明

以下内容仅供学习,如有侵权,联系作者删除。
参考文献:王道考研系列数据结构、B站up主:C语言技术网
链接: C语言技术网

代码实现

/* * 程序名:btree2.c,此程序演示二叉树的前序遍历、中序遍历和后序遍历,包括递归和非递归两种方法。 * 作者:jack 日期:20210708 * 参考作者:C语言技术网(www.freecplus.net), B站UP主:C语言技术网 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

///
// 二叉树的数据结构。
typedef struct BiTNode
{ 
	char data;				// 存放结点的数据元素。
	struct BiTNode *Lchild;	// 指向左子结点地址的指针。
	struct BiTNode *Rchild;	// 指向右子结点地址的指针。
}BiTNode, *BiTree;

///



// 栈的数据结构。
#define MAXSIZE 30       // 顺序栈的最大长度。

typedef BiTree ElemType;	// 自定义栈的数据元素为二叉树。

typedef struct
{ 
	ElemType data[MAXSIZE];	// 用数组存储顺序栈中的元素。
	int top;				// 栈顶指针,从0到MAXSIZE-1,-1表示空栈。
							// 也可以从1到MAXSIZE,0表示空栈。
}SeqStack, *PSeqStack;




// 顺序栈SS的初始化操作。
void InitStack(PSeqStack SS);

// 清空顺序栈。
void ClearStack(PSeqStack SS);

// 求顺序栈的长度,返回值:栈SS中元素的个数。
int Length(PSeqStack SS);

// 判断顺序栈是否为空,返回值:1-空,0-非空或失败。
int IsEmpty(PSeqStack SS);

// 判断顺序栈是否已满,返回值:1-已满,0-未满或失败。
int IsFull(PSeqStack SS);

// 打印顺序栈中全部的元素。
void PrintStack(PSeqStack SS);

// 获取栈顶元素,返回值:0-失败;1-成功。
// 只查看栈顶元素的值,元素不出栈。
int GetTop(PSeqStack SS, ElemType *ee);

// 元素入栈,返回值:0-失败;1-成功。
int Push(PSeqStack SS, ElemType *ee);

// 元素出栈,返回值:0-失败;1-成功。
int Pop(PSeqStack SS, ElemType *ee);



// 求二叉树的高度。
int TreeDepth(BiTree TT);

// 访问结点元素。
void visit(BiTNode *pp);

// 采用递归的方法对二叉树的先序遍历。
void PreOrder(BiTree TT);
// 不采用递归的方法对二叉树的先序遍历。
void PreOrder1(BiTree TT);

// 采用递归的方法对二叉树的中序遍历。
void InOrder(BiTree TT);
// 不采用递归的方法对二叉树的中序遍历。
void InOrder1(BiTree TT);

// 采用递归的方法对二叉树的后序遍历。
void PostOrder(BiTree TT);
// 不采用递归的方法对二叉树的后序遍历。
//void PostOrder1(BiTree TT);


int main()
{ 
	BiTree TT = 0; // 声明树指针变量。

  /* // 手工构造一个如下结构的二叉树。 1 / \ 2 3 / \ / 4 5 6 / \ / \ 7 8 9 0 */

  // 分配根节点。
	TT = (BiTNode *)malloc(sizeof(BiTNode));
	TT->data = '1';
	TT->Lchild = TT->Rchild = 0;

	// 第二层第一个节点。
	TT->Lchild = (BiTNode *)malloc(sizeof(BiTNode));
	TT->Lchild->data = '2'; TT->Lchild->Lchild = TT->Lchild->Rchild = 0;

	// 第二层第二个节点。
	TT->Rchild = (BiTNode *)malloc(sizeof(BiTNode));
	TT->Rchild->data = '3'; TT->Rchild->Lchild = TT->Rchild->Rchild = 0;

	// 第三层第一个节点。
	TT->Lchild->Lchild = (BiTNode *)malloc(sizeof(BiTNode));
	TT->Lchild->Lchild->data = '4'; TT->Lchild->Lchild->Lchild = TT->Lchild->Lchild->Rchild = 0;

	// 第三层第二个节点。
	TT->Lchild->Rchild = (BiTNode *)malloc(sizeof(BiTNode));
	TT->Lchild->Rchild->data = '5'; TT->Lchild->Rchild->Lchild = TT->Lchild->Rchild->Rchild = 0;

	// 第三层第三个节点。
	TT->Rchild->Lchild = (BiTNode *)malloc(sizeof(BiTNode));
	TT->Rchild->Lchild->data = '6'; TT->Rchild->Lchild->Lchild = TT->Rchild->Lchild->Rchild = 0;

	// 第四层第一个节点。
	TT->Lchild->Lchild->Lchild = (BiTNode *)malloc(sizeof(BiTNode));
	TT->Lchild->Lchild->Lchild->data = '7'; TT->Lchild->Lchild->Lchild->Lchild = TT->Lchild->Lchild->Lchild->Rchild = 0;

	// 第四层第二个节点。
	TT->Lchild->Lchild->Rchild = (BiTNode *)malloc(sizeof(BiTNode));
	TT->Lchild->Lchild->Rchild->data = '8'; TT->Lchild->Lchild->Rchild->Lchild = TT->Lchild->Lchild->Rchild->Rchild = 0;

	// 第四层第三个节点。
	TT->Lchild->Rchild->Lchild = (BiTNode *)malloc(sizeof(BiTNode));
	TT->Lchild->Rchild->Lchild->data = '9'; TT->Lchild->Rchild->Lchild->Lchild = TT->Lchild->Rchild->Lchild->Rchild = 0;

	// 第四层第四个节点。
	TT->Lchild->Rchild->Rchild = (BiTNode *)malloc(sizeof(BiTNode));
	TT->Lchild->Rchild->Rchild->data = '0'; TT->Lchild->Rchild->Rchild->Lchild = TT->Lchild->Rchild->Rchild->Rchild = 0;

	// 二叉树的先序遍历。
	printf("先序遍历结果1:"); PreOrder(TT); printf("\n");
	printf("先序遍历结果2:"); PreOrder1(TT); printf("\n");

	// 二叉树的中序遍历。
	printf("中序遍历结果1:"); InOrder(TT); printf("\n");
	printf("中序遍历结果2:"); InOrder1(TT); printf("\n");

	// 二叉树的后序遍历。
	printf("后序遍历结果1:"); PostOrder(TT); printf("\n");
	//printf("后序遍历结果2:"); PostOrder1(TT); printf("\n");


	// 求二叉树的高度。
	printf("树的高度是:%d\n", TreeDepth(TT));

	return 0;
}

// 访问结点元素。
void visit(BiTNode *pp)
{ 
	printf("%c ", pp->data);  // 访问结点元素就是把值输出来,意思一下就行了。
}

// 二叉树的先序遍历。
void PreOrder(BiTree TT)
{ 
	if (TT == NULL) return;

	visit(TT);               // 访问子树TT的根结点。
	PreOrder(TT->Lchild);    // 遍历左子树。
	PreOrder(TT->Rchild);    // 遍历右子树。
}

// 二叉树的中序遍历。
void InOrder(BiTree TT)
{ 
	if (TT == NULL) return;

	InOrder(TT->Lchild);     // 遍历左子树。
	visit(TT);               // 访问子树TT的根结点。
	InOrder(TT->Rchild);     // 遍历右子树。
}

// 二叉树的后序遍历。
void PostOrder(BiTree TT)
{ 
	if (TT == NULL) return;

	PostOrder(TT->Lchild);     // 遍历左子树。
	PostOrder(TT->Rchild);     // 遍历右子树。
	visit(TT);                 // 访问子树TT的根结点。
}

// 不采用递归的方法对二叉树的先序遍历。
void PreOrder1(BiTree TT)
{ 
	SeqStack SS;     // 创建顺序栈。

	InitStack(&SS);  // 初始化顺序栈。

	ElemType ee = TT;  // 栈的元素是二叉树。

	while ((ee != NULL) || (IsEmpty(&SS) != 1))
	{ 
		if (ee != NULL)
		{ 
			visit(ee);               // 入栈前访问。
			Push(&SS, &ee);           // 入栈。
			ee = ee->Lchild;           // 继续处理左子树。
		}
		else
		{ 
			Pop(&SS, &ee);            // 出栈。
			ee = ee->Rchild;           // 处理右子树。 
		}
	}
}

// 不采用递归的方法对二叉树的中序遍历。
void InOrder1(BiTree TT)
{ 
	SeqStack SS;     // 创建顺序栈。

	InitStack(&SS);  // 初始化顺序栈。

	ElemType ee = TT;  // 栈的元素是二叉树。

	while ((ee != NULL) || (IsEmpty(&SS) != 1))
	{ 
		if (ee != NULL)
		{ 
			Push(&SS, &ee);        // 入栈。
			ee = ee->Lchild;        // 继续处理左子树。
		}
		else
		{ 
			Pop(&SS, &ee);        // 出栈。
			visit(ee);           // 访问出栈元素。
			ee = ee->Rchild;       // 处理右子树。
		}
	}
}

// 求二叉树的高度。
int TreeDepth(BiTree TT)
{ 
	if (TT == NULL) return 0;

	int ll = TreeDepth(TT->Lchild);  // 求左子树的高度。

	int rr = TreeDepth(TT->Rchild);  // 求右子树的高度。

	return ll > rr ? ll + 1 : rr + 1;  // 取左、右子树的较大者再加上根结点的高度。
}

// 顺序栈SS的初始化操作。
void InitStack(PSeqStack SS)
{ 
	ClearStack(SS);	// 清空顺序栈。
}

// 清空顺序栈。
void ClearStack(PSeqStack SS)
{ 
	if (SS == NULL)  return;	// 检查空指针。

	SS->top = -1;				// 栈顶指针置为-1。
	memset(SS->data, 0, sizeof(ElemType) * MAXSIZE);	// 数组元素清零。
}

// 求顺序栈的长度,返回值:栈SS中元素的个数。
int Length(PSeqStack SS)
{ 
	if (SS == NULL) return 0; // 检查空指针。

	return SS->top + 1;
}


// 判断顺序栈是否为空,返回值:1-空,0-非空或失败。
int IsEmpty(PSeqStack SS)
{ 
	if (SS == NULL) return 0;  // 检查空指针。

	if (SS->top == -1) return 1;

	return 0;
}

// 判断顺序栈是否已满,返回值:1-已满,0-未满或失败。
int IsFull(PSeqStack SS)
{ 
	if (SS == NULL) return 0;  // 检查空指针。

	if (SS->top >= MAXSIZE - 1) return 1;

	return 0;
}

// 元素入栈,返回值:0-失败;1-成功。
int Push(PSeqStack SS, ElemType *ee)
{ 
	if ((SS == NULL) || (ee == NULL)) return 0;  // 检查空指针。

	if (IsFull(SS) == 1)
	{ 
		printf("顺序栈已满,不能插入。\n"); return 0;
	}

	SS->top++;  // 栈指针先加1。

	memcpy(&SS->data[SS->top], ee, sizeof(ElemType));  // 用数组的下标访问。
	// memcpy(SS->data+SS->top,ee,sizeof(ElemType)); // 采用指针运算也可以。

	return 1;
}

// 打印顺序栈中全部的元素。
void PrintStack(PSeqStack SS)
{ 
	if (SS == NULL) return;  // 检查空指针。

	if (SS->top == -1) {  printf("栈为空。\n"); return; }

	int kk;
	for (kk = 0; kk <= SS->top; kk++)
	{ 
		printf("SS[%d],value=%d\n", kk, (SS->data[kk]->data));     // 用数组的下标访问。
		// printf("SS[%d],value=%d\n",kk,*(SS->data+kk)); // 采用指针运算也可以。
	}
}

// 元素出栈,返回值:0-失败;1-成功。
int Pop(PSeqStack SS, ElemType *ee)
{ 
	if ((SS == NULL) || (ee == NULL)) return 0;  // 检查空指针。

	if (SS->top == -1) {  printf("栈为空。\n"); return 0; }

	memcpy(ee, &SS->data[SS->top], sizeof(ElemType));  // 用数组的下标访问。
	// memcpy(ee,SS->data+SS->top,sizeof(ElemType)); // 采用指针运算也可以。

	SS->top--;  // 栈指针减1。

	return 1;
}

// 获取栈顶元素,返回值:0-失败;1-成功。
// 只查看栈顶元素的值,元素不出栈。
int GetTop(PSeqStack SS, ElemType *ee)
{ 
	if ((SS == NULL) || (ee == NULL)) return 0;  // 检查空指针。

	if (IsEmpty(SS) == 1) {  printf("栈为空。\n"); return 0; }

	memcpy(ee, &SS->data[SS->top], sizeof(ElemType));  // 用数组的下标访问。
	// memcpy(ee,SS->data+SS->top,sizeof(ElemType)); // 采用指针运算也可以。

	return 1;
}

运行结果

《二叉树先中后序遍历代码实现》

    原文作者:jack学编程
    原文地址: https://blog.csdn.net/COOL_jack/article/details/118577902
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞