【数据结构 C语言版】树，二叉树，线索二叉树，哈夫曼树

树的概念

根 如下图中，树形结构的 A。

子树 每个节点下又称为一棵子树，如 B 为 A 的子树。

在一棵树中，节点被定义为他的每一个 子树 根节点的前驱，而他每一个子树的根节点就是他的后继。

在描述属性树形结构时，人们往往使用家族称谓，如 把 A 称为 B 的双亲节点，B 称为 A 的孩子节点。拥有同一双亲的节点称为兄弟节点。每个结点的子树的所有节点成为子孙节点。

节点的度：节点所拥有的子树数目称为节点的度。如 A 的度为3。

树的度：树中各节点度的最大值。

叶子结点：无后继的的节点，即度为零的节点，也叫终端节点。

分支节点：度不为零的节点，也叫非终端节点。

节点的层数：从根开始，根节点为第一层，其孩子为第二层，依此类推。

树的深度：书中节点层数的最大值就是树的深度，也叫树的高度。

有序树：树中子树的顺序不能更换。

森林：多个不相交树的集合。

1二叉树

二叉树，即每一个节点上最多只有两颗子树。二叉树严格区分左，右子树，顺序不能更换，否则就是另一颗二叉树了。

所有关于树的名词术语对于二叉树都适用。

二叉树不是度为 2 的树，二叉树是每个节点的度至多为 2，可以只有一个子树。

满二叉树：深度为K，且有 (2的K次方) - 1 个节点的二叉树称为满二叉树。

完全二叉树：如果一颗具有n个节点，深度为 K 的二叉树，它的每一个节点斗鱼深度为 K 的满二叉树中编号 1~~n 的节点一一对应，则称其为完全二叉树。

 

二叉树的重要性质：

       1. 二叉树的第 i 层上至多有 2 的(i-1)次方个节点。

        2.深度为 h 的二叉树至多有 (2 的 h 次方) -1 个节点。

        3.对于任意一个二叉树，若其叶子结点数为 n。，度为 2 的节点数为 n₂ ，则  n。= n₂+1

        4.具有 n 个节点的完全二叉树的深度为 log₂( n+1) 或 (log₂n)+1

        5.若一颗有n个节点的完全二叉树的节点按层序，从左到右进行编号，则对编号为 i 的节点：

                ①若 i = 1，则节点是二叉树的根，无双亲结点；否则，i > 1，其双亲结点编号为 i /2。

                ②如果 2i > n, 则序号为 i 的节点无左孩子，否则，序号为 i 的节点的左孩子节点序号为                                 2i。

                ③如果 2i+1 > n, 则序号为 i 的节点无右孩子，否则，序号为 i 的节点的右孩子节点

                                序号为 2i+1。

1.1   二叉树的存储结构

二叉树的存储可采用顺序存储或链式存储。

1.1.1   顺序存储结构：采用一组地址连续的存储单元存储数据元素，为了在存储结构中反应节点的逻辑关系，必须按照一定的规律存放书中的节点。

对于完全二叉树，其节点可按照从上到下，从左到右的次序存储在一维数组中。

即将完全二叉树编号为 i 的节点数据存储在一维数组中下标 i - 1 的分量中。

对于非完全二叉树，为使得下标反应位置关系，将不存在节点用 NULL 补为完全二叉树。

但是，这对空间浪费极大。

1.1.2   链式存储结构

二叉树的链式存储结构就是用指针建立二叉树节点之间的关系。二叉树的每个节点至多有两个分支，分别指向节点的左子树和右子树，因此二叉树的结构体应有一个数值域，两个指针（二叉链存储结构），这样可以很容易找到孩子节点，如果还想很方便找的双亲结点，可在设置一个指向双亲的指针（三叉链存储结构）。

二叉链存储结构体

typedef struct Node
{
	DataType data;
	struct Node* lchild, * rchild;
}BiTNode,*BiTree;

1.2   二叉树的先序序列建立二叉树

查看每一个节点中数值

void Visit(DataType x)
{
	printf("%c", x);
}

递归的先序遍历二叉树：

        1.   访问根节点；

        2.   先序遍历左子树；

        3.   先序遍历右子树。

void PreOrder(BiTree root)
{	// 先序遍历
	if (root != NULL)
	{
		Visit(root->data);
		PreOrder(root->lchild);
		PreOrder(root->rchild);
	}
}

递归的中序遍历二叉树：

        1.   中序遍历左子树；

        2.   访问根节点；

        3.   中序遍历右子树。

void InOrder(BiTree root)
{	// 中序遍历
	if (root != NULL)
	{
		
		InOrder(root->lchild);
		Visit(root->data);
		InOrder(root->rchild);
	}
}

递归的后序遍历二叉树：

        1.   后序遍历左子树；

        2.   后序遍历右子树；

        3.   访问根节点。

void PostOrder(BiTree root)
{	// 后序遍历
	if (root != NULL)
	{
		PostOrder(root->lchild);
		PostOrder(root->rchild);
		Visit(root->data);
	}
}

先序序列创建二叉树，以扩展的先序序列作为输入数据，采用类似先序遍历的递归算法创建二叉树。如果是 “ # ” ，则当前树根置空；否则申请节点空间，存入节点数据，分别用当前的根节点的左右子树的指针进行递归调用，穿件左右子树。

void CrrateBiTree(BiTree* root)
{
	char ch;
	ch=getchar();
	if (ch == '#') *root = NULL;
	else
	{
		*root = (BiTree)malloc(sizeof(BiTNode));
		(*root)->data = ch;
		CrrateBiTree(&((*root)->lchild));
		CrrateBiTree(&((*root)->rchild));
	}

}

1.3   输出叶子结点

 输入二叉树，当二叉树不为空时，先遍历左子树，直到到达左子树的最底部（叶节点左右子树都为空），即叶子结点处，输出叶子结点处的数值，再递归遍历叶子结点的双亲结点的右子树，依次逐渐遍历到跟节点，随后同样的方法遍历右子树。

void InOnder(BiTree root)
{	// 输出叶子节点
	if (root)
	{
		InOnder(root->lchild);
		if (root->lchild == NULL && root->rchild == NULL)
		{
			printf("%c",root->data);
		}
		InOnder(root->rchild);
	}
}

1.4   叶节点数目

输入二叉树，当二叉树不为空时，先遍历左子树，直到到达左子树的叶子结点的双亲结点，双亲结点的左孩子是叶子结点时，nl + 1，双亲结点的右孩子是叶子结点时，nr + 1，之后 nl + nr 为 这个双亲结点的数值，其后返回到这个双亲结点的双亲结点。直到遍历完这个二叉树，得到所有叶子结点的个数。

int leaf(BiTree root)
{	// 叶结点数目
	int nl, nr;
	if (root == NULL) return 0;
	if (root->lchild == NULL && root->rchild == NULL) return 1;
	nl = leaf(root->lchild);
	nr = leaf(root->rchild);
	return nl + nr;
}

1.5   二叉树高度

输入二叉树，当二叉树不为空时，先遍历左子树，直到到达左子树的最底部，判断其左叶子结点与右叶子节点的高度，大者再加上左子树的根节点的 1 ，按照同样的方法遍历右子树，最后判断左子树的高度和右子树的高度，大者加上树的根节点数 1。

int TreeDepth(BiTree root)
{	// 二叉树高度
	int hl, hr, h;
	if (root == NULL) return 0;
	else
	{
		hl = TreeDepth(root->lchild);
		hr = TreeDepth(root->rchild);
		h = (hl > hr ? hl : hr) + 1;
		return h;
	}
}

1.6   按树的层打印树

横向打印二叉树

void PrintTree(BiTree root, int h)
{	// 打印树
	if (root == NULL) return;
	PrintTree(root->rchild, h + 3);
	for (int i = 0; i < h; i++) printf(" ");
	{
		printf("%c\n", root->data);
	}
	PrintTree(root->lchild, h + 3);
}

1.7   实现代码

# include<stdio.h>
# include<malloc.h>
typedef char DataType;
typedef struct Node
{
	DataType data;
	struct Node* lchild, * rchild;
}BiTNode,*BiTree;


void CrrateBiTree(BiTree* root)
{
	char ch;
	ch=getchar();
	if (ch == '#') *root = NULL;
	else
	{
		*root = (BiTree)malloc(sizeof(BiTNode));
		(*root)->data = ch;
		CrrateBiTree(&((*root)->lchild));
		CrrateBiTree(&((*root)->rchild));

	}

}


void Visit(DataType x)
{
	printf("%c", x);
}

void PreOrder(BiTree root)
{	// 先序遍历
	if (root != NULL)
	{
		Visit(root->data);
		PreOrder(root->lchild);
		PreOrder(root->rchild);
	}
}

void InOrder(BiTree root)
{	// 中序遍历
	if (root != NULL)
	{
		
		InOrder(root->lchild);
		Visit(root->data);
		InOrder(root->rchild);
	}
}

void PostOrder(BiTree root)
{	// 后序遍历
	if (root != NULL)
	{
		PostOrder(root->lchild);
		PostOrder(root->rchild);
		Visit(root->data);
	}
}


void InOnder(BiTree root)
{	// 输出叶子节点
	if (root)
	{
		InOnder(root->lchild);
		if (root->lchild == NULL && root->rchild == NULL)
		{
			printf("%c",root->data);
		}
		InOnder(root->rchild);
	}
}

int leaf(BiTree root)
{	// 叶结点数目
	int nl, nr;
	if (root == NULL) return 0;
	if (root->lchild == NULL && root->rchild == NULL) return 1;
	nl = leaf(root->lchild);
	nr = leaf(root->rchild);
	return nl + nr;
}

int TreeDepth(BiTree root)
{	// 二叉树高度
	int hl, hr, h;
	if (root == NULL) return 0;
	else
	{
		hl = TreeDepth(root->lchild);
		hr = TreeDepth(root->rchild);
		h = (hl > hr ? hl : hr) + 1;
		return h;
	}
}

void PrintTree(BiTree root, int h)
{	// 打印树
	if (root == NULL) return;
	PrintTree(root->rchild, h + 3);
	for (int i = 0; i < h; i++) printf(" ");
	{
		printf("%c\n", root->data);
	}
	PrintTree(root->lchild, h + 3);
}


int main() 
{
	BiTree tree;
	CrrateBiTree(&tree);
	printf("前序遍历: ");
	PreOrder(tree);
	printf("\n");
	printf("中序遍历: ");
	InOrder(tree);
	printf("\n");
	printf("后序遍历: ");
	PostOrder(tree);
	printf("\n");
	printf("输出叶子结点: ");
	InOnder(tree);
	printf("\n");
	printf("叶节点数目: %d\n", leaf(tree));
	printf("二叉树高度: %d\n", TreeDepth(tree));
	printf("纵向打印二叉树: \n");
	PrintTree(tree,1);

}

2   线索二叉树

遍历二叉树是以一定的规则将二叉树中的节点排列成一个线性序列，从而得到二叉树节点的先序，中序或后序序列。其实质是对一个非线性结构进行线性操作，使序列中的每一个节点都有了一个直接的前驱和后继。

现做如下规定：若节点有左孩子，则将其 lchild 指向左孩子，否则令 lchild 指向其前驱；若节点有右孩子， 则将其 rchild 指向左孩子，否则令 rchild 指向其后继。另外还需要增加两个标志域来区别当前指针所指对象是指向孩子还是指向前驱或后继（指向孩子标志域为 0 ，指向前驱或后继标志域为 1 。）

以中序线索二叉树为例：

 线索二叉树的结构体

typedef char DataType;
typedef struct Node
{
	DataType data;
	struct Node* lchild, * rchild;
	int ltag, rtag;

}ThreadNode, * ThreadTree;

3   哈夫曼树

曼哈顿树又称最优树，是一类带权路径长度最短的树。利用曼哈顿树可以构造最优编码，用于信息传递，数据压缩等。

基础概念：

        路径：从树的一个节点到另一个节点之间的分支序列构成这两个节点的路径。

        路径长度：路径上分支的条数叫做路径长度。

        树的路径长度：从树的根到达每一个节点的路径长度。

        节点的权：树节点被赋予的有意义数值。

        节点的带权路径长度：树的每一个路径长度与其权值的乘积。

        树的带权路径长度：节点的带权路径之和。

哈夫曼树就是带权路径长度的二叉树。

3.1   哈夫曼树的构造

 1.   构造过程

        1.根据给定的 n 个权值，构造 n 颗只有根节点的二叉树，这 n 颗二叉树构成一个森林 F(森林是多个树的集合)。

        2.在森林 F 中选取两颗根节点权值最小的数作为左右子树创造一个新的二叉树，新的二叉树权值为左右子树权值之和。

        3.在森林 F 中删除 2 中使用的两棵树，并加入新构造的树。

        4.重复 2 3，直到 F 只含一棵树为止。这就是哈夫曼树。

 

 2.   算法实现

有 n 个叶子节点的哈夫曼树中没有度唯一的节点，所以 哈夫曼树的节点数为 2n-1。

使用一个 2n-1 的一维数组即可。采用静态三叉链来存储哈夫曼树。

哈夫曼树结构体

typedef struct
{
	int weight;
	int parent;
	int lchild;
	int rchild;

} HTNode;