离散数学树知识点总结

离散数学树知识点
总结
-CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN
第六章树
一、掌握基本概念
树的子树是互不相交的，树可以为空（空树）
非空的树中，只有一个结点是没有前趋的，那就是根。

非空树只有一个树根，是一对多的关系。

叶子结点、结点的度、树的度、结点的层次、树的深度、树的四种表示方法二、二叉树的定义、特点、五种基本形态
二叉树是有序树，左右子树不能互相颠倒
二叉树中结点的最大度为2，但不一定都是2。

三、二叉树的性质要掌握
性质1：二叉树的第i层上至多有2 i-1（i 1）个结点。

性质2：深度为k的二叉树中至多2k-1个结点。

性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为
n2，则n0＝n2＋1。

证明：1)结点总数 n=n0+n1+n2 (n1是度为1的结点数)
2)进入分支总数m(每个结点唯一分支进入) n=m+1
3)m个分支是由非叶子结点射出 m=n1+2n2
性质4：具有n个结点的完全二叉树的深度k为[log2n]+1
四、满二叉树和完全二叉树的区别是什么？
满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。

深度为k的二叉树，最少有k个结点，最多有2k-1
深度为k的完全二叉树，最少有2k-1-1+1个结点,最多有2k-1
五、二叉树的存储结构（可以通过下标找结点的左右孩子）
1.顺序存储结构适用于满二叉树和完全二叉树。

（其缺点是必须把其他二叉树补成完全二叉树，从上到下，从左到右依次存储在顺序存储空间里，会造成空间浪费）
2.二叉链表存储结构（其优点是找左孩子和右孩子方便，但缺点是找父节点麻烦）
lchild Data rchild
（重点）
3. 三叉链表存储结构
不仅找其左、右孩子很方便，而且找其双亲也方便
六、遍历的概念是什么？
七、二叉树的遍历有三种：前序（先序、先根）遍历、中序（中序、中根）遍历、后序（后序、后根）遍历
1.给出一棵二叉树，要会二叉树的三种遍历
2.给出两种遍历（必须有中序遍历），要求会画该二叉树。

八、了解引入线索（中序、先序、后序）二叉树的原因是什么？
九、会在二叉树上画先序线索化、中序线索化、后序线索化。

在线索二叉树的格式中，可以找到任意结点的直接后继。

（错）
在线索二叉树中，如果某结点的右孩子为空，那么可以找到该结点的直接后继。

（对）
在线索二叉树中，如果某结点的左孩子为空，那么可以找到该结点的直接前趋。

（对）
十、树.森林和二叉树的相互转换
树转换成二叉树后，转换后的二叉树根的右子树为空。

十一、森林的遍历（只有先序遍历和后序遍历）
先序遍历一棵树，相当于先序遍历该树所对应的二叉树。

后序遍历一棵树，相当于中序遍历该树所对应的二叉树。

十二、赫夫曼树（又称最优二叉树或哈夫曼树）、赫夫曼树编码
1. 赫夫曼树中，权越大的叶子离根越近，其形态不唯一，但是WPL带权路径长度一定是最小。

2.一定要会构造哈夫曼树，在构造好的哈夫曼树上会构造哈夫曼编码。

（认真看题目要求）
第6章算法设计题
1．已知二叉树中的结点类型用BiTNode表示，被定义描述为：
Typedef struct BiTNode {
TElemType data ;
struct BiTNode * LChild , *RChild;
} BiTNode,*BiTree;
其中data为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，编写出求一棵二叉树高度的算法。

Int BTreeHeight(BiTree BT){
if (BT==NULL) return 0;
else {
h1=BTreeHeight(BT->LChild);
h2=BTreeHeight(BT->RChild);
if (h1>h2) return(h1+1);
else return( h2+1);
}
}
2．已知二叉树中的结点类型用BiTNode表示，被定义描述为：
Typedef struct BiTNode {
TElemType data ;
struct BiTNode * LChild , *Rchild；
} BiTNode,*BiTree；
BiTree T；
其中data为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，编写算法，求出二叉树中2度结点个数。

int degree2nodenum(BiTree T)
{if (T){
if(T->lchild！=NULL &&T->child！=NULL)
count++;
leafnodenum(l->lchild);
leafnodenum(l->rchild);
}
return count;
}
3．已知二叉树中的结点类型用BiTNode表示，被定义描述为：
Typedef struct BiTNode {
TElemType data ;
struct BiTNode * LChild , *RChild;
} BiTNode,*BiTree;
BiTree T；
其中data为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，写一算法，求出二叉树中的叶子结点个数。

void BTreeLeaf (BiTree BT)
{
if(BT)
{
if(BT-> LChild==NULL && BT->RChild==NULL) count++;
BTreeLeaf (BT->LChild); // 访问左子树
BTreeLeaf (BT->RChild); // 访问右子树
}
}
或下面算法均可
编写递归算法，计算二叉树中叶子结点的数目。

int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目
{
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1; //叶子结点
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数
}//LeafCount_BiTree
4．PPT上的三种遍历递归算法和课本上P131先序递归创建二叉链表。

5. 给定一棵二叉树，其根指针为root。

试写出求二叉树结点数目的算法（递归算法或非递归算法）。

【提示】采用递归算法实现。

int count(BiTree t){
if (t==NULL)
return 0;
else
return count(t->lchild)+count(t->rchild)+1;
}
6. 以二叉链表为存储结构，写一算法交换各结点的左右子树。

【分析】
依题意，设t 为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算基于后序遍历实现：交换左子树上各结点的左右子树；交换右子树上各结点的左右子树；再交换根结点的左右子树。

【算法】
void Exchg(BiTree *t){
BinNode *p;
if (t){
P=(*t)->lchild;
(*t)->lchild=(*t)->rchild;
(*t)->rchild=p;
Exchg(&((*t)->lchild));
Exchg(&((*t)->rchild));
}
}
7. 已知一棵二叉树采用二叉链表结构存储，每个结点的值为整数类型。

要求：给出相应的语言描述，在此基础上设计计算二叉树中所有结点值之和的算法。

typedef struct link
{int data;
struct link * lchild;
struct link * rchild;
} bitnode , *bitree ;
void sum(bitree *bt,int &s)
{
if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);} }。