banner
cos

cos

愿热情永存,愿热爱不灭,愿生活无憾
github
tg_channel
bilibili

数据结构学习笔记<4> 二叉树

一、什么是树#

1. 树的定义#

树(Tree):n(n≥0)个结点构成的有限集合。
当 n=0 时,称为空树
对于任一棵非空树(n>0), 它具备以下性质:

  1. 树中有一个称为 “根(Root)” 的特殊结点,用 r 表示
  2. 其余结点可分为 m(m>0)个互不相交的有限集 T1,T2,……,Tm, 其中每个集合本身又是一棵树,称为原来树的 “子树(SubTree)”。
  3. 子树是不相交
  4. 除了根结点外,每个结点有且仅有一个父结点;
  5. 一个N 个结点的树有N-1 条边

2. 树的一些基本术语#

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): 树中所有结点的最大层次是这棵树的深度。
12. 森林: m 棵不相交的树的集合

二、树的表示#

1. 儿子 - 兄弟表示法#

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

三、二叉树#

1. 定义#

二叉树 T: 一个有穷的结点集合。
这个结点可以为空
若不为空,则它是由根结点和称为其左子树 TL右子树 TR的两个不相交的二叉树组成
二叉树具体五种基本形态 a 空树 b 只有一个结点 c 有一个结点和左子树 d 有一个结点和左子树 e 有一个结点和左右子树
在这里插入图片描述
PS:二叉树的子树有左右顺序之分

几种特殊二叉树
在这里插入图片描述
二叉树的抽象数据类型定义
类型名称:二叉树
数据对象集:一个有穷的结点集合。
若不为空,则由根结点和其左、右二叉子树组成。
操作集: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); //层次遍历,从上到下、从左到右

2. 二叉树的几个重要性质#

  • 一个二叉树第 i 层的最大节点数2^i-1^,i≥1。
  • 深度为 k的二叉树有最大结点总数2^k^-1,k≥1。
  • 对任何非空二叉树 T,若 n0 表示叶结点的个数、n2 是度为 2 的非叶结点个数,那么两者满足关系 n0=n2+1。
  • 具有n 个结点的完全二叉树深度 k必为log~2~n+1

3. 二叉树的存储结构#

1、顺序存储结构#

完全二叉树:按从上至下、从左到右顺序存储n个结点的完全二叉树的结点父子关系

  • 非根结点(序号 i > 1)的父结点的序号是 [i / 2] ;(向下取整)
  • 结点(序号为 i)的左孩子的序号是 2i(2i ≤ n,否则没有左孩子)
  • 结点(序号为 i)的右孩子的序号是 2i+1(2i + 1 ≤ n,否则没有右孩子)

一般二叉树也可采用这种顺序存储结构,但是会造成空间浪费

满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树,区别于完全二叉树在这里插入图片描述

2、链式存储#

(1) 定义#
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode {
		ElementType Data;
		BinTree Left;
		BinTree Right;
}
(2) 遍历(递归实现)#
先序遍历:

1. 先访问根结点;
2. 先序遍历其左子树;
3. 先序遍历其右子树。

void PreOrderTraversal(BinTree BT) {
	if(BT) {
		printf("%d", BT->Data);
		PreOrderTraversal( BT->Left);
		PreOrderTraversal( BT->Right);
	}
}
中序遍历:

1. 中序遍历其左子树
2. 访问根结点
3. 中序遍历其右子树。

void InOrderTraversal(BinTree BT) {
	if(BT) {
		InOrderTraversal( BT->Left);
		printf("%d", BT->Data);
		InOrderTraversal( BT->Right);
	}
}
后序遍历:

1. 后序遍历其左子树
2. 后序遍历其右子树。
3. 访问根结点

void PostOrderTraversal(BinTree BT) {
	if(BT) {
		PostOrderTraversal( BT->Left);
		PostOrderTraversal( BT->Right);
		printf("%d", BT->Data);
	}
}
(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. 若该元素所指结点的左、右孩子结点非空,将其左、右孩子的指针顺序入队
void LevelOrderTraversal(BinTree BT) {
	Queue Q;  BinTreee T;
	if ( !BT ) return;	//若是空树直接返回
	Q = CreateQueue(MaxSize);//创建并初始化队列Q
	AddQ(Q, BT);
	while( !IsEmpty(Q) ) {
		T = DeleteQ(Q);
		printf("%d\n", T->Data);//访问结点
		if(T->Left) AddQ(Q, T->Left);//将左孩子放入队列
		if(T->Right) AddQ(Q, T->Right);//将右孩子放入队列
	}
}

补充知识
数据管理的基本操作之查找:根据某个给定关键字 K,从集合 R 中找出关键字与 K 相同的记录,分为静态查找与动态查找
静态查找:集合中记录是固定的,没有插入和删除操作,只有查找。
法 1:顺序查找 (哨兵概念:在数组的边界上设一个值,碰到哨兵循环就可以结束了,可以少一个分支判断)复杂度 O (n);
法 2:二分查找 (前提:数组连续且有序)
动态查找:集合中记录时动态变化的,除查找外还可能发生插入和删除

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。