二叉树

树

树的定义：树是n（n>0）个结点的有穷集合。

（1） 有且仅有一个称为根的结点；

（2） 其余结点分为m（m>=0）个互不相交的非空集合T1，T2…Tm，这些集合中的每

一个都是一棵树，称为根的子树。

在树上，根结点没有直接前趋。

树形结构的术语及其含义：

（1） 度：树上任一结点所拥有的子树的数目称为该结点的度。

（2） 叶子或终端结点：度为0的结点。

（3） 非终端结点或分支点：度大于0的结点。

（4） 树的度：一棵树中所有结点的度的最大值。

（5） 双亲或父结点：若树中结点A是结点B的直发前趋，则A是B的双亲或父结点。

（6） 孩子或子结点：B为A的孩子或子结点。

（7） 兄弟：父结点相同的结点互称为兄弟。

（8） 子孙：一棵树上的任何结点（不包括根结点）称为根的子孙。

（9） 祖先：若B是A的子孙则A是B的祖先。

（10） 结点的层数：从根结点开始算起，根的层数为1，其余结点的层数为其双亲的层数

加1。

（11） 树的高度或深度：一棵树中所有结点层数的最大值。

二叉树

二叉树的定义：二叉树结点的有有穷集合，它或者是空集，或者同时满足下述两个条件：

（1） 有且仅有一个称为根的结点；

（2） 其余结点分为两个互不相交的集合T1、T2，T1与T2都是二叉树，并且T1与T2

有顺序关系（T1在T2之前），它们分别称为根的左子树和右子树。

二叉树与树的区别：

（1） 二叉树可以是空集，这种二叉树称为空二叉树。

（2） 二叉树的任一结点都有两棵子树，并且这两棵子树之间有顺序关系，位置不能交换。

（3） 二叉树上任一结点的度定义为该结点的孩子数。

二叉树有五种基本形态：

[UPLOAD=jpg]../upload_pic/2006042123183344.jpg[/UPLOAD]

满二叉树：深度为k(k>=1)且有 -1个结点的二叉树。满二叉树上各层的结点数已达到了

二叉树可以容纳的最大值。

完全二叉树：如果在一棵深度为k(k>=1)的满二叉树上删去第k层上最右边的连续

j(0<=j< )个结点，就得到一棵深度为k的完全正确二叉树。

二叉树的性质：

（1） 二叉树第i（i>=1）层上至多有 个结点。

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

（3） 对任何二叉树，若2度结点数为 ，则叶子数 = +1。

（4） 具有n个结点的完全二叉树的深度为 。

（5） 如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点

X有：

<1>若i=1，则结点X是根，若i>1则X的双亲PARENT(X)的编号为 。

<2>若2i>n，则结点X无左孩子（且无右孩子）；否则，X的左孩子LCHILD(X)的编号为

2i。

<3>若2i+1>n，则结点X无右孩子；否则，X的右孩子RCHILD(X)的编号为2i+1。

二叉树有两种存储结构：顺序存储结构和链式存储结构。

链式存储结构的二叉树称为二叉链表。如下：

Lchild Data Rchild

Data域：称为数据域，用于存储二叉树结点中的数据元素；

lchild域：称为左孩子指针域，用于存放指向本结点左孩子的指针（左指针）。Rchild域也

相同。

根指针：每个二叉链表还必须有一个指向根结点的指针，该指针称为根指针。根指针具有

标识二叉链表的作用，对二叉链表的访问只能从根指针开始。

注意：二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的

一个孩子的指针，或者是空指针NULL。

定义如下：

程序代码

typedef struct btnode *bitreptr;

Struct btnode {

datatype data;

bitreptr lchild, rchild;

}

bitreptr root;

若二叉树为空，则root=NULL。

顺序存储结构由一个一维数组构成。

存储策略：对于任何完全二叉树来说，可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。在这一存储结构中，由于一结点的存储位置（下标）也就是它的编号，故结点间的逻辑关系可通过它们下标间的数值关系确定。如：在bt中找结点F的左孩子，根据二叉树性质5，从F的下标值5可以算出其左孩子的下标值为10（2*5）。右孩子的下标值为11（2*5+1）。

由于二叉树的性质5对非完全二叉树一般不成立，因此在计算非完全二叉树结点的下标值时，首先必须将其转化为完全二叉树，可以在“残缺”位置上增设“虚结点”。各个“虚结点”在数组中用一个特殊记号“∧”表示。比较浪费空间。

二叉树的遍历：就是按某种次序系统地“访问”二叉树上的所有结点，使每个结点恰好被“访问”一次。并保证只被“访问”一次。

先根遍历：

（1） 访问根结点；

（2） 先根遍历左子树；

（3） 先根遍历右子树；

中根遍历：

（1） 中根遍历左子树；

（2） 访问根结点；

（3） 中根遍历右子树；

后根遍历：

（1） 后根遍历左子树；

（2） 后根遍历右子树；

（3） 访问根结点；

树的存储结构：

（1） 孩子链表表示法：树上的一个结点的内容（数据元素）以及指向该结点所有孩子的指针存储在一起以便于运算的实现。一个孩子链表是一个带头结点的单链表，单链表的头结点含两个域：数据域和指针域。其中，数据域用于存储结点X中的数据元素；指针域用于存放指向该单链表中第一个表结点（首结点）的指针。为了检索方便，所有头结点组织成一个数组，称为表头数组。

（2） 孩子兄弟链表表示法：包含三个域：数据域—用于存储树上结点中的数据元素；孩子域—用于存放指向本结点第一个孩子的指针；兄弟域—用于存放指向本结点下一个兄弟的指针。孩子兄弟链表的结构形式与二叉链表完全相同；但存储结点中指针的含义不同。二叉链表中存储结点的左、右指针分别指向左、右孩子；而孩子兄弟链表中存储结点的两个指针分别指向“长子”和“大弟”。

（3） 双亲表示法：树上每个结点的孩子可以有任意多个，但双新只有一个。通过指向双亲的指针而将树中所有结点组织在一起形成一种存储结构是十分简洁的。在双亲表示法下，每个存储结点由两个域组成：数据域—用于存储树上结点中的数据元素；指针域—用于指示本结点的双亲所在的存储结点。孩子结点的下标值大于其双亲结点的下标值，“弟”结点的下标值大于“兄”结点的下标值。于是若要查找任一下标值为i的结点X的子孙，只需在下标值大于i的结点中去查找。

遍历方法：

先根遍历：

（1） 访问根结点；

（2） 依次先根遍历根的各个子树T1，…，Tm；

后根遍历：

（1） 依次后根遍历根的各个子树T1，…，Tm；

（2） 访问根结点。

层次遍历：

（1） 若树非空，访问根结点；

（2） 若第1，…，i(i>=1)层结点已被访问，且第i+1层结点尚未访问，则从左到右依次访问第i+1层结点。

树(Tree)是n(n≥O)个结点的有限集。在一棵非空树中：

◇有且只有一个特定的称为根(Root)的结点。

◇当n>1时，其余结点可分为m(m>O)个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树(Subtree)。

树的定义也是一种递归定义。

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为O的结点称为叶子结点或终端结点。度不为O的结点称为非终端结点

或分支结点。除根结点外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。树中结点最大层次称为树的深度(Depth)或高度。

如果树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。

森林(Forest)是m(m≥O)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

例1（1998年中国科学院软件研究所）若一个具有N个顶点，K条边的无向图是一个森林（N>K），则该森林中必有______棵树。

A．K B．N C．N-K D．1

【分析】 因为一棵具有n个顶点的树有n-1条边，因此设此森林中有m棵树，每棵树具有的顶点数为vi(1≤i≤m)，则：

v1+v2+…+vm=N， ①

(vl-1)+(v2-1)+．．．+(vm一1)=K，②

①一②得：m=N-K

【解答】 答案为C。

二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树具有如下性质：

◇在二叉树的第i层上至多有2i-1个结点(i>=1)。

◇深度为k的二叉树至多有2k-1个结点(k>=1)。

1+ 。。。。。+ 2k-1

◇对任何一棵二叉树T，如果其终端结点数为儿n0，度为2的结点数为n2，则n0=n2+l。

◇具有n个结点的完全二叉树的深度为[log2n]+1。

◇如果对一棵有n个结点的完全二叉树(其深度为[log2n]]+1)的结点按层序编号(从第1层到第log2n]+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：

(1)如果i=1，则结点i是二叉树的根，无双亲；若i>1，则其双亲PARENT(i)是结点[i/2]。

(2)如果2i>n，则结点i无左孩子；否则其左孩子LCHILD(i)是结点2i。

(3)如果2i+l>n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。

二叉树的存储结构有顺序存储结构和链式存储结构两种。

例1（1999年中国科学院计算机技术研究所）深度为k(设根的层数为1)的完全二叉树至少有______个结点，至多有______个结点，k和结点数n之间的关系为______。

【分析】 当第k层只有1个结点时，深度为j的完全二叉树所具有的结点数最少，为20+21+…+2k-2+1=2k-1．当第k层有2k-1个结点时，深度为k的完全二叉树所具有的结点数最多，为20+21+…+2k-1=2k-1，此时的完全二叉树为满二叉树。

【解答】

2k-1 , 2k-1 ,k=1+[log2n]

二叉树的遍历有先(根)序遍历、中(根)序遍历、后(根)序遍历和层序遍历。遍历二叉树的基本操作就是访问结点。不论按照哪一种次序进行遍历，对含儿个结点的二叉树，其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，故空间复杂度也为O(n)。

利用二叉树中的空链域指向结点的前驱和后继的指针，叫做线索。加上线索的二叉树称为线索二叉树。对二叉树某种顺序遍历使其变为线索二叉树的过程称为线索化。利用线索来遍历二叉树一般情况下可以不使用栈。

例1（1999年中国科学院计算机技术研究所）______的遍历仍需要栈的支持。

(1)前序线索树 (2)中序线索树 (3)后序线索树

【分析】 由于后序遍历先访问子树后访问根结点，从本质上要求运行栈中存放祖先的信息，即使对二叉树进行后序线索化，仍然不能脱离栈的支持对此二叉树进行遍历。比如图中的后序线索树，没有栈的支持就无法对其进行后序遍历。

当访问到结点②时，由于没有线索指向②的后序后继③，而且没有指针返回到②的父结最④，因此对此二叉线索树的后序遍历无法进行，除非使用栈。

然而对于前序和中序线索树，则可以不使用栈就能够遍历。值得提出的是中序线索树，又称为对称线索树，对它不仅可以方便地进行中序遍历，而且能够在没有栈的支持的情况下，对其进行前序和后序遍历。

【解答】 答案为(3)。

哈夫曼树，又称最优树，是一类带权路径长度最短的树。从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度是从树根到每一结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径长度之和(最优查找树的定义相比较)。假设有n个权值(wl，w2，…， wn)，试构造一棵有儿个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树。

哈夫曼树的一个应用是哈夫曼编码。若要设计长短不等的编码，则必须任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。要设计总长最短的二进制前缀编码应以几种字符出现的频率作权，设计一棵哈夫曼树，由此得到的二进制前缀编码称为哈夫曼编码。

例1（1996年中国科学技术大学）已知某电文出现了1O种不同的字母，每个字母出现的频率分别为A：8，B：5，C：3，D：2，E：7，F：23，G：9，H：11，I：2，J：35，现在对这段电文用三进制进行编码(即码字由O，1，2组成)，问电文编码总长度至少有多少位?请画出相应的图。

【分析】有n个叶子结点的带权路径长度最短的二叉树称哈夫曼树，同理，存在有n个叶子结点的带权路径长度最短的三叉、四叉、…、k叉树，也称为哈夫曼树。要注意，若叶子结点数目不足以构成真正的k叉树(树中只有度为忌或O的结点)，即不满足(n-1)MOD(k-1)=O，需要添加权为O的结点，添加权为O的结点的个数为：k-(m-1)MOD(k1)-1。添加的位置应该是距离根结点最远处。

每个字母的编码长度为对应叶子结点的深度li(其中根结点的深度为O)，而电文的总长度为$sum_(i=1)^nw_il_i$，wi为每种字母在电文中出现的次数。

【解答】相应的哈夫曼编码树如图所示。

码长至少为35+(11+23+24)×2+(3+5)×3+(2+2)x4=191。

【考研－数据结构－树和二叉树－树的计数】

二叉树T和T'相似是指：两者都为空树或者两者都不为空树，且它们的左右子树分别相似。二叉树T和T'等价是指：两者不仅相似，而且所有对应结点上的数据元素均相同。二叉树的计数问题是讨论具有n个结点、互不相似的二叉树的数目bn。

含有n个结点的互不相似的二叉树有$1/(n+1)C_(2n)^n$棵。

含有n个结点有不同形态的树的数目tn和具有n-1个结点互不相似的二叉树的数目相同。

例1（1996年中国科学技术大学）如果只考虑有序树的情形，那么具有7个结点的不同形态的树共有________。

A.132 B.154 C.429 D.前三者均不正确

【分析】

含有n个结点有不同形态的树的数目tn和具有n-1个结点互不相似的二叉树的数目相同：$1/(n+1)C_(2n)^n$

【解答】

$t_6=1/(6+1)C_(12)^6=132$.

答案为A

例2（1995年中国科学院计算机技术研究所）具有7个结点的互不相似的二叉树共有多少？

【解答】

具有n个结点的互不相似的二叉树有$1/(n+1)C_(2n)^n$棵。

故具有7个结点的互不相似的二叉树有$1/(7+1)C_14^7＝429$棵。

BTree.cpp : Defines the entry point for the console application.

/*

作者：成晓旭

时间：2001年7月2日(9:00:00-14:00:00)

内容：完成二叉树的创建、前序遍历、中序遍历、后序遍历

时间：2001年7月2日(14:00:00-16:00:00)

内容：完成二叉树的叶子节点访问，交换左、右孩子

*/

#include \"stdafx.h\"

#include \"stdlib.h\"

#define MAX_NODE 100

#define NODE_COUNT1 8

#define NODE_COUNT2 15

int TreeValue0[NODE_COUNT1][2] {{'0',0},{'D',1},{'B',2},{'F',3},{'A',4},{'C',5},{'E',6},{'G',7}};

int TreeValue1[NODE_COUNT1][2] {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7}};

=

=

int TreeValue2[NODE_COUNT2][2] =

{{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7},{'H',8},{'I',9},{'J',10},{'K',11},{'L',12},{'M',13},{'N',14}};

struct BTree

{

int data;

int order;

BTree *lchild;

BTree *rchild;

};

void Swap(int *p1,int *p2)

{

int t;

t = *p1;

*p1 = *p2;

*p2 = t;

}

/*

function CreateBTree()功能：创建一颗二叉树，并返回一个指向其根的指针

*/

BTree *CreateBTree(int data[][2],int n)

{

BTree *Addr[MAX_NODE];

BTree *p,

*head;

int nodeorder,//节点序号

noderoot, //节点的双亲

i;

if(n>MAX_NODE)

{

printf(\"参数错误！\\n\");

return(0);

}

for(i=1;i<=n;i++)

{

p = (BTree *)malloc(sizeof(BTree));

if(p==NULL)

{

printf(\"内存溢出错误！\\n\");

return(0);

}

else

{

p->data = data[i][0];

p->lchild = NULL;

p->rchild = NULL;

nodeorder = data[i][1];

p->order = nodeorder;

Addr[nodeorder] = p;

if(nodeorder>1)

{

noderoot = nodeorder/2;

if(nodeorder %2 == 0)

Addr[noderoot]->lchild = p;

else

Addr[noderoot]->rchild = p;

}

else

head = p;

printf(\"BTree[%d] = %c\\

}

//free(p);

}

return(head);

}

/*

function FirstOrderAccess0()功能：实现二叉树的前序遍历

二叉树前序遍历的思想：

从根节点开始，沿左子树一直走到没有左孩子的节点为止，

依次访问所经过的节点，同时所经[节点]的地址进栈；

当找到没有左孩子的节点时，从栈顶退出该节点的双亲的

右孩子，此时，此节点的左子树已访问完毕；

在用上述方法遍历该节点的右子树，如此重复到栈空为止。

*/

void FirstOrderAccess0(BTree * header)

{

BTree * stack[MAX_NODE];

BTree *p;

int top;

top = 0;

p = header;

do

{

while(p!=NULL)

{

printf(\"BTree[%d] = %c\\访问节点P

top = top+1;

stack[top] = p;

p = p->lchild;//继续搜索节点P的左子树

}

if(top!=0)

{

p = stack[top];

top = top-1;

p = p->rchild;//继续搜索节点P的右子树

}

}while((top!=0)||(p!=NULL));

}

/*

function FirstOrderAccess1()功能：实现二叉树的前序遍历

二叉树前序遍历的思想：

从根节点开始，沿左子树一直走到没有左孩子的节点为止，

依次访问所经过的节点，同时所经[节点的非空右孩子]进栈；

当找到没有左孩子的节点时，从栈顶退出该节点的双亲的

右孩子，此时，此节点的左子树已访问完毕；

在用上述方法遍历该节点的右子树，如此重复到栈空为止。

*/

void FirstOrderAccess1(BTree * header)

{

BTree * stack[MAX_NODE];

BTree *p;

int top;

top = 0;

p = header;

do

{

while(p!=NULL)

{

printf(\"BTree[%d] = %c\\

if(p->rchild!=NULL)

stack[++top] = p->rchild;

p = p->lchild;

}

if(top!=0)

p = stack[top--];

}while((top>0)||(p!=NULL));

}

/*

function MiddleOrderAccess()功能：实现二叉树的中序遍历

二叉树中序遍历的思想：

从根节点开始，沿左子树一直走到没有左孩子的节点为止，

并将所经[节点]的地址进栈；

当找到没有左孩子的节点时，从栈顶退出该节点并访问它，

此时，此节点的左子树已访问完毕；

在用上述方法遍历该节点的右子树，如此重复到栈空为止。

*/

void MiddleOrderAccess(BTree * header)

{

BTree * stack[MAX_NODE];

BTree *p;

int top;

top = 0;

p = header;

do

{

while(p!=NULL)

{

stack[++top] = p;//节点P进栈

p = p->lchild; //继续搜索其左子树

}

if(top!=0)

{

p = stack[top--];//节点P出栈

printf(\"BTree[%d] = %c\\访问节点P

p = p->rchild;//继续搜索其左子树

}

}while((top!=0)||(p!=NULL));

}

/*

function LastOrderAccess()功能：实现二叉树的后序遍历

二叉树后序遍历的思想：

从根节点开始，沿左子树一直走到没有左孩子的节点为止，

并将所经[节点]的地址第一次进栈；

当找到没有左孩子的节点时，此节点的左子树已访问完毕；

从栈顶退出该节点，判断该节点是否为第一次进栈，如是，再

将所经[节点]的地址第二次进栈，并沿该节点的右子树一直走到

没有右孩子的节点为止，如否，则访问该节点；此时，该节点的

左、右子树都已完全遍历，且令指针p = NULL;

如此重复到栈空为止。

*/

void LastOrderAccess(BTree * header)

{

BTree * stack[MAX_NODE];//节点的指针栈

int count[MAX_NODE];//节点进栈次数数组

BTree *p;

int top;

top = 0;

p = header;

do

{

while(p!=NULL)

{

stack[++top] = p;//节点P首次进栈

count[top] = 0;

p = p->lchild; //继续搜索节点P的左子树

}

p = stack[top--];//节点P出栈

if(count[top+1]==0)

{

stack[++top] = p;//节点P首次进栈

count[top] = 1;

p = p->rchild; //继续搜索节点P的左子树

}

else

{

printf(\"BTree[%d] = %c\\访问节点P

p = NULL;

}

}while((top>0));

}

/*

function IsLeafNode()功能：判断给定二叉树的节点是否是叶子节点

*/

int IsLeafNode(BTree *node)

{

if((node->lchild==NULL)&&(node->rchild==NULL))

return(1);

else

return(0);

}

/*

function PrintLeafNode()功能：输出给定二叉树的叶子节点

*/

void PrintLeafNode(BTree *header)

{

BTree * stack[MAX_NODE];//节点的指针栈

BTree *p;

int top;

p = header;

top = 0;

do

{

while(p!=NULL)

{

stack[++top] = p;

p = p->lchild;//继续搜索节点P的左子树

}

if(top!=0)

{

p = stack[top--];

if(IsLeafNode(p))

printf(\"LNode[%d] = %c\\访问叶子节点

p = p->rchild;//继续搜索节点P的右子树

}

}while(top>0||p!=NULL);

}

/*

function HasTwoChildNode()功能：判断给定二叉树的节点是否存在两个孩子节点

*/

int HasTwoChildNode(BTree *node)

{

if((node->lchild!=NULL)&&(node->rchild!=NULL))

return(1);

else

return(0);

}

/*

function SwapChildNode()功能：交换给定二叉树的所有节点的左、右孩子

*/

void SwapChildNode(BTree *header)

{

BTree * stack[MAX_NODE];//节点的指针栈

BTree *p;

int top;

p = header;

top = 0;

do

{

while(p!=NULL)

{

stack[++top] = p;

p = p->lchild;//继续搜索节点P的左子树

}

if(top!=0)

{

p = stack[top--];

if(HasTwoChildNode(p))

Swap(&p->lchild->data,&p->rchild->data);//交换节点P的左、右孩子

p = p->rchild;//继续搜索节点P的右子树

}

}while(top>0||p!=NULL);

}

int main(int argc, char* argv[])

{

BTree * TreeHeader;

printf(\"二叉树创建数据结果：\\n\");

TreeHeader = CreateBTree(TreeValue1,NODE_COUNT1-1);

//TreeHeader = CreateBTree(TreeValue2,NODE_COUNT2-1);

if (TreeHeader==0)

{

printf(\"二叉树创建失败！\\n\");

return(0);

}

else

{

printf(\"\\n二叉树前序遍历结果：\\n\");

FirstOrderAccess1(TreeHeader);

printf(\"\\n二叉树中序遍历结果：\\n\");

MiddleOrderAccess(TreeHeader);

printf(\"\\n二叉树后序遍历结果：\\n\");

LastOrderAccess(TreeHeader);

//printf(\"\\n二叉树的所有叶子节点：\\n\");

//PrintLeafNode(TreeHeader);

//SwapChildNode(TreeHeader);

//printf(\"\\n二叉树交换孩子的结果：\\n\");

//MiddleOrderAccess(TreeHeader);

printf(\"\\n程序运行完毕!\\n\");

return 0;

}

}