二叉树的性质

在这里插入图片描述
性质1：
二叉树的第 i 层上至多有 2^i-1个结点（i >= 1）

性质2：
深度为k的二叉树至多有2^k-1个结点（k >= 1）

性质3：
对于任何一颗二叉树T，如果其叶子数为n₀，度为2的结点数为n₂，则n₀ = n₂ + 1

两种特殊形式的二叉树

满二叉树

定义：
一棵深度为k且有2^k-1个结点的二叉树称为满二叉树

在这里插入图片描述
如图是深度为4且有15个结点的二叉树

特点：

每一层上的结点数都是最大结点数(即每层都满)
叶子结点全部在最底层

对满二叉树结点位置进行编号

编号规则：从根结点开始，自上而下，自左而右
每一结点位置都有元素

完全二叉树

定义：
深度为k的具有n个结点的二叉树，当且仅当其中每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树
在这里插入图片描述
Ps:在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树

完全二叉树的性质

性质4：
具有n个结点的完全二叉树的深度为「log2ⁿ」+ 1¹

性质5：
如果对一棵有n个结点的完全二叉树(深度为「log2ⁿ」+ 1)的结点按层序编号(从第1层到第「log2ⁿ」+ 1层，每层从左到右)，则对任一结点i(1 ≤ i ≤ n),有：

在这里插入图片描述

二叉树的性质和存储结构

在这里插入图片描述

二叉树的顺序存储

实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素

//二叉树顺序存储表示
#define MAXSIZE 100
Typedef TElemType SqBiTree[MAXSIZE];		//bt —— Binary Tree
SqBiTree bt;

在这里插入图片描述

【例】二叉树结点数值采用顺序存储结构，如图所示。画出二叉树表示

二叉树的顺序存储缺点：

最坏情况：深度为k的且只有k个结点的单支树需要长度为2^k-1的一维数组（造成空间浪费）
在这里插入图片描述
特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树

二叉树的链式存储

二叉树结点的特点：
在这里插入图片描述

二叉树链表存储结构

typedef struct BiNode{
	TElemType data;
	struct BiBode *lchild, *rchild;	//左右孩子指针
}BiNode,  *BiTree;	// *BiTree指向结点的指针

在这里插入图片描述

在 n 个结点的二叉链表中，有 n+1 个空指针域

*三叉链表

在这里插入图片描述

typedef struct TriTNode{
	TelemType data;
	struct TriTNode *lchild, *parent, *rchild;
}TriTNode, *TriTree;

遍历二叉树

定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次（又称周游）
遍历目的——得到树中所有结点的一个线性排列
遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提；是二叉树一切运算的核心

根结点（D）左子树（L）右子树（R）
若规定先左后右，则只有三种情况：
DLR——先序遍历
LDR——中序遍历
LRD——后序遍历
在这里插入图片描述

例：

DLR(先序遍历)遍历顺序：ABELDHMIJ
LDR(中序遍历)遍历顺序：ELBAMHIDJ
LRD(后序遍历)遍历顺序：LEBMIHJDA

例：

根据遍历序列确定二叉树

若二叉树中各结点的值均不同，则二叉树结点的先序序列、中序序列和后序序列都是唯一的
由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一的二叉树

例：已知二叉树的先序和中序序列，构造出相应的二叉树

分析：由先序序列确定根；由中序序列确定左右子树

1、由先序知根为A，则由中序知左子树为CDBFE，右子树为IHGJ
2、再分别在左、右子树的序列中找出根、左子树序列、右子树序列
3、以此类推，直到得到二叉树
在这里插入图片描述

例：已知中序和后序序列求二叉树

在这里插入图片描述

二叉树遍历算法

先序遍历算法(DLR):
在这里插入图片描述

Status PreOrderTraverse(BiTree T){
	if(T == NULL)	//空二叉树
		return OK;
	else{
		visit(T); //访问根结点
		PreOrderTraverse(T -> lchild);	//递归遍历左子树
		PreOrderTraverse(T -> rchild);	//递归遍历右子树
	}
}

void Pre(BiTree *T){
	if(T != NULL){
		cout << T-> data;
		pre(T -> lchild);
		pre(T -> rchild);
	}
}

在这里插入图片描述
中序遍历算法(LDR)：

Status InOrderTraverse(BiTree T){
	if(T == NULL)	//空二叉树
		return OK;
	else{
		InOrderTraverse(T -> lchild);	///递归遍历左子树
		visit(T);	//访问根结点
		InOrderTraverse(T -> rchild);	///递归遍历右子树
	}
}

后序遍历算法(LRD)：

Status PostOrderTraverse(BiTree T){
	if(T == NULL)	//空二叉树
		return OK;
	else{
		PostOrderTraverse(T -> lchild);	///递归遍历左子树
		PostOrderTraverse(T -> rchild);	///递归遍历右子树
		visit(T);	//访问根结点
	}
}

遍历算法分析：
在这里插入图片描述
时间效率：O(n) 每个结点只访问一次
空间效率：O(n) 栈占用的最大辅助空间

中序遍历非递归算法

二叉树中序遍历的非递归算法的关键：
在中序遍历过某结点的整个左子树后，如何找到该结点的根以及右子树

基本思想：

建立一个栈
根结点进栈，遍历左子树
根结点出栈，输出根结点，遍历右子树

Status InOrderTraverse(BiTree){
	BiTree p;
	q = new BiTNode;
	InitStack(S);
	p =T;
	while(p || !StackEmpty(S)){
		if(p){
			Push(S, p);
			p = p -> lchild;	
		}
		else{
			Pop(S, q);
			cout << q -> data;
			p = q -> rchild; 	
		}
	}
	return OK;
}

二叉树的层次遍历

在这里插入图片描述
层次遍历结果：abfcdgeh

对于一个二叉树，从根结点开始，按从上到下、从左到右的顺序访问每一个结点，每个结点仅访问一次

算法设计思路：使用一个队列

将根结点入队；
队不空时循环：从队列中出列一个结点 *p，访问它；
1）若它有左孩子结点，将左孩子结点入队；
2）若它有右孩子结点，将右孩子结点入队

使用队列类型定义：

typedef struct{
	BTNode data[MaxSize];	//存放队中元素
	int front, rear;	//队头和队尾指针
}SqQueue;		//顺序循环队列类型

void LevelOrder(BTNode *b){
	BTNode *p;
	SqQueue *q;
	InitQueue(q);		//初始化队列
	enQueue(q, b);		//根结点指针进入队列
	while(!QueueEmpty(q)){		//队不为空，则循环
		deQueue(q, p);		//出队结点p
		cout << p -> data;		//访问结点p
		if(p -> lchild != NULL)
			enQueue(q, p -> lchild);	//有左孩子时将其入队
		if(p -> rchile != NULL)
			enQueue(q, p-> rchild);	//有右孩子时将其入队
	}
}

按先序遍历序列建立二叉树的二叉链表

在这里插入图片描述

为了保证得到想要的二叉树，我们为二叉树补充空结点：

在这里插入图片描述
根据补充空结点的位置不一样，我们构造出来的二叉树就不一样了

在这里插入图片描述

Status CreateBiTree(BiTree &T){
	cin >> ch;
	if(ch == "#")		//用"#"代表空结点
		T= NULL;
	else{
		if(!(T = new BiTNode);	
			exit(OVERFLOW);
		T -> data = ch;	//生成根结点
		CreateBiTree(T -> lchild);	//构造左子树
		CreateBiTree(T -> rchild);	//构造右子树
	}
	return OK;
} //CreateBiTree

复制二叉树

复制二叉树：

如果是空树，递归结束
否则，申请新结点空间，复制根结点
递归复制左子树
递归复制右子树

int Copy(BiTree T, BiTree &NewT){
	if(T == NULL){		//如果是空树返回0
		NewT = NULL;
		return 0;	
	}
	else{
		NewT = new BiTNode;
		NewT -> data = T -> data;
		Copy(T -> lChild, NewT -> lchild);
		Copy(T -> rChild, NewT -> rchild);
	}
}

计算二叉树深度

计算二叉树深度：

如果是空树，则深度为0；
否则，递归计算左子树的深度记为m，递归计算右子树的深度为n，二叉树的深度则为m与n的较大者加1

int Depth(BiTree T){
	if(T == NULL)		//如果是空树返回0
		return 0;
	else{
		m = Depth(T -> lChild);
		n = Depth(T -> rChild);
		if(m > n)
			return (m + 1);
		else
			return (n + 1);
	}
}

计算二叉树结点总数

计算二叉树结点总数：

如果是空树，则结点个数为0；
否则，结点个数为左子树的结点个数 + 右子树的结点个数再 + 1

int NodeCount(BiTree T){
	if(T == NULL)
		return 0;
	else
		return NodeCount(T -> lchild) + 
		NodeCount(T -> rchild) + 1;
}

补充：计算二叉树叶子结点数

计算二叉树叶子结点数：

如果是空树，则叶子结点个数为0
否则，为左子树的叶子结点个数 + 右子树的叶子结点个数

int LeafCount(BiTree T){
	if(T == NULL)		//如果是空树返回0
		return 0;
	if(T -> lchild == NULL && T -> rchild == NULL)	//如果是叶子结点返回1
		return 1;
	else
		return LeafCount(T -> lchild) + LeafCount(T -> rchild);
}

线索二叉树(Threaded Binary Tree)

利用二叉链表中的空指针域：
如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；
如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继
——这种改变指向的指针称为“线索”
在这里插入图片描述
为区分lchild和rchild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域ltag和rtag，并约定：

//结点结构
typedef struct BiThrNode{
	int data;
	int ltag, rtag;
	struct BiThrNode *lchild, *rchild;
}BiThrNode, *BiThrTree;

例：在这里插入图片描述

练习：

「x」：称作x的底，表示不大于x的最大整数「log2ⁿ」+ 1 ↩︎

原文链接：https://blog.csdn.net/Labrador_Katie/article/details/122614304

数据结构——树和二叉树

树和二叉树

二叉树的性质

两种特殊形式的二叉树

满二叉树

完全二叉树

完全二叉树的性质

二叉树的性质和存储结构

二叉树的顺序存储

二叉树的链式存储

*三叉链表

遍历二叉树

根据遍历序列确定二叉树

二叉树遍历算法

中序遍历非递归算法

二叉树的层次遍历

按先序遍历序列建立二叉树的二叉链表

复制二叉树

计算二叉树深度

计算二叉树结点总数

补充：计算二叉树叶子结点数

线索二叉树(Threaded Binary Tree)