一.树的基本术语
1.树
- 什么是空树？结点数为0的树
- 非空树的特性？有且仅有一个根结点，没有后继的结点称为“叶子结点”，有后继的结点称为“分支结点”，除了根结点外任何一个结点都有且仅有一个前驱，每个结点可以有一个或者多个后继
- 什么是两个结点之间的路径？：只能从上往下，有方向的
- 什么是路径长度？经过了几条边
- 结点的高度?从上往下数；树的高度：一共有多少层
- 什么是结点的度？有几个分支
- 什么是树的度？各结点度的最大值
- 什么是有序树？逻辑上看树中结点的各子树从左至右是有次序的，不能互换
- 什么是森林？森林是m棵互不相交的树的集合
- 树有什么性质？
- 结点数=总度数+1
- 度为m的树和m叉树的区别
- 度为m的树（或者m叉树）第i层最多有m的i-1次幂个结点(i>=1)
- 高度为h的m叉树最多有(m的h次幂-1)/(m-1)个结点
- 高为h的m叉树至少有h个节点；高度为h、度为m的树至少有h+m-1个结点
- 具有n个结点的m叉树最小高度为logm(n(m-1)+1)向上取整
2.二叉树
- 二叉树有什么特点？每个结点至多只有两棵子树；左右子树不能颠倒，二叉树是有序树
- 什么是满二叉树？只有最后一层有叶子结点；不存在度为1 的结点；按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1，结点i的父节点为i/2向下取整；一棵高度为h，且含有(2的h次幂-1)个结点的二叉树。
- 什么是完全二叉树？当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。
- 什么是二叉排序树？左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字。左子树和右子树又是一颗二叉排序树
- 什么是平衡二叉树？树上任意结点的左子树和右子树的深度之差不超过1，平衡二叉树有更高的搜索效率
- 非空二叉树有哪些性质？（1）设非空二叉树中度为0,1,2的结点个数分别为n0，n1和n2，则n0=n2+1，结点总数=n0+n1+n2（2）二叉树的第i层最多有(2的i-1次幂)个结点（3）高度为h的二叉树至少有(2的h次幂-1)个结点
- 完全二叉树的常考性质？（1）具有n个结点的完全二叉树高度为(log2(n+1)向上取整)，(log2n向下取整+1)（2）对于完全二叉树，可以由结点数n推出度为0、1和2 的结点个数为n0，n1和n2，n0+n2一定是奇数，n1一定是0或者1
- 二叉树的存储结构有哪些？顺序存储和链式存储
- 非完全二叉树如何顺序存储？一定要把二叉树的结点标号和完全二叉树对应起来，但是实际应用中这样空间浪费，一般很少使用。
- 二叉树链式存储从无到有的构建过程？
//存放二叉树的结点
typedef struct BiTNode{
int data;//数据域
struct BiTNode *lchild,*rchild;//指针域
}BiTNode,*BiTree;
int main()
{
//定义一颗空树
BiTree root=NULL;
//插入根结点
root=(BiTree)new BiTNode;
root->data=1;root->lchild=NULL;root->rchild=NULL;
//插入新结点
BiTNode* p=(BiTNode*)new BiTNode;
p->data=2;p->lchild=NULL;p->rchild=NULL;
root->lchild=p;//插入的新结点作为根结点的左孩子
}
- 如果需要方便的找到父结点怎么存储？存储左右孩子指针(*lchild,*rchild)之后存储父指针(*parent)
- n个结点的二叉链表有多少个空链域？n+1（2n-（n-1））
二.二叉树的遍历
- 二叉树的先序（根）遍历如何遍历？根左右
- 二叉树的后序遍历如何遍历？左右根
- 二叉树的中序遍历如何遍历？左根右
- 对于算数表达式的分析树，先序遍历代表前缀表达式，后序遍历代表后缀表达式，中序遍历代表中缀表达式
//先序遍历
void PreOrder(BiTree T)
{
if(T!=NULL)
{
visit(T);//遍历根结点
PreOrder(T->lchild);//遍历左子树
PreOrder(T->rchild);//遍历右子树
}
}
//中序遍历
void InOrder(BiTree T)
{
if(T!=NULL)
{
PreOrder(T->lchild);//遍历左子树
visit(T);//遍历根结点
PreOrder(T->rchild);//遍历右子树
}
}
//后序遍历
void PostOrder(BiTree T)
{
if(T!=NULL)
{
PreOrder(T->lchild);//遍历左子树
PreOrder(T->rchild);//遍历右子树
visit(T);//遍历根结点
}
}- 二叉树的层序遍历步骤？（1）设置一个辅助队列，根结点入队（2）若队列非空则根结点出队，根结点的左右结点入队（3）重复步骤（2）直到队列为空。
//层次遍历
//其实入队的是结点的指针而不是结点，结点指针入队更节省
void LevelOrder(BiTree T)
{
queue<BiTree> q;//辅助队列
BiTree p;
q.push(T);//将根节点入队
while(!q.empty())
{
p=q.front();//返回队列第一个元素
q.pop();//删除队列第一个元素
if(p->lchild!=NULL)///左孩子入队
q.push(p->lchild);
if(p->rchild!=NULL)//右孩子入队
q.push(p->rchild);
}
} - 给出一个二叉树的前/中/后/层 序遍历中的一种，能唯一确定一颗二叉树吗？不能
- 给出哪两个遍历序列可以唯一确定一棵二叉树？前序+中序，后序+中序，层序+中序
三.线索二叉树
- 什么是线索二叉树？利用二叉树的n+1个空链域，把这些链域变成线索，用tag标记线索与否
- 有几种线索二叉树？有3种线索二叉树，他们之间是根据先序、后序、中序来确定前驱后继的
- 线索二叉树有什么好处？可以很方便的找到指定结点的前驱和后继
- 中序线索化的过程？中序线索化实际上就是中序遍历过程中，一边遍历一边线索化
- 中序线索化的代码？（先序、后序线索化执行过程与中序一致，但是需要改变遍历次序）
typedef struct ThreadNode{
int data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;//左右线索标志 tag=0的时候表示指向孩子,tag=1表示指向线索
}ThreadNode,*ThreadTree;
//全局变量，访问当前结点的前驱结点
ThreadNode* pre=NULL
//创建中序线索二叉树
void CreateInThread(ThreadTree T)
{
if(T!=NULL)//非空二叉树才能线索化
{
InThread(T);//中序线索化二叉树
if(pre->rchild==NULL)//注意处理最后一个结点的孩子
pre->rtag=1;//遍历的最后一个结点后继为NULL
}
}
//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T)
{
if(T!=NULL)
{
InThread(T->lchild);//中序遍历左子树
visit(T);//访问根结点
InThread(T->rchild);//中序遍历右子树
}
}
void visit(ThreadNode* q)
{
if(q->lchild==NULL)
{
q->lchild=pre;//左孩子指向前驱节点
q->ltag=1;//孩子节点标记为线索
}
if(pre!=NULL&&pre->rchild==NULL)
{
pre->rchild=q;//右孩子指向后继
pre->rtag=1
}
pre=q;//标记前驱结点
} - 先序线索化如果遍历代码不加限制会出现什么情况？遍历访问左孩子的代码时会转圈循环
- 如何修改？
void PreThread(ThreadTree T)
{
if(T!=NULL)
{
visit(T);//访问根结点
if(T->ltag==0)//如果lchild不是前驱线索的情况下
PreThread(T->lchild);//先序遍历左子树
PreThread(T->rchild);//先序遍历右子树
}
} - 如何使用中序线索二叉树找中序后继？（得出中序序列）
typedef struct ThreadNode{
int data;//数据域
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*TreadTree;
//找到以p为根结点的子树中，第一个被中序遍历的结点
ThreadNode* FirstNode(ThreadNode* p)
{
//循环找到最左下结点，不一定是叶子结点
while(p->lchild)
{
p=p->lchild;//可能最后一个左结点存在右孩子
}
return p;//返回最左结点的指针
}
//在中序线索二叉树中找到p的后继结点
ThreadNode* NextNode(ThreadNode* p)//寻找p的后继结点
{
//找到右子树中最左下结点
if(p->rtag==0)
return FirstNode(p);
else return p->rchild;//rtag=1直接返回后继线索
}
//对中序线索二叉树进行中序遍历
void Inorder(ThreadNode *T)
{
for(ThreadNode* p=FirstNode(T);p!=NULL;p=NextNode(p))
visit(p);//
} - 如何用中序线索二叉树找中序前驱？（将中序序列逆序）
//找到以p为根的子树中最后一个被中序遍历的结点
ThreadNode* LastNode(ThreadNode* p)
{
while(p->ltag)
p=p->rchild;//循环找到最右侧结点
return p;
}
//在中序线索二叉树中找到p的前驱结点
ThreadNode* PreNode(ThreadNode* p)
{
if(p->ltag==0)return LastNode(p);//如果没有线索，返回中序序列前驱
else return p->lchild;//ltag=1返回前驱线索
}
//对中序线索二叉树进行逆向中序遍历
void RevInOrder(ThreadNode* T)
{
for(ThreadNode*p=LastNode(T);p!=NULL;p=PreNode(T))
visit(p);//遍历p
}无论是中序线索二叉树找前驱还是后继，都是对二叉树的一种遍历，但是遍历方式不同于二叉树的递归遍历，而是自写一套有关于中序遍历的规则，找前驱是正常写出中序序列，找后继是逆向写出中序序列。
- 如何在先序线索二叉树中找到指定结点*p的先序后继next？如果p->rtag=1那么next=p>rchild，如果p->rtag=0，那么如果p有左孩子，则先序后继为左孩子；如果p没有左孩子，那么先序后继为右孩子。
- 先序线索二叉树可以找到指定结点的前驱吗？如果只有左右指针的话不可以，可以使用三叉链表，或者从头开始遍历
- 后序线索二叉树能找到只能找到前驱，不能找到后继
四.树
- 树的表示方法？
（1）双亲表示法（顺序存储）：每个结点存放指向双亲的序号。存入：放入结点以及双亲结点；删除：将结点条目的双亲结点=-1或者删除此条目以及以该结点为根结点的所有结点。
typedef struct{
ElemType data;//数据(工程中数据不一定是整型，可能是结构体)
int parent;//双亲位置域
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE];//双亲表示
int n;//结点数
}PTree;表示形式如果data为整型其实也可以是二维数组，但是并没有结构体嵌套这样方便
（2）孩子表示法（顺序存储和链式存储）：顺序存储中的结点链式存储自己的孩子，顺序存储的结点包括所有的结点，用顺序存储的下标号表示每一个结点。
//链式存储的孩子
typedef struct CTNode{
int child;//孩子结点在数组中的位置
struct CTNode* next;//指针指向下一个孩子
};
//顺序存储的所有结点
typedef struct CTbox{
ElemType data;
struct CTNode* firstchild;//顺序存储的结点的每一串孩子
}CTbox;
//顺序表
typedef struct{
CTbox nodes[MAX_TREE_SIZE];//顺序存储表
int n,r;//结点数和根的位置
}CTree;（3）孩子兄弟表示法：每一个结点的左指针指向第一个孩子，右指针指向第一个兄弟。这样可以将树转换成二叉树
//孩子兄弟表示法
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针
}CSNode,*CSTree;- 树的遍历可以参考二叉树的遍历
- 先中后序遍历森林本质是先用孩子兄弟表示法存储森林，然后依次遍历各个子树的先中后序遍历
五.哈夫曼树
- 什么是带权路径长度？树中根到该结点的长度（经过的边数）与该结点上权值的乘积
- 什么是树的带权路径长度WPL？树中所有叶子结点的带权路径长度之和
- 什么是哈夫曼树（最优二叉树）？给定n个带权结点的二叉树，其中带权路径WPL最小的二叉树称为哈夫曼树
- 如何构造哈夫曼树？
- 给定n个结点，将这n个结点作为仅含一个结点的二叉树，构造森林F
- 选取其中权值最小的两个树，将其作为左右子树，其根结点的权值为左右子树的权值之和，在森林F中去掉这两个树，并加入权值之和的树
- 循环步骤2.直到没有剩余树
- 哈夫曼树有什么特点？含有n个叶子结点的哈夫曼树一共有2n-1个结点；每一个初始结点最终都成为叶子结点，并且权值越小的叶子结点离根越远；哈夫曼树中不存在度为1的结点；哈夫曼树并不唯一，但是哈夫曼树必定权值相同。
- 什么是可变长度编码？允许对不同字符用不等长的二进制位表示
- 什么是前缀编码？没有一个编码是另一个编码的前缀
- 如何由哈夫曼树构造哈夫曼编码？字符集中的每一个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，构造哈夫曼树之后，左支代表0，右支代表1，得到哈夫曼编码。
- 哈夫曼树传递的位数是多少？该树的WPL
