首页 > 其他分享 >数据结构：二叉树

数据结构：二叉树

时间：2022-10-15 21:23:04浏览次数：70  
标签：遍历 qu BiTree fprintf 二叉树 数据结构 节点

定义

特点

  • 每个节点最多有两棵子树，所以二叉树中不存在度大于2的节点。
  • 左子树和右子树是有区别的，次序不能颠倒。
  • 即使某个节点只有1个子节点，也是有左右之分的。

特殊的二叉树：

  1. 斜树：正如上图的树1和树2，向一边斜的二叉树。
  2. 满二叉树：叶子节点都在最后一层，也就是说，非叶子节点都有左右子树

​

  1. 完全二叉树：

    对一棵具有n个节点的二叉树按层序编号，如果编号为 i（1<=i<=n）的节点与同样深度的满二叉树中编号为 i的节点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树，如下图所示

    ​ 就是说，这样 1开始，从左向右，从上至下的编号，如果所有有子节点的节点 i满足：

    ​ 左儿子 j：$ j = 2 * i$ ，右儿子 k: $ k = 2 * i + 1$，那么它就是一棵完全二叉树

    1. 完全二叉树不一定是满二叉树
    2. 满二叉树一定是完全二叉树
    3. 手写的堆就是一棵完全二叉树

性质

  1. 二叉树第 i层最多有\(2^{i-1}\)个节点。
  2. 深度为 k的二叉树最多有\(2^k-1\)个节点。（1 + 2 + 4 + 8 + ··· + \(2^{k - 1}\)）
  3. 有 n个节点的完全二叉树的深度为 \(|log_2n| + 1\) ，\(|x|\)代表对x向下取整。证明略。
  4. 从1开始，将完全二叉树从左到右，从上至下，依次标号(如上图)，那么对于节点 i，左儿子 j：$ j = 2 * i$ ，右儿子 k: $ k = 2 * i + 1$。

存储结构

顺序存储结构

就是刚刚的性质4，存储的是完全二叉树。（也可以不是）

用数组模拟，下标代表树的标号。

主要的应用：线段树，堆

链式存储结构

又名二叉链表，即在结构体中定义两个指针，分别指向它的左儿子和右儿子。

typedef struct BiTNode  /* 结点结构 */
{
   TElemType data;		/* 结点数据 */
   struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;

遍历二叉树

前序遍历

若二叉树为空则返回，否则先访问根节点，再前序遍历左子树，再前序遍历右子树

总结起来：根左右

中序遍历

若二叉树为空则返回，否则先中序遍历左子树，再访问根节点，再中序遍历右子树

总结起来: 左根右

后序遍历

若二叉树为空则返回，否则先后序遍历左子树，再后序遍历右子树，最后访问根节点

总结起来：左右根

层序遍历

顾名思义，一层一层的遍历二叉树。

前三种是递归的遍历，要用到栈，层序遍历则是循环的遍历，要用到队列！

具体实现方法见代码。

作业

作业题目： 二叉树存储结构的建立、遍历和应用树和二叉树遍历是树形结构的最基础、最重要的核心算法。本作业要求掌
握和巩固二叉树的存储结构的建立方法、二叉树的遍历方法、过程及应用。


作业要求：

  1. 编写建立二叉树的动态（或者静态） 二叉链表存储结构（左右链表示） 的程序，并以适当的形式显示和保存二叉树；
  2. 采用二叉树的上述二叉链表存储结构，编写程序实现二叉树的先序、中序和后序遍历的递归和非递归算法以及层序遍历算法， 并以适当的形式显示和保存二叉树及其相应的遍历序列；
  3. 设计并实现判断任意一棵二叉树是否为完全二叉树的算法。
  4. 设计并实现计算任意一棵二叉树的宽度的（递归或非递归）算法。 二叉树的宽度是指其各层结点数的最大值。

思路：

  1. 非递归算法则是手写一个栈用于存储节点信息。
  2. 判断是否为完全二叉树，可采用层序遍历的方式，无论子节点是否为空，都加入到队列中。当遍历到空节点时，退出，判断队列剩余元素是否全为空。如果是则为完全二叉树。
  3. 计算宽度也是用的层序遍历的方法，每一层计算下队头到队尾的元素数，更新最大值即可。

代码

点击查看代码 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>  
#include <time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;		/* Status是函数返回的类型*/

/* 用于构造二叉树 */
int treeIndex = 1;
typedef char String[MAXSIZE]; /*  0号单元存放串的长度 */
String str; // str为初始化的字符串 
FILE *fp;   // 保存用的文件指针 

typedef char TElemType;
TElemType Nil=' '; /* 字符型以空格符为空 */

typedef struct BiTNode  /* 结点结构 */
{
   TElemType data;		/* 结点数据 */
   struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;

/* 非递归使用的栈 */
typedef struct Stack
{
	BiTree s[MAXSIZE];
	int top;	
}Stack;

/* 层序遍历使用的队列 */
typedef struct Queue
{
	BiTree q[MAXSIZE];
	int head;
	int tail;
}Queue;

Status StrAssign(String T,char *chars);	// 前序遍历初始化 
Status visit(TElemType e);				// 访问树的节点元素	
Status InitBiTree(BiTree *T);			// 初始化 
void DestroyBiTree(BiTree *T);			// 释放二叉树 
void CreateBiTree(BiTree *T);			// 建立二叉树
Status BiTreeEmpty(BiTree T);			// 判空 
int BiTreeDepth(BiTree T);				// 求二叉树的深度 
TElemType Root(BiTree T);				// 求二叉树的根节点 
TElemType Value(BiTree p);				// 返回该节点的值 
void Assign(BiTree p,TElemType value);	// 给二叉树的节点赋值 
void PreOrderTraverseRec(BiTree T);		// 前序遍历递归版 
void PreOrderTraverse(BiTree T);		// 前序遍历非递归版 
void InOrderTraverseRec(BiTree T);		// 中序遍历递归版 
void InOrderTraverse(BiTree T);			// 中序遍历非递归版 
void PostOrderTraverseRec(BiTree T);	// 后序遍历递归版 
void PostOrderTraverse(BiTree T);		// 后序遍历非递归版 
void SeqTraverse(BiTree T);				// 层序遍历 
int CalcuWidth(BiTree T);				// 返回二叉树的最大宽度 
Status JudgeCBT(BiTree T);				// 判断是否为完全二叉树 


int main(int args, char * argv[])
{
	BiTree T;
	InitBiTree(&T);
	
	FILE *infile = fopen("in.txt","r");
	
	fp = fopen("out.txt","w");
	if(fp == NULL || infile == NULL)
	{
		(void) fprintf (stderr, "File open error!\n");//错误输出流 
		exit(EXIT_FAILURE);
	}
	
	String input;
	fprintf(stdout,"please input BinaryTree with Preorder:(Empty Node with #)\n");
	fscanf(infile,"%s", input);
	StrAssign(str,input);
	
	fprintf(stdout,"%s\n",input);
	fprintf(fp,"%s\n",input);
	
	CreateBiTree(&T);
	
	fprintf(stdout,"\nPreOrderTraverseRec:");
	fprintf(fp,"\nPreOrderTraverseRec:");
	PreOrderTraverseRec(T);
	
	fprintf(stdout,"\nPreOrderTraverse:");
	fprintf(fp,"\nPreOrderTraverse:");
	PreOrderTraverse(T);
	
	fprintf(stdout,"\nInOrderTraverseRec:");
	fprintf(fp,"\nInOrderTraverseRec:");
	InOrderTraverseRec(T);
	
	fprintf(stdout,"\nInOrderTraverse:");
	fprintf(fp,"\nInOrderTraverse:");
	InOrderTraverse(T);
	
	fprintf(stdout,"\nPostOrderTraverseRec:");
	fprintf(fp,"\nPostOrderTraverseRec:");
	PostOrderTraverseRec(T);
	
	fprintf(stdout,"\nPostOrderTraverse:");
	fprintf(fp,"\nPostOrderTraverse:");
	PostOrderTraverse(T);
	
	fprintf(stdout,"\nSeqTraverse:");
	fprintf(fp,"\nSeqTraverse:");
	SeqTraverse(T);
	
	fprintf(stdout,"\nCBT? %d(1:yes 0:no)\n",JudgeCBT(T)); 
	fprintf(fp,"\nCBT? %d(1:yes 0:no)\n",JudgeCBT(T)); 
	
	fprintf(stdout,"BiTree`s width:%d\n",CalcuWidth(T));
	fprintf(fp,"BiTree`s width:%d\n",CalcuWidth(T));

	DestroyBiTree(&T);
	
	fclose(fp);
	fclose(infile);
	
	return 0;
}



Status StrAssign(String T,char *chars)
{ 
	int i;
	if(strlen(chars) > MAXSIZE)
		return ERROR;
	else
	{
		T[0] = strlen(chars);
		for(i = 1;i <= T[0]; i ++ )
			T[i] = *(chars + i - 1);
		return OK;
	}
}

Status visit(TElemType e)
{
	printf("%c ",e);
	return OK;
}

/* 构造空二叉树T */
Status InitBiTree(BiTree *T)
{ 
	*T=NULL;
	return OK;
}

/* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */
void DestroyBiTree(BiTree *T)
{ 
	if(*T) /* 递归的销毁，类似于后序遍历 */ 
	{
		if((*T)->lchild) /* 有左孩子 */
			DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
		if((*T)->rchild) /* 有右孩子 */
			DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
		free(*T); /* 释放根结点 */
		*T = NULL; /* 空指针赋NULL */
	}
}

/* 按前序输入二叉树中结点的值（一个字符） */
/* #表示空树，构造二叉链表表示二叉树T。 */
void CreateBiTree(BiTree *T)
{ 
	TElemType ch;
	
	/* scanf("%c",&ch); */
	ch=str[treeIndex ++];

	if(ch == '#') 
		*T = NULL;
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if(!*T)
		{
			(void) fprintf (stderr, "Cannot allocate memory!\n");//错误输出流 
			exit(OVERFLOW);
		} 
			
		(*T)->data=ch; /* 生成根结点 */
		CreateBiTree(&(*T)->lchild); /* 构造左子树 */
		CreateBiTree(&(*T)->rchild); /* 构造右子树 */
	}
}

/* 初始条件: 二叉树T存在 */
/* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
Status BiTreeEmpty(BiTree T)
{ 
	if(T)
		return FALSE;
	else
		return TRUE;
}


/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int BiTreeDepth(BiTree T)
{
	int i, j;
	if(!T)
		return 0;
	if(T->lchild)
		i = BiTreeDepth(T->lchild);
	else
		i = 0;
	if(T->rchild)
		j = BiTreeDepth(T->rchild);
	else
		j = 0;
	return i > j ? i+1 : j+1;
}

/* 初始条件: 二叉树T存在。操作结果: 返回T的根 */
TElemType Root(BiTree T)
{ 
	if(BiTreeEmpty(T))
		return Nil;
	else
		return T->data;
}

/* 初始条件: 二叉树T存在，p指向T中某个结点 */
/* 操作结果: 返回p所指结点的值 */
TElemType Value(BiTree p)
{
	return p->data;
}

/* 给p所指结点赋值为value */
void Assign(BiTree p,TElemType value)
{
	p->data=value;
}

/* 前序递归遍历 */
void PreOrderTraverseRec(BiTree T)
{ 
	if(T == NULL)
		return;
	fprintf(stdout,"%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
	fprintf(fp,"%c",T->data);
	PreOrderTraverseRec(T->lchild); /* 再先序遍历左子树 */
	PreOrderTraverseRec(T->rchild); /* 最后先序遍历右子树 */
}

/* 前序非递归遍历 */
void PreOrderTraverse(BiTree T)
{
	Stack stk;
	stk.top = 0;
	
	while(T || stk.top)
	{
		if(T)
		{
			fprintf(stdout,"%c",T->data);// 先打印根节点 
			fprintf(fp,"%c",T->data);
			stk.s[++ stk.top] = T;// 入栈 
			T = T->lchild;//  递归左节点 
		}else
		{
			T = stk.s[stk.top --]; // 回溯 
			T = T->rchild; 		   // 递归右节点 
		}
	}
}

/* 中序递归遍历 */
void InOrderTraverseRec(BiTree T)
{ 
	if(T == NULL)
		return;
	InOrderTraverseRec(T->lchild); /* 中序遍历左子树 */
	fprintf(stdout,"%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
	fprintf(fp,"%c",T->data);
	InOrderTraverseRec(T->rchild); /* 最后中序遍历右子树 */
}
/* 中序非递归遍历 */
void InOrderTraverse(BiTree T)
{
	Stack stk;
	stk.top = 0;
	
	while(T || stk.top)
	{
		if(T)
		{
			stk.s[++ stk.top] = T; /* 入栈，递归左节点  */ 
			T = T->lchild;
		}else
		{
			T = stk.s[stk.top --]; /* 出栈，回溯，打印根节点 */ 
			fprintf(stdout,"%c",T->data);
			fprintf(fp,"%c",T->data);
			T = T->rchild;		   /* 递归右节点 */ 
		}
	}
}

/* 后序递归遍历 */
void PostOrderTraverseRec(BiTree T)
{
	if(T == NULL)
		return;
	PostOrderTraverseRec(T->lchild); /* 先后序遍历左子树  */
	PostOrderTraverseRec(T->rchild); /* 再后序遍历右子树  */
	fprintf(stdout,"%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
	fprintf(fp,"%c",T->data);
}

/* 后序非递归遍历 */
void PostOrderTraverse(BiTree T)
{
	Stack stk;
	stk.top = 0;

	BiTree right = NULL; /*上一次遍历到的右节点 */ 
	while(T || stk.top)
	{
		if(T)
		{
			stk.s[++ stk.top] = T; /* 不断向左递归 */ 
			T = T->lchild;
		}else
		{
			T = stk.s[stk.top];
			
			if(T->rchild && T->rchild != right) /* 向右 */ 
			{
				T = T->rchild;
			}else /* 左右都不行的话，回溯，打印当前结点 */ 
			{
				stk.top --;
				fprintf(stdout,"%c",T->data);
				fprintf(fp,"%c",T->data);
				right = T;
				T = NULL;/* 防止死循环 */ 
			}
		}
	}
}

/* 层序遍历 */ 
void SeqTraverse(BiTree T)
{
	Queue qu;
	qu.head = 1;
	qu.tail = 0;
	qu.q[++ qu.tail] = T;
	
	while(qu.head <= qu.tail) /* 打印队头的元素，再将队头的元素的左右儿子入队 */ 
	{
		int lenth = qu.tail - qu.head + 1;
		while(lenth --)
		{
			BiTree root = qu.q[qu.head ++];
			fprintf(stdout,"%c",root->data);
			fprintf(fp,"%c",root->data);
			if (root->lchild)
				qu.q[++ qu.tail] = root->lchild;
			if(root->rchild)
				qu.q[++ qu.tail] = root->rchild;
		}
	}
}

/* 宽度计算 */ 
int CalcuWidth(BiTree T)
{
	if(T == NULL) return 0;
	Queue qu;
	qu.head = 1;
	qu.tail = 0;
	qu.q[++ qu.tail] = T;
	int res = 0; 
	
	while(qu.head <= qu.tail) 
	{
		int lenth = qu.tail - qu.head + 1;//一行一行的取宽度最大值
		if(res < lenth) res = lenth;
		while(lenth --)
		{
			BiTree root = qu.q[qu.head ++];
			if (root->lchild)
				qu.q[++ qu.tail] = root->lchild;
			if(root->rchild)
				qu.q[++ qu.tail] = root->rchild;
		}
	}
	return res;
}
/* 判断是否为完全二叉树 */ 
Status JudgeCBT(BiTree T)
{
	if(T == NULL)
	{
		return TRUE;
	}
	
	Queue qu;
	qu.head = 1;
	qu.tail = 0;
	qu.q[++ qu.tail] = T;
	
	while(qu.head <= qu.tail) /* 打印队头的元素，再将队头的元素的左右儿子入队 */ 
	{
		BiTree root = qu.q[qu.head ++];
		
		if(root == NULL)
		{
			break;
		}

		qu.q[++ qu.tail] = root->lchild;
			
		qu.q[++ qu.tail] = root->rchild;
	}
	
	while(qu.head <= qu.tail)
	{
		if(qu.q[qu.head ++] != NULL)
		{
			return FALSE;
		}
	}
	return TRUE;
}

参考文献

程杰. 大话数据结构：溢彩加强版[M]. 北京: 清华大学出版社, 2020.

标签：遍历,qu,BiTree,fprintf,二叉树,数据结构,节点
From： https://www.cnblogs.com/Az1r/p/16795060.html

相关文章

  • 数据结构—线性表的定义和特点
          在日常生活中，线性表的例子比比皆是。例如，26个英文字母的字母表：(A，B，C，...，Z)是一个线性表，表中的数据元素是单个字母。在稍复杂的线性表中一个数据元素可以包含若......
  • 114. 二叉树展开为链表
    题目描述给你二叉树的根结点root，请你将它展开为一个单链表：展开后的单链表应该同样使用TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。展......
  • 二叉树（存储结构，三种遍历方式，构建树）——C语言描述
    二叉树（存储结构，三种遍历方式，构建树）——C语言描述目录二叉树（存储结构，三种遍历方式，构建树）——C语言描述0测试用例框架1定义2特殊二叉树3二叉树的性质4二叉树存储结构5......
  • 数据结构—第一章绪论习题
    1、简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。解答：    数据：是客观事物的符号表示，指所有能输入到计算机中并被......
  • 226. 翻转二叉树
    题目描述解题思路二叉树的题一般都有对应的模板，我们做题时可以参考对应模板二叉树解题的思维模式分两类：1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个trav......
  • 哈夫曼编码解码（数据结构实验）
    哈夫曼树定义定义：带权路径长度WPL最小的二叉树称作哈夫曼树，又叫最优二叉树节点的带权路径长度为：从该节点到树根之间的路径长度与节点上的权的乘积树的带权路径长度为：......
  • 617. 合并二叉树
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),left(......
  • 124.二叉树的最大路径和
    路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点......
  • 数据结构 玩转数据结构 3-1 栈和栈的应用：撤销操作和系统栈
    0课程地址https://coding.imooc.com/lesson/207.html#mid=13417 1重点关注1.1栈和数组对比相同点：都是线性结构不同点：栈只能从一端增删元素......
  • 数据结构—算法的时间复杂度
    1、什么是时间复杂度     一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99