数据结构——树和二叉树

树和二叉树

二叉树的性质两种特殊形式的二叉树

满二叉树完全二叉树完全二叉树的性质 二叉树的性质和存储结构

二叉树的顺序存储二叉树的链式存储*三叉链表 遍历二叉树

根据遍历序列确定二叉树二叉树遍历算法中序遍历非递归算法二叉树的层次遍历按先序遍历序列建立二叉树的二叉链表复制二叉树计算二叉树深度计算二叉树结点总数补充：计算二叉树叶子结点数 线索二叉树(Threaded Binary Tree)

二叉树的性质

性质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;

 
例：


 
练习：

---

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