当前位置:   article > 正文

数据结构(5)—— 树(上)_一棵树中,某结点位置上方各层中的所有结点都是该结点的祖先。

一棵树中,某结点位置上方各层中的所有结点都是该结点的祖先。

1. 什么是树

查找(Searching):根据某个给定关键字K,从集合R中找出关键字与K相同的记录

静态查找:集合中记录是固定的

  • 没有插入和删除操作,只有查找 动态查找:集合中记录是动态变化的
  • 除查找,还可能发生插入和删除

顺序查找:O(n) 二分查找:O(logn)

  • 假设n个数据元素的关键字满足有序(比如:小→大)k1<k2<…<kn,并且是连续存放(数组),那么可以进行二分查找

树(Tree):n(n≥0)个结点构成的有限集合,当n=0时称为空树。

对于任一颗非空树(n>0),它具备以下性质:

  • 树中有一个称为根(Root)的特殊结点,用r表示;
  • 其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,称为原来树的子树(SubTree)

树与非树?

  • 子树是不相交的;
  • 除了根节点外,每个结点有且仅有一个父节点;
  • 一颗N个结点的树有N-1条边;

树的一些基本术语

  1. 结点的度(Degree):结点的子树个数
  2. 树的度:树的所有结点中最大的度数
  3. 叶结点(Leaf):度为0的结点
  4. 父结点(Parent):有子树的结点是其子树的根节点的父结点
  5. 子节点(Child):若A结点是B结点的父结点,则称B结点是A结点的子节点;子节点也称孩子结点;
  6. 兄弟结点(Sibling):具有同一父结点的各结点彼此是兄弟结点;
  7. 路径和路径长度:从结点n1到nk的路径为一个结点序列n1,n2,…,nk,ni是ni+1的父结点。路径所包含边的个数为路径的长度;
  8. 祖先节点(Ancestor):沿树根到某一结点路径上的所有结点都是这个节点的祖先节点;
  9. 子孙节点(Descendant):某一结点的子树中的所有结点是这个节点的子孙;
  10. 节点层次(Level):规定根节点在1层,其他任一结点的层数是其父结点的层数加1;
  11. 树的深度(Depth):树中所有结点中的最大层次是这棵树的深度

树的表示

在这里插入图片描述

2. 二叉树的定义

二叉树T:一个有穷的结点集合。这个集合可以为空;若不为空,则它是由根节点和称为其左子树 T L T_L TL和右子树 T R T_R TR的两个不相交的二叉树组成。

二叉树的具体5种形态:
在这里插入图片描述
二叉树的子树有左右顺序之分:
在这里插入图片描述

(1)特殊二叉树

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

(2)二叉树的几个重要性质

  • 一个二叉树第i层的最大节点数为: 2 i − 1 , i ≥ 1 2^{i-1},i≥1 2i1i1
  • 深度为k的二叉树有最大结点总数为: 2 k − 1 , k ≥ 1 2^k-1,k≥1 2k1k1
  • 对任何非空二叉树T,若n0表示叶结点的个数、n2是度为2的非叶结点个数,那么两者满足关系n0=n2+1
    在这里插入图片描述

(3)二叉树的抽象数据类型定义

  • 数据类型:二叉树
  • 数据对象集合:一个有穷的结点集合。若不为空,则由根结点和其左、右二叉子树组成。
  • 操作集:BT∈BinTree,Item∈ElementType,重要操作有:
    1. Boolean IsEmpty(BinTree BT):判别BT是否为空
    2. void Traversal(BinTree BT):遍历,按某顺序访问每个结点
    3. BinTree CreatBinTree():创建一个二叉树

二叉树常用的遍历方法:

  • void PreOrderTraversal(BinTree BT):先序——根、左子树、右子树
  • void InOrderTraversal(BinTree BT):中序——左子树、根、右子树
  • void PostOrderTraversal(BinTree BT):后序——左子树、右子树、根
  • void LevelOrderTraversal(BinTree BT):层次遍历——从上到下、从左到右

3. 二叉树及存储结构

(1)顺序存储结构

  • 完全二叉树:按从上到下、从左到右顺序存储n个结点的完全二叉树的结点父子关系:
    在这里插入图片描述
    • 非根节点(序号i>1)的父结点序号为int(i/2)
    • 结点(序号为i)的左孩子结点的序号是2i,(若2i<=n,否则没有左孩子)
    • 结点(序号为i)的右孩子结点的序号是2i+1,(若2i+1<=n,否则没有右孩子)
      在这里插入图片描述

(2)链表存储

在这里插入图片描述
在这里插入图片描述

typedef struct TreeNode *BinTree;
typedef BinTree Positioon;

struct TreeNode{
	ElementType Data;
	BinTree Left;
	BinTree Right;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

4. 二叉树的遍历

(1)递归遍历

先序遍历

遍历过程为:

  • ①访问根节点
  • ②先序遍历其左子树
  • ③先序遍历其右子树

采用递归实现

void PreOrderTraversal(BinTree BT)
{
	if(BT)
	{
		printf("%d",BT->Data);
		PreOrderTraversal(BT->Left);
		PreOrderTraversal(BT->Right);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

在这里插入图片描述
A(BDFE)(CGHI)

中序遍历

遍历过程为:

  • ①中序遍历其左子树
  • ②访问根结点
  • ③中序遍历其右子树
void InOrderTraversal(BinTree BT)
{
	if(BT)
	{
		InOrderTraversal(BT->Left);
		printf("%d",BT->Data);
		InOrderTraversal(BT->Right);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

在这里插入图片描述

后续遍历

遍历过程为:

  • ①后序遍历其左子树
  • ②后序遍历其右子树
  • ③访问根结点
void PostOrderTraversal(BinTree BT)
{
	if(BT)
	{
		PostOrderTraversal(BT->Left);
		PostOrderTraversal(BT->Right);
		print("%d",BT->Data);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

在这里插入图片描述
(DEFB)(HGCI)A

前序、中序和后序遍历过程:遍历过程中经过结点的路线一样,只是访问各结点的时机不同。

在这里插入图片描述

(2)非递归遍历

非递归算法实现的基本思路:使用堆栈

中序遍历非递归遍历算法:

  • 遇到一个结点,就把它压栈,并去遍历它的左子树;
  • 当左子树遍历结束后,从栈顶弹出这个结点并访问它;
  • 然后按其右指针再去中序遍历该结点的右子树
void InOrderTraversal(BinTree BT)
{
	BinTree T = BT;
	Stack S = CreatStack(MaxSize); /* 创建并初始化堆栈s */
	while(T || !IsEmpty(S))
	{
		while(T) /* 一直向左并将沿途结点压入堆栈 */
		{
			Push(S,T);
			T = T->Left;
		}
		if(!IsEmpty(S))
		{
			T = Pop(S);	/* 结点弹出堆栈 */
			printf("%5d",T->Data); /* (访问)打印结点 */
			T = T->Right; /* 转向右子树 */
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

先序遍历非递归遍历算法:

void InOrderTraversal(BinTree BT)
{
	BinTree T = BT;
	Stack S = CreatStack(MaxSize); /* 创建并初始化堆栈s */
	while(T || !IsEmpty(S))
	{
		while(T) /* 一直向左并将沿途结点压入堆栈 */
		{
			printf("%5d",T->Data); /* (访问)打印结点 */
			Push(S,T);
			T = T->Left;
		}
		if(!IsEmpty(S))
		{
			T = Pop(S);	/* 结点弹出堆栈 */
			T = T->Right; /* 转向右子树 */
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

(3)层序遍历

二叉树遍历的核心问题:二维结构的线性化

  • 从结点访问其左、右儿子结点,需要一个存储结构保存暂时不访问的结点,存储结构:堆栈、队列
队列实现

遍历从根节点开始,首先将根结点入队,然后开始执行循环:结点出队、访问该结点、其左右儿子入队

在这里插入图片描述
ABCDFGIEH

层序基本过程:先根节点入队,然后:

  • ① 从队列中取出一个元素
  • ② 访问该元素所指结点
  • ③ 若该元素所指结点的左、右孩子结点非空,则将其左、右孩子的指针顺序入队。
void LevelOrderTraversal(BinTree BT)
{
	Queue Q;
	BinTree T;

	if(!BT) return; /* 若是空树,则直接返回 */
	Q = CreatQueue(MaxSize); /* 创建并初始化队列Q */
	AddQ(Q,BT);
	while(!IsEmptyQ(Q))
	{
		T = DeleteQ(Q);
		printf("%d\n",T->Data); /* 访问取出队列的结点 */
		if(T->Left) AddQ(Q,T->Left);
		if(T->Right) AddQ(Q,T->Right);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

遍历二叉树的应用

在这里插入图片描述
在这里插入图片描述

通过改造后序遍历

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200714205137753.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ1NTU4MQ==,size_16,color_FFFFFF,t_70

在这里插入图片描述
在这里插入图片描述

先序和中序遍历序列来确定一棵二叉树
分析:

  • 根据先序遍历序列第一个结点确定根结点
  • 根据根结点在中序遍历序列中分割出左右两个子序列
  • 对左子树和右子树分别递归使用相同的方法继续分解

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/747804
推荐阅读
相关标签
  

闽ICP备14008679号