【数据结构与算法】树与二叉树

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】树与二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构与算法】树与二叉树

一.树

1.树的定义

除了之前我们讲的栈、队列、链表等线性结构,数据结构中还有着一对多的非线性结构———
树是有n个结点组成的有限集,当n=0时为空树,在任意一颗非空树中,有且仅有一个特定的根结点 ;当n>1时,其余结点又可以分为一棵树,称为根的子树
如下图所示:
【数据结构与算法】树与二叉树
A为整棵树的根节点,分别以B、C为根节点能组成两颗子树:
【数据结构与算法】树与二叉树

2.结点的分类与关系

结点拥有的子树个数称为结点的度,一颗树结点为各个结点度的最大值。度为0的结点称为叶结点或者终端结点
一棵树中结点之间的关系,结点的子树的根结点称为该结点的孩子,所以该结点称为孩子结点的双亲结点。同一个双亲的孩子结点之间称为兄弟结点

3.树的相关概念

结点的层次就是从何根开始定义为第一层,根的孩子为第二层以此类推。树中结点的最大层次称为树的深度或者高度
森林是指由多颗互不相交的树的集合。

4.树的表示方法

树常使用双亲表示法:

typedef int DataType;
struct Node
{
 struct Node* firstChild1;    // 第一个孩子结点
 struct Node* pNextBrother;   // 指向其下一个兄弟结点
 DataType data;               // 结点中的数据域
};

二.二叉树

1.二叉树的定义

二叉树是度为2的树,二叉树的子树有左右之分所以二叉树是有序树

2.特殊二叉树

  1. 斜树顾名思义,斜树一定是斜的:所有结点都只有左子树的二叉树叫做左斜树,所有结点都只有右子树的二叉树叫做右斜树。这两者统称为斜树。
  2. 满二叉树:在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子结点又在同一层上,这样的二叉树叫做满二叉树
  3. 完全二叉树,假设完全二叉树的有K层则此二叉树在前K-1层为满二叉树并且在第K层至少有一个结点,在第K层从左到右连续。

3.二叉树的性质

  1. 在二叉树的第k层至多有2^(k-1)个结点。
  2. 深度为k的二叉树至多有2^k-1个结点。
  3. 对于任何一棵二叉树,叶子结点数为n0,度为2的结点数为n2,则有n0=n2+1
  4. 具有n个结点的完全二叉树的深度为log以2为底n的对数加1
  5. 具有n个结点的二叉树具有n-1个边。

4.二叉树的顺序结构

二叉树的顺序结构就是使用一维数组存储二叉树的结点,但是只适合储存完全二叉树,也就是前面讲过的堆,所以这里不过多赘述,想了解的点击链接[堆和堆排序]。(http://t.csdn.cn/Sgjar)

5.二叉树的链式结构

现在我们来看下二叉树真正适合的存储结构-----链式结构。

(1)链式结构的创建

一个结点可以存储一个数据元素,以及左孩子、右孩子。

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;//存储一个数据元素
	struct BinaryTreeNode* left;//指向左孩子
	struct BinaryTreeNode* right;//指向右孩子
}BTNode;
(2)结点的创建

我们编写一个用来创建结点存储数据的函数,并将左右孩子初始化为空。

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;

}
(3)二叉树的手动构建

我们使用创建结点函数手动构建出一个二叉树便于验证后续函数代码的正确:

BTNode* CreatTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);


	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node2->right = node7;

	return node1;
}

【数据结构与算法】树与二叉树

(4)前中后序遍历

前中后序遍历的区别即是根结点如何访问的问题,eg:前序遍历:先访问根结点再访问左孩子最后右孩子。

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);

}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}
(5)二叉树结点个数

二叉树链式存储结构函数的编写多使用递归的方式,这里我们需要求得结点的个数只需要将左树的结点加上右树的再加1即可

int TreeSize(BTNode* root)
{
	return root == NULL ? 0 :
		TreeSize(root->left)
		+ TreeSize(root->right)
		+ 1;
}
(6)二叉树的高度

二叉树的高度为树中结点的最大层次,比较左子树和右子树高度的较大值再加一个即可,需要注意的是需要记录左右子树的高度,不然递归的效率将会大大降低。

int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
(7)第k层的结点个数

利用分治递归的思想,想要求第k层的结点个数,只要分别求左右树第k-1层的结点个数并相加即可。


int TreeKLevel(BTNode* root, int k)
{
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	int leftKLevel = TreeKLevel(root->left, k - 1);
	int rightKLevel = TreeKLevel(root->right, k - 1);

	return leftKLevel + rightKLevel;
}
(8)查找二叉树中为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data == x)
		return root;

	BTNode* left = BinaryTreeFind(root->left, x);
	if (left)
		return left;

	BTNode* right = BinaryTreeFind(root->right, x);
	if (right)
		return right;

	return NULL;

}
(9)层序遍历

层序遍历即是将每一层都访问后,继续访问下一层,显然之前学习的队列非常适合实现这一操作:其中重要的是将队列原先存储的元素改为二叉树的结点指针类型


typedef struct BinaryTreeNode* QDataType;///****

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;


void QueueInit(Queue* pt);
void QueueDestroy(Queue* pt);

void QueuePush(Queue* pt, QDataType x);
void QueuePop(Queue* pt);
bool QueueEmpty(Queue* pt);
QDataType QueueFront(Queue* pt);

void QueueInit(Queue* pt)
{
	assert(pt);

	pt->head = pt->tail = NULL;
	pt->size = 0;
}

void QueueDestroy(Queue* pt)
{
	assert(pt);
	QNode* cur = pt->head;

	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pt->head = pt->tail = NULL;
	pt->size = 0;
}


void QueuePush(Queue* pt, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->next = NULL;
	newnode->data = x;

	if (pt->head == NULL)
	{
		assert(pt->tail == NULL);
		pt->head = pt->tail = newnode;
	}
	else
	{
		pt->tail->next = newnode;
		pt->tail = newnode;
	}

	pt->size++;

}


void QueuePop(Queue* pt)
{
	assert(pt);
	assert(pt->head != NULL);

	if (pt->head->next == NULL)
	{
		free(pt->head);
		pt->head = pt->tail = NULL;
	}
	else
	{
		QNode* next = pt->head->next;

		free(pt->head);
		pt->head = next;
	}
	pt->size--;
}
bool QueueEmpty(Queue* pt)
{
	assert(pt);
	
	return pt->size == 0;
}

QDataType QueueFront(Queue* pt)
{
	assert(pt);
	assert(!QueueEmpty(pt));

	return pt->head->data;
}

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%d ", front->data);

		if (front->left)
			QueuePush(&q, front->left);

		if (front->right)
			QueuePush(&q, front->right);

	}



	QueueDestroy(&q);
}
(10)判断是否为完全二叉树

我们想要判断二叉树是否为完全二叉树,就要了解完全二叉树的特点:完全二叉树在前k-1层是满二叉树,在第k层的非空结点从左到右也是连续的。思路已有,代码实现:

bool BinaryTreeComplete(BTNode* root)
{
	Queue eth;
	QueueInit(&eth);

	if (root)
		QueuePush(&eth, root);

	while (!QueueEmpty(&eth))
	{
		BTNode* front = QueueFront(&eth);
		QueuePop(&eth);

		if (front == NULL)
			break;
		else
		{
			QueuePush(&eth, front->left);
			QueuePush(&eth, front->right);
		}
	}

	while (!QueueEmpty(&eth))
	{
		BTNode* front = QueueFront(&eth);
		QueuePop(&eth);

		if (front)
		{
			QueueDestroy(&eth);
			return false;
		}
	}

	return true;
}

(11)销毁二叉树

销毁二叉树我们依旧使用递归实现,需要注意的是在调用销毁函数后,需要在函数体外手动置空。文章来源地址https://www.toymoban.com/news/detail-407708.html

void TreeDestroy(BTNode* root)//外部手动置空
{
	if (root == NULL)
		return;

	TreeDestroy(root->left);
	TreeDestroy(root->right);

	free(root);

}

到了这里,关于【数据结构与算法】树与二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】树与二叉树

    树是一种 非线性的数据结构 ,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 。它具有以下的特点: 有一个特殊的结点,称为根结点,根结点没有前驱结点 除根结点外,其余结点被分

    2024年02月11日
    浏览(45)
  • [数据结构] 树与二叉树

    树是由 (n(n geq 0)) 个节点组成的有限集。当 (n = 0) 时,称为空树。 任意一棵非空树应满足以下两点: (1)有且仅有一个特定的称为根的节点; (2)当 (n 1) 时,其余节点可分为 (m(m0)) 个互不相交的有限集 (T_1, T_2, dots, T_m) ,其中每个集合本身又是一棵树,称为根的

    2024年03月09日
    浏览(41)
  • 数据结构--树与二叉树

    树的定义 树是n(n =0)个节点的有限集。当n=0 时,称为空树 在任意一棵非空树中应满足 有且仅有一个特定的称为根的结点 当n1 时,其余节点可分为m(m0) 个互不相交的有限集T1,T2……Tm,其中每个集合本身又是一棵树,并且称为根的子树 树是一种逻辑结构,也是一种分层结构 树的

    2024年02月22日
    浏览(44)
  • 数据结构:图文详解 树与二叉树(树与二叉树的概念和性质,存储,遍历)

    目录 一.树的概念 二.树中重要的概念 三.二叉树的概念 满二叉树 完全二叉树 四.二叉树的性质 五.二叉树的存储 六.二叉树的遍历 前序遍历 中序遍历  后序遍历  树是一种 非线性数据结构 ,它由节点和边组成。树的每个节点可以有零个或多个子节点,其中一个节点被指定为

    2024年02月04日
    浏览(49)
  • 【数据结构】树与二叉树(中)

    目录 前言: 一、顺序存储结构: 二、堆: 1.堆的性质: 2.堆的性质: 3.堆的实现: Ⅰ.堆的初始化:  Ⅱ.堆的插入(含向上调整):  Ⅲ.堆的删除(含向下调整算法): Ⅳ.取堆顶的数据: Ⅴ.堆中的数据个数: Ⅵ.堆的判空:  Ⅶ.堆的销毁: 总结:         上篇文章中,

    2024年02月16日
    浏览(46)
  • 数据结构_树与二叉树

    目录 1. 树的基本概念 1.1 树的定义 1.2 基本术语 1.3 树的性质 1.4 相关练习 2. 二叉树的概念 2.1 二叉树的概念及其主要特性 2.2 二叉树的存储结构 2.2.1 顺序存储结构 2.2.2 链式存储结构 2.3 相关练习 3. 二叉树的遍历和线索二叉树 3.1 二叉树的遍历 3.1.1 先序遍历 3.1.2 中序遍历 3.1

    2024年02月04日
    浏览(46)
  • 【数据结构】24王道考研笔记——树与二叉树

    树是n个结点的有限集合,n=0时,称为空树。非空树满足: 除了根节点外,任何一个结点都有且仅有一个前驱 结点的层次(深度):从上往下数 结点的高度:从下往上数 树的高度(深度):总共有多少层 结点的度:有几个孩子(分支) 树的度:各节点的度的最大值 森林:

    2024年02月13日
    浏览(50)
  • 数据结构--》解锁数据结构中树与二叉树的奥秘(一)

            数据结构中的树与二叉树,是在建立非线性数据结构方面极为重要的两个概念。它们不仅能够模拟出生活中各种实际问题的复杂关系,还常被用于实现搜索、排序、查找等算法,甚至成为一些大型软件和系统中的基础设施。         无论你是初学者还是进阶者

    2024年02月08日
    浏览(46)
  • 数据结构--》解锁数据结构中树与二叉树的奥秘(二)

            数据结构中的树与二叉树,是在建立非线性数据结构方面极为重要的两个概念。它们不仅能够模拟出生活中各种实际问题的复杂关系,还常被用于实现搜索、排序、查找等算法,甚至成为一些大型软件和系统中的基础设施。         无论你是初学者还是进阶者,

    2024年02月08日
    浏览(43)
  • 【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历)

    树与二叉树知识点文章: 【数据结构】树与二叉树(递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方法) 二叉树遍历算法的应用: 【数据结构】树与二叉树遍历算法的应用(求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、

    2024年04月13日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包