数据结构与算法之树

树是一种非线性结构，有一个前驱，可能有多个后继（1:n）的数据结构

树的基本知识

树的定义

由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，···，Tm。每个集合本身又是棵树，被称作这个根的子树

若干术语

根：即根结点(没有前驱)
叶子：即终端结点(没有后继)
森林：指m棵不相交的树的集合(例如删除A后的子树个数)
有序树：结点各子树从左至右有序，不能互换（左为第一）
无序树：结点各子树可互换位置
双亲：即上层的那个结点(直接前驱) parent
孩子：即下层结点的子树 (直接后继) child
兄弟：同一双亲下的同层结点（孩子之间互称兄弟）sibling
堂兄弟：即双亲位于同一层的结点（但并非同一双亲）cousin
祖先：即从根到该结点所经分支的所有结点
子孙：即该结点下层子树中的任一结点
结点：即树的数据元素
结点的度：结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）
结点的层次：从根到该结点的层数（根结点算第一层）
终端结点：即度为0的结点，即叶子
分支结点：除树根以外的结点（也称为内部结点）
树的度：所有结点度中的最大值（Max{各结点的度}）
树的深度(或高度)：指所有结点中最大的层数（Max{各结点的层次}）

树的表示法有几种

图形表示法
嵌套集合表示法
广义表表示法
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
根作为由子树森林组成的表的名字写在表的左边
目录表示法
左孩子－右兄弟表示法

逻辑结构

(特点)：一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交

存储结构

树是非线性结构，该怎样存储？
仍然有顺序存储、链式存储等方式
树的顺序存储方案应该怎样制定？
可规定为：从上至下、从左至右将树的结点依次存入内存
重大缺陷：复原困难（不能唯一复原就没有实用价值）
树的链式存储方案应该怎样制定？
可用多重链表：一个前趋指针，n个后继指针。
细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？
缺点：等长结构太浪费（每个结点的度不一定相同）;不等长结构太复杂（要定义好多种结构类型）
计算机如何实现各种不同进制的运算？
实现思路：先研究最简单、最有规律的二进制运算规律，然后设法把各种不同进制的运算转化二进制运算
树的存储可否借鉴这种思路呢？
解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为这种简单的树

树的运算

普通树（即多叉树）若不转化为二叉树，则运算很难实现
二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上

二叉树

二叉树的结构最简单，规律性最强
可以证明，所有树都能转为唯一对应的二叉树，不失一般性（利用左孩子－右兄弟表示法）

二叉树的定义

定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成

逻辑结构：一对二（1：2）

基本特征:

每个结点最多只有两棵子树（不存在度大于2的结点）
左子树和右子树次序不能颠倒（有序树）

二叉树的性质

性质1: 在二叉树的第i层上至多有2^i-1个结点（i>0）
性质2：深度为k的二叉树至多有2^k-1个结点（k>0）
性质3：对于任何一棵二叉树，若2度的结点数有n₂个，则叶子数（n₀）必定为n₂＋1 （即n₀=n₂+1）
满二叉树：一棵深度为k 且有2^k-1个结点的二叉树。（特点：每层都“充满”了结点）
完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应(完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。这其实是顺序二叉树的含义)
满二叉树和完全二叉树在顺序存储方式下可以复原
性质4：具有n个结点的完全二叉树的深度必为log₂n＋1
对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

二叉树的存储结构

顺序存储结构：
按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储

链式存储结构：
一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始）
二叉树结点数据类型定义：

typedef struct node *tree_pointer;
typedef struct node {
    int data;
    tree_pointer left_child, right_child;
} node;

二叉链表

typedef struct BiNode
{
	int data;
	struct BiNode  *lchild, *rchild;
}BiNode, *BiTree;

三叉链表

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

双亲链表

typedef struct BPTNode
{
	int data;
	int parentPosition; //指向双亲的指针 //数组下标
	char LRTag; //左右孩子标志域
}BPTNode;

typedef struct BPTree
{
	BPTNode nodes[100]; //因为节点之间是分散的，需要把节点存储到数组中
	int num_node;  //节点数目
	int root; //根结点的位置 //注意此域存储的是父亲节点在数组的下标
}BPTree;

定义一颗简单的树

void main()
{
	BPTree tree;

	BiNode t1, t2, t3, t4, t5;

	memset(&t1, 0, sizeof(BiNode));
	memset(&t2, 0, sizeof(BiNode));
	memset(&t3, 0, sizeof(BiNode));
	memset(&t4, 0, sizeof(BiNode));
	memset(&t5, 0, sizeof(BiNode));

	t1.data = 1;
	t2.data = 2;
	t3.data = 3;
	t4.data = 4;
	t5.data = 5;

	//建立树关系
	//t1的左孩子为t2
	t1.lchild = &t2;
	//t1的右孩子为t3
	t1.rchild = &t3;
	//t2的左孩子为t4
	t2.lchild = &t4;
	//t3的左孩子为t5
	t3.lchild = &t5;

	system("pause");
}

使用指针去定义树

void main()
{
	BiTree p1, p2, p3, p4, p5;

	p1 = (BiTree)malloc(sizeof(BiNode));
	p2 = (BiTree)malloc(sizeof(BiNode));
	p3 = (BiTree)malloc(sizeof(BiNode));
	p4 = (BiTree)malloc(sizeof(BiNode));
	p5 = (BiTree)malloc(sizeof(BiNode));

	memset(p1, 0, sizeof(BiNode));
	memset(p2, 0, sizeof(BiNode));
	memset(p3, 0, sizeof(BiNode));
	memset(p4, 0, sizeof(BiNode));
	memset(p5, 0, sizeof(BiNode));

	p1->data = 1;
	p2->data = 2;
	p3->data = 3;
	p4->data = 4;
	p5->data = 5;

	//建立树关系
	//t1的左孩子为t2
	p1->lchild = p2;
	//t1的右孩子为t3
	p1->rchild = p3;
	//t2的左孩子为t4
	p2->lchild = p4;
	//t3的左孩子为t5
	p3->lchild = p5;

	system("pause");
}

遍历二叉树和线索二叉树

遍历二叉树

遍历定义：指按某条搜索路线遍访每个结点且不重复（又称周游）
遍历用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心
遍历方法：牢记一种约定，对每个结点的查看都是“先左后右”

遍历规则：
二叉树由根、左子树、右子树构成，定义为D、L、R
D、L、R的组合定义了六种可能的遍历方案：LDR, LRD, DLR, DRL, RDL, RLD

若限定先左后右，则有三种实现方案：

DLR 先(根)序遍历
LDR 中(根)序遍历
LRD 后(根)序遍历

DLR—先序遍历，即先根再左再右
LDR—中序遍历，即先左再根再右
LRD—后序遍历，即先左再右再根

e.g.
( A ( B ( D , E ), C ) )
先序遍历的结果是：A B D E C
中序遍历的结果是：D B E A C
后序遍历的结果是：D E B C A
( A ( B ( C ( D , E ) ) , F ( G ( H ) ) ) )
先序遍历：ABCDEFGH
中序遍历：BDCEAFHG
后序遍历：DECBHGFA

e.g.(用二叉树表示算术表达式)

先序遍历 -> + * * / A B C D E -> 前缀表示法
中序遍历 -> A / B * C * D + E -> 中缀表示法
后序遍历 -> A B / C * D * E + -> 后缀表示法
层序遍历 -> + * E * D / C A B

遍历的算法实现：

//结点数据类型自定义
typedef struct node{
   int  data; 
   struct node *lchild,*rchild；
} NODE;
NODE *root;

先序遍历算法

DLR(NODE *root )
{ 
    if (root) //非空二叉树
    {
        printf(“%d”,root->data); //访问D
        DLR(root->lchild); //递归遍历左子树
        DLR(root->rchild); //递归遍历右子树
    }
}

中序遍历算法

LDR(NODE *root)
{
    if(root !=NULL)
    {
        LDR(root->lchild);
        printf(“%d”,root->data);
        LDR(root->rchild);
    }
}

后序遍历算法

LRD (NODE *root)
{
    if(root !=NULL)
    {
        LRD(root->lchild);
        LRD(root->rchild);
        printf(“%d”,root->data);
    }
}

除去打印条件，其结构是一样的
这里的差别在于：
先序遍历在第一次访问时候输出
中序遍历在第二次访问时候输出
后序遍历在第三次访问时候输出

e.g.(二叉树中叶子结点的数目)

//使用全局变量sum
DLR_CountLeafNum(NODE *root)
{
    if (root)  //非空二叉树条件，还可写成if(root!=NULL)
    {
        if(!root->lchild && !root->rchild)//是叶子结点则统计并打印，在先中后打印并无区别
        {
            sum++;
            printf("%d\n",root->data);
        }
        DLR_CountLeafNum(root->lchild); //递归遍历左子树，直到叶子处；
        DLR_CountLeafNum(root->rchild);//递归遍历右子树，直到叶子处；
    }
    return 0;
}

DLR_CountLeafNum(NODE *root, int *num)
{
    if (root != NULL)
    {
        if(!root->lchild && !root->rchild)
        {
            sum++;
            printf("%d\n",root->data);
        }
        DLR_CountLeafNum(root->lchild, num); //递归遍历左子树，直到叶子处；
        DLR_CountLeafNum(root->rchild, num);//递归遍历右子树，直到叶子处；
    }
    return 0;
}

e.g.(二叉树的深度)

int GetDepth(BiNode *root)
{
	int depthleft = 0, depthright = 0; 
	int depthVal = 0;
	int tmp = 0;

	if (root == NULL)
	{
		depthVal = 0;
		return depthVal;
	}
	//求左子树高度
	depthleft = GetDepth(root->lchild);
	//求右子树高度
	depthright = GetDepth(root->rchild);

	tmp = ((depthleft>depthright)? depthleft : depthright);
	depthVal = 1 + tmp; 

	return depthVal;
}

e.g.(树的拷贝)

BiNode *copyTree(BiNode *T)
{
	BiNode *newLptr = NULL, *newRptr = NULL;
	BiNode *newNode = NULL;

	if (T->lchild != NULL)
	{
		newLptr =copyTree(T->lchild);
	}
	else
	{
		newLptr = NULL;
	}

	if (T->rchild != NULL)
	{
		newRptr = copyTree(T->rchild);
	}
	else
	{
		newRptr = NULL; 
	}

	newNode = (BiNode *)malloc(sizeof(BiNode));
	if (newNode == NULL)
	{
		return NULL;
	}

	newNode->lchild = newLptr;
	newNode->rchild = newRptr;
	newNode->data = T->data;

	return newNode;
}

中序遍历非递归算法:

步骤1：结点的所有路径情况
如果结点有左子树，该结点入栈；
如果结点没有左子树，访问该结点；

如果结点有右子树，重复步骤1；

如果结点没有右子树（结点访问完毕），回退，让栈顶元素出栈，访问栈顶元素，并访问右子树，重复步骤1

如果栈为空，表示遍历结束。

注意：入栈的结点表示，本身没有被访问过，同时右子树也没有被访问过。

#include <iostream>
#include <stack>
using namespace std;

//二叉链表
typedef struct BiNode
{
	int data;
	struct BiNode  *lchild, *rchild;
}BiNode, *BiTree;

BiNode *GoFarLeft(BiNode *T, stack<BiNode *> &s)
{
	if (T == NULL)
	{
		return NULL;
	}
	while (T->lchild)
	{
		s.push(T);
		T = T->lchild;
	}
	return T;
}
void InOrder(BiNode *T)
{
	 stack<BiNode *> s;
	 //步骤1：一直往左走，找到中序遍历的起点
	 BiTree t = GoFarLeft(T, s);
	 while (t)
	 {
		 printf("%d ", t->data); //中序遍历打印
		 //如果t节点有右子树，那么重复步骤1
		 if (t->rchild != NULL)
		 {
			t =  GoFarLeft(t->rchild, s);
		 }
		 //如果t没有右子树，根据栈顶指示，访问栈顶元素
		 else if (!s.empty())
		 {
			 t = s.top();
			 s.pop();
		 }
		 //如果t没有右子树，并且栈为空 
		 else
		 {
			 t = NULL;
		 }
	 }
}
void main()
{
	BiNode t1, t2, t3, t4, t5;
	memset(&t1, 0, sizeof(BiNode));
	memset(&t2, 0, sizeof(BiNode));
	memset(&t3, 0, sizeof(BiNode));
	memset(&t4, 0, sizeof(BiNode));
	memset(&t5, 0, sizeof(BiNode));
	t1.data = 1;
	t2.data = 2;
	t3.data = 3;
	t4.data = 4;
	t5.data = 5;
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;
	InOrder(&t1);
	system("pause");
}

二叉树内存释放

void BiTree_Free(BiTNode* T)
{
	BiTNode *tmp = NULL;
	if (T != NULL)
	{
		if (T->rchild != NULL)
        {
            BiTree_Free(T->rchild);
        }
		if (T->lchild != NULL)
        {
            BiTree_Free(T->lchild);
        }
		if (T != NULL)
		{
			free(T); 
			T = NULL;
		}
	}
}

先序遍历创建树，需要有占位符：124#35#

//按给定的先序序列建立二叉链表
BiTNode* BiTree_Creat()
{
	BiTNode *tmp = NULL;
	char ch;
	printf("\n请输入字符: ");
	scanf("%c", &ch);
	if (ch == '#')
	{
		return NULL;
	}
	else
	{
		tmp = (BiTNode *)malloc(sizeof(BiTNode));
		if (tmp == NULL)
		{
			return NULL;
		}
		tmp->data = ch; //生成根结点
		tmp->lchild = BiTree_Creat();//构建左子树
		tmp->rchild = BiTree_Creat();//构建右子数
		return tmp;
	}
}

根据先序和中序遍历结果可以得到原树
e.g.
先序结果：ADEBCF
中序结果：DEACFB
分析方法：

先从先序遍历中找到根节点A，然后根据A在中序遍历中的位置，区分出A的左子树和A的右子树
在A的左（右）子树中，找到左（右）子树的根节点（在先序中），重复上述步骤

分析：

由于先序从根节点开始，故A为根节点，再根据中序结果，DE为左节点，CFB为右节点。
由于在先序和中序中，DE顺序一样，故D为E的父节点，E为D的右节点
由先序结果，右节点为B，而中序结果中B位于最后，故得到B没有右节点
由于在先序和中序中，DE顺序一样，则可得出C为B的左节点，F为C的右节点

线索二叉树

普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得
若可将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了

规定：

若结点有左子树，则lchild指向其左孩子；否则， lchild指向其直接前驱(即线索)
若结点有右子树，则rchild指向其右孩子；否则， rchild指向其直接后继(即线索)

lchild

LTag

data

RTag

rchild

约定:

当Tag域为0时,表示正常情况
当Tag域为1时,表示线索情况

在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继

线索链表：用上面结点结构所构成的二叉链表
线索：指向结点前驱和后继的指针
线索二叉树：加上线索的二叉树(图形式样)
线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程

二叉树线索化算法

void InTreading(BiThrTree p) 
//中序遍历进行中序线索化
{
    if (p)
    {
        InThreading(p->lchild); /*左子树线索化*/
        if (!p->lchild) /*前驱线索*/
        {
            p->ltag=1;
            p->lchild=pre;
        }
        if (!pre->rchild) /*后继线索*/
        {
            pre->rtag=1;
            pre->rchild=p;
        }
        pre=p;
        InThreading(p->rchild); /*右子树线索化*/
    }
}

二叉树线索化遍历算法:(非递归，且不用栈)

p = T->lchild; //从头结点进入到根结点；
while(p != T)
{
    while(p->LTag == link)
        p = p->lchild; //先找到中序遍历起点
    if(!visit(p->data))
        return ERROR; //若起点值为空则出错告警
    while(p->RTag == Thread ……)
    {
        p = p->rchild;
        Visit(p->data);
    } //若有后继标志，则直接提取p->rchild中线索并访问后继结点；
    p = p->rchild; //当前结点右域不空或已经找好了后继，则一律从结点的右子树开始重复{  }的全部过程。
}
return OK;

线索化过程就是在遍历过程中修改空指针的过程：
将空的lchild改为结点的直接前驱；
将空的rchild改为结点的直接后继。
非空指针仍然指向孩子结点
e.g.

#include <string.h>
#include <stdio.h>  
#include <stdlib.h>   
#include <io.h>  
#include <math.h>  
#include <time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag;    /* Link==0表示指向左右孩子指针, */
                                        /* Thread==1表示指向前驱或后继的线索 */
typedef  struct BiThrNode    /* 二叉线索存储结点结构 */
{
    TElemType data;    /* 结点数据 */
    struct BiThrNode *lchild, *rchild;    /* 左右孩子指针 */
    PointerTag LTag;
    PointerTag RTag;        /* 左右标志 */
} BiThrNode, *BiThrTree;

TElemType Nil='#'; /* 字符型以空格符为空 */

Status visit(TElemType e)
{
    printf("%c ",e);
    return OK;
}

/* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
/* 0(整型)/空格(字符型)表示空结点 */
Status CreateBiThrTree(BiThrTree *T)
{ 
    TElemType h;
    scanf("%c",&h);

    if(h==Nil)
        *T=NULL;
    else
    {
        *T=(BiThrTree)malloc(sizeof(BiThrNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data=h; /* 生成根结点(前序) */
        CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
        if((*T)->lchild) /* 有左孩子 */
            (*T)->LTag=Link;
        CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
        if((*T)->rchild) /* 有右孩子 */
            (*T)->RTag=Link;
    }
    return OK;
}

BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{ 
    if(p)
    {
        InThreading(p->lchild); /* 递归左子树线索化 */
        if(!p->lchild) /* 没有左孩子 */
        {
            p->LTag=Thread; /* 前驱线索 */            p->lchild=pre; /* 左孩子指针指向前驱 */
        }
        if(!pre->rchild) /* 前驱没有右孩子 */
        {
            pre->RTag=Thread; /* 后继线索 */
            pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
        }
        pre=p; /* 保持pre指向p的前驱 */
        InThreading(p->rchild); /* 递归右子树线索化 */
    }
}

/* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ 
    *Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
    if(!*Thrt)
        exit(OVERFLOW);
    (*Thrt)->LTag=Link; /* 建头结点 */
    (*Thrt)->RTag=Thread;
    (*Thrt)->rchild=(*Thrt); /* 右指针回指 */
    if(!T) /* 若二叉树空,则左指针回指 */
        (*Thrt)->lchild=*Thrt;
    else
    {
        (*Thrt)->lchild=T;
        pre=(*Thrt);
        InThreading(T); /* 中序遍历进行中序线索化 */
        pre->rchild=*Thrt;
        pre->RTag=Thread; /* 最后一个结点线索化 */
        (*Thrt)->rchild=pre;
    }
    return OK;
}

/* 中序遍历二叉线索树T(头结点)的非递归算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{ 
    BiThrTree p;
    p=T->lchild; /* p指向根结点 */
    while(p!=T)
    { /* 空树或遍历结束时,p==T */
        while(p->LTag==Link)
            p=p->lchild;
        if(!visit(p->data)) /* 访问其左子树为空的结点 */
            return ERROR;
        while(p->RTag==Thread&&p->rchild!=T)
        {
            p=p->rchild;
            visit(p->data); /* 访问后继结点 */
        }
        p=p->rchild;
    }
    return OK;
}

int main()
{
    BiThrTree H,T;
    printf("请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')\n");
     CreateBiThrTree(&T); /* 按前序产生二叉树 */
    InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
    printf("中序遍历(输出)二叉线索树:\n");
    InOrderTraverse_Thr(H); /* 中序遍历(输出)二叉线索树 */
    printf("\n");
    system("pause");
    return 0;
}

树和森林

树和森林的存储方式

双亲表示法
孩子表示法
孩子兄弟表示法

树和森林与二叉树的转换

树如何转为二叉树
方法：加线—擦线—旋转
step1: 将树中同一结点的兄弟相连;
step2: 保留结点的最左孩子连线，删除其它孩子连线；
step3: 将同一孩子的连线绕左孩子旋转45度角
二叉树怎样还原为树：
把所有右孩子变为兄弟
森林如何转为二叉树：
- ①各森林先各自转为二叉树；
  ②依次连到前一个二叉树的右子树上
- 森林直接变兄弟，再转为二叉树
二叉树如何还原为森林
即B={root, LB, RB} ==> F={T1, T2, …,Tm}
把最右边的子树变为森林，其余右子树变为兄弟

一般树的遍历

深度遍历(先序、中序、后序)
广度遍历(层次)

先序遍历

访问根结点；
依次先序遍历根结点的每棵子树

后序遍历

依次后序遍历根结点的每棵子树；
访问根结点

树没有中序遍历(因子树不分左右)

霍夫曼树

对于文本”BADCADFEED”的传输而言，因为重复出现的只有
”ABCDEF”这6个字符，因此可以用下面的方式编码:

接收方可以根据每3个bit进行一次字符解码的方式还原文本信息。
这样的编码方式需要30个bit位才能表示10个字符
当需要传送的数据量很大时，采用新的编码方式

准则：任一字符的编码都不是另一个字符编码的前缀！