一.树的基本术语

1.树

• 什么是空树？结点数为0的树
• 非空树的特性？有且仅有一个根结点，没有后继的结点称为“叶子结点”，有后继的结点称为“分支结点”，除了根结点外任何一个结点都有且仅有一个前驱，每个结点可以有一个或者多个后继
• 什么是两个结点之间的路径？：只能从上往下，有方向的
• 什么是路径长度？经过了几条边
• 结点的高度?从上往下数；树的高度：一共有多少层
• 什么是结点的度？有几个分支
• 什么是树的度？各结点度的最大值
• 什么是有序树？逻辑上看树中结点的各子树从左至右是有次序的，不能互换
• 什么是森林？森林是m棵互不相交的树的集合
• 树有什么性质？

1. 结点数=总度数+1
2. 度为m的树和m叉树的区别
3. 度为m的树（或者m叉树）第i层最多有m的i-1次幂个结点(i>=1)
4. 高度为h的m叉树最多有(m的h次幂-1)/(m-1)个结点
5. 高为h的m叉树至少有h个节点；高度为h、度为m的树至少有h+m-1个结点
6. 具有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最小的二叉树称为哈夫曼树
• 如何构造哈夫曼树？

1. 给定n个结点，将这n个结点作为仅含一个结点的二叉树，构造森林F
2. 选取其中权值最小的两个树，将其作为左右子树，其根结点的权值为左右子树的权值之和，在森林F中去掉这两个树，并加入权值之和的树
3. 循环步骤2.直到没有剩余树

• 哈夫曼树有什么特点？含有n个叶子结点的哈夫曼树一共有2n-1个结点；每一个初始结点最终都成为叶子结点，并且权值越小的叶子结点离根越远；哈夫曼树中不存在度为1的结点；哈夫曼树并不唯一，但是哈夫曼树必定权值相同。
• 什么是可变长度编码？允许对不同字符用不等长的二进制位表示
• 什么是前缀编码？没有一个编码是另一个编码的前缀
• 如何由哈夫曼树构造哈夫曼编码？字符集中的每一个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，构造哈夫曼树之后，左支代表0，右支代表1，得到哈夫曼编码。
• 哈夫曼树传递的位数是多少？该树的WPL