编辑

4、二叉树（Binary Tree）

一、什么是树

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必为log2n+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：二分查找 （前提：数组连续且有序） 动态查找：集合中记录时动态变化的，除查找外还可能发生插入和删除

上一页3、队列（Queue）下一页5、二叉搜索树与平衡二叉树（BST & AVL）

最后更新于

这有帮助吗？