一、二叉树的定义
二叉树是 n( n >= 0 ) 个结点组成的有限集合，这个集合要么是空集（当 n 等于 0 时），要么是由一个根结点和两棵互不相交的二叉树组成。其中这两棵互不相交的二叉树被称为根结点的左子树和右子树。
如图所示，2 是 1 的左子树，3 是 1 的右子树；同时，4 和 5 分别是 2 的左右子树，6 和 7 分别是 3 的左右子树。
二、二叉树的特点
二叉树是一种树，它有如下几个特征：
1）每个结点最多二棵子树，即每个结点的孩子结点个数为 0、1、2。
2）这两棵子树是有顺序的，分别叫：左子树 和 右子树，就像左手和右手一样，是不能颠倒的。
3）如果只有一棵子树的情况，也需要区分顺序，如图所示：
b 为 a 的左子树
c 为 a 的右子树
三、特殊二叉树
1、斜树
所有结点都只有左子树的二叉树，被称为左斜树，像这样：
所有结点都只有右子树的二叉树，被称为右斜树，像这样：
斜树有点类似线性表，所以线性表可以理解为一种特殊形式的树。
2、满二叉树
对于一棵二叉树，如果它的所有根结点和内部结点都存在左右子树，且所有叶子结点都在同一层，这样的树就是满二叉树，像这样：
满二叉树有如下几个特点：
1）叶子结点一定在最后一层
2）非叶子结点的度为 2
3）深度相同的二叉树中，满二叉树的结点个数最多，为 2^h-1（其中 h 代表树的深度）
3、完全二叉树
对一棵具有 n 个结点的二叉树，按照层序进行编号，如果编号 i 的结点和同样深度的满二叉树中的编号 i 的结点在二叉树中，位置完全相同则被称为 完全二叉树。
满二叉树一定是完全二叉树，而完全二叉树则不一定是满二叉树，完全二叉树有如下几个特点：
1）叶子结点只能出现在最下面两层
2）最下层的叶子结点，一定是集中在左边的连续位置，倒数第二层如果有叶子结点一定集中在右边的连续位置
3）如果某个结点度为 1，则只有左子树，即 不存在只有右子树 的情况
4）同样结点数的二叉树，完全二叉树的深度最小
如下图所示，就不是一棵完全二叉树，因为 5 号结点没有右子树，但是 6 号结点是有左子树的，不满足上述第 2 点。完全二叉树实际上是对应的满二叉树删除叶结点层最右边若干个结点得到的
四、二叉树的性质
以下性质对理解二叉树有很好的帮助，可以尝试自行证明。或许在后续遇到贪心相关问题时，需要用到这些证明。
1）二叉树的第 i（i >= 1）层上最多 2^(i-1) 个结点；
2）深度为 h 的二叉树至多 2^h - 1 个结点；
3）n 个结点的完全二叉树的深度为 floor(log2n) + 1（其中 floor(x) 代表对 x 取下整）；
4) 若编号为 i 的结点有左孩子结点，则左孩子结点的编号为 2i ；若编号为i的结点有右孩子结点，则右孩子结点的编号为 2i+1。
5) 除树根结点外，若一个结点的编号为 i，则它的双亲结点的编号为 floor[i/2] 。 若i≤floor[n/2]，则编号为i的结点为分支结点，否则为叶结点。
五、二叉树的顺序存储
二叉树的顺序存储就是指：利用顺序表对二叉树进行存储。结点的存储位置即顺序表的索引，能够体现结点之间的逻辑关系比如父结点和孩子结点之间的关系，左右兄弟结点之间的关系 等等。
1、完全二叉树
来看一棵完全二叉树，我们对它进行如下存储：
编号代表了顺序表索引的绝对位置，映射后如下
这里为了方便，我们把顺序表索引为 0 的位置给留空了。
这样一来，当知道某个结点在顺序表中的索引 x，就可以知道它左右儿子的索引分别为 2x 和 2x+1。反之，当知道某个结点的索引 x，也能知道它父结点的索引为 floor(x/2)。
2、非完全二叉树
对于非完全二叉树，只需要将对应不存在的结点设置为空即可
编号代表了顺序表索引的绝对位置，映射后如下
3、稀疏二叉树
对于较为稀疏的二叉树，就会有如下情况出现。这时候如果用这种方式进行存储，就比较浪费内存了
编号代表了顺序表索引的绝对位置，映射后如下：
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| data | - | a | b | c | d | - | - | g | h | - | - | - | - |
在顺序存储结构中，找一个结点的双亲和孩子都很容易.
这种情况下，为了提升内存利用率，我们可以采用链表进行存储。
六、二叉树的链式存储
二叉树每个结点至多有两个孩子结点，所以对于每个结点设置一个 数据域（data） 和 两个 指针域（left 和 right） 即可。指针域 分别指向 左孩子结点 和 右孩子结点。
占用的存储空间与树形没有关系，只与树中结点个数有关。
在二叉链中，找一个结点的孩子很容易，但找其双亲不方便。
七、二叉树的遍历概念
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点访问一次且仅被访问一次。
对于线性表的遍历，要么从头到尾，要么从尾到头，遍历方式较为单纯。但是树不一样，它的每个结点都有可能有两个孩子结点，所以遍历的顺序面临着不同的选择。
二叉树的常用遍历方法，有以下四种：前序(先序)遍历、中序遍历、后序遍历、层序遍历。
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| data | - | a | b | c | d | - | e | f | g | h | - | - | i |
八、二叉树的前序遍历
如果二叉树为空则直接返回，否则先访问根结点，再递归前序遍历左子树，再递归前序遍历右子树。前序遍历的结果如下：abdghcefi
九、二叉树的中序遍历
如果二叉树为空则直接返回，否则先递归中序遍历左子树，再访问根结点，再递归中序遍历右子树。中序遍历的结果如下：gdhbaecif。
十、二叉树的后序遍历
如果二叉树为空则直接返回，否则先递归后遍历左子树，再递归后序遍历右子树，再访问根结点。后序遍历的结果如下：ghdbeifca。
以二叉树表示表达式的递归定义如下：
（1）若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息；
（2）若表达式为“第一操作数 运算符 第二操作数”的形式，则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元运算符，则左子树为空），其中，操作数本身又为表达式。
例如图所示的二叉树表达式 a+b*(c-d)-e/f
先序的遍历序列为：-+a*b-cd/ef
中序的遍历序列为：a+b*c-d-e/f
后序的遍历序列为：abcd -*+ef/ -
十一、二叉树的层序遍历
如果二叉树为空直接返回，否则依次从树的第一层开始，从上至下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。图中二叉树层序遍历的结果为：abcdefghi。
十二、线索二叉树
对于具有n个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有2n个指针域。
其中只有n-1个结点被有效指针所指向，即有n-1个非空指针域。
所以共有2n-(n-1) = n+1个空链域。
二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？
——可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。
若结点有左子树，则lchild指向其左孩子；否则， lchild指向其直接前驱(即线索)；
若结点有右子树，则rchild指向其右孩子；否则， rchild指向其直接后继(即线索) 。
typedef struct BiThrNode
{ TElemType data; //结点数据域
int LTag，RTag; //增加的线索标记
struct BiThrNode *lchild; //左孩子或线索指针
struct BiThrNode *rchild; //右孩子或线索指针
} BiThrNode, *BiThrTree; //线索树结点类型定义
由于对二叉树进行先序和后序线索化后，对二叉树的遍历仍然需要用到双亲的信息才能够遍历，所以这两种线索化很少使用，通常只用中序线索化二叉树。
实际还有很多但是他并不常用，因此不看了
一、二叉树结点定义
#include <iostream>
using namespace std;
template < typename T >
struct TreeNode {
T val; // (1)
TreeNode * left; // (2)
TreeNode * right; // (3)
TreeNode(): val(0), left(NULL), right(NULL) {} // (4)
TreeNode(T x): val(x), left(NULL), right(NULL) {} // (5)
};(1) 定义了一个类型为 T 的成员变量 val，用于存储树节点的值。
(2) 定义了一个指向 TreeNode 类型的指针成员变量 left，用于存储左子结点的指针。
(3) 定义了一个指向 TreeNode 类型的指针成员变量 right，用于存储右子结点的指针。
(4) 定义了一个无参的构造函数，在创建树节点时将 val、left 和 right 都初始化为 NULL，并将 val 的值设置为 0。
(5) 定义了一个带参的构造函数，在创建树节点时将传入的参数赋值给 val，并将 left 和 right 都初始化为 NULL。
二、二叉树类的定义
template < typename T >
class Tree {
private:
TreeNode < T > * nodes;
TreeNode < T > * root;
size_t nodeSize;
TreeNode < T > * Create(T a[], int size, int nodeId, T nullNode); // (1)
void visit(TreeNode < T > * node); // (2)
void preOrder(TreeNode < T > * node); // (3)
void inOrder(TreeNode < T > * node); // (4)
void postOrder(TreeNode < T > * node); // (5)
public:
Tree(); // (6)
Tree(int maxNodes); // (7)
~Tree(); // (8)
TreeNode < T > * GetTreeNode(int id); // (9)
void CreateTree(T a[], int size, T nullNode); // (10)
void preOrderTraversal(); // (11)
void inOrderTraversal(); // (12)
void postOrderTraversal(); // (13)
};(1) 这是一个模板函数声明，用于创建一个具有类型为 T 的树，是用于递归调用的。
(2) 这是一个成员函数声明，用于访问树结点（这里的实现就是打印结点的值）。
(3) 这是一个成员函数声明，用于前序遍历树结点。
(4) 这是一个成员函数声明，用于中序遍历树结点。
(5) 这是一个成员函数声明，用于后序遍历树结点。
(6) 这是构造函数声明，用于创建树结点池。
(7) 这是构造函数声明，用于创建一个具有最大结点数为 maxNodes 的树。
(8) 这是析构函数声明，用于销毁树对象并释放内存。
(9) 这是一个成员函数声明，用于获取指定编号的树结点。
(10) 这是一个成员函数声明，用于创建树。
(11) 这是一个成员函数声明，用于执行前序遍历。
(12) 这是一个成员函数声明，用于执行中序遍历。
(13) 这是一个成员函数声明，用于执行后序遍历。
三、二叉树的创建
template < typename T >
Tree < T > ::Tree() {
nodeSize = 100001;
nodes = new TreeNode < T > [nodeSize];
}
template < typename T >
Tree < T > ::Tree(int maxNodes) {
nodeSize = maxNodes;
nodes = new TreeNode < T > [nodeSize];
}这是两个不同参数的 Tree 的构造函数的实现，用来生成树的结点池。
四、二叉树的销毁
template<typename T>
Tree<T>::~Tree() {
delete[] nodes;
}当树销毁的时候，利用 delete 来清理结点池的内存空间。
五、获取二叉树的结点
template<typename T>
TreeNode<T>* Tree<T>::GetTreeNode(int id) {
return &nodes[id];
}通过 id 在 nodes 数组中索引，通过 O(1) 的时间复杂度内快速找到对应的树结点，然后再取地址并返回，就得到了 id 对应的树结点的地址。
六、访问二叉树的结点
template<typename T>
void Tree<T>::visit(TreeNode<T> *node) {
cout << node->val;
}用于访问传入的二叉树结点 node，为了体现二叉树的遍历，所以这里的实现是输出它的值。
void DispLeaf(BiTree T)
{
if (T != NULL)
{
if (T->lchild == NULL && T->rchild == NULL)
printf("%c "，T->data); //访问叶子结点
DispLeaf(T->lchild); //输出左子树中的叶子结点
DispLeaf(T->rchild); //输出右子树中的叶子结点
}
}七、二叉树的初始化
template < typename T >
TreeNode < T > * Tree < T > ::Create(T a[], int size, int nodeId, T nullNode) {
if (nodeId >= size || a[nodeId] == nullNode) {
return NULL; // (1)
}
TreeNode < T > * nowNode = GetTreeNode(nodeId); // (2)
nowNode -> val = a[nodeId]; // (3)
nowNode -> left = Create(a, size, nodeId * 2, nullNode); // (4)
nowNode -> right = Create(a, size, nodeId * 2 + 1, nullNode); // (5)
return nowNode; // (6)
}
template < typename T >
void Tree < T > ::CreateTree(T a[], int size, T nullNode) {
root = Create(a, size, 1, nullNode); // (7)
}(1) 如果树结点编号 nodeId 大于等于数组大小 size，或者数组中编号为 nodeId 的元素的值等于空节点值 nullNode，则返回 NULL 表示创建一颗空树。
(2) 通过调用 GetTreeNode 方法获取编号为 nodeId 的树结点。
(3) 将数组中编号为 nodeId 的元素的值赋给当前树结点。
(4) 递归调用 Create 方法创建当前节点的左子结点，其中 nodeId 乘以 2 作为左子结点的编号。
(5) 递归调用 Create 方法创建当前节点的右子结点，其中 nodeId 乘以 2 加 1 作为右子结点的编号。
(6) 返回创建成功的树结点。
(7) 将根结点的指针设置为通过调用 Create 方法创建的树结点。
八、二叉树的前序遍历
template < typename T >
void Tree < T > ::preOrder(TreeNode < T > * node) {
if (node) {
visit(node); // (1)
preOrder(node -> left); // (2)
preOrder(node -> right); // (3)
}
}
template < typename T >
void Tree < T > ::preOrderTraversal() {
preOrder(root); // (4)
}(1) 调用 `visit` 函数访问当前树节点。
(2) 递归调用 `preOrder` 方法遍历当前节点的左子树。
(3) 递归调用 `preOrder` 方法遍历当前节点的右子树。
(4) 调用 `preOrder` 方法遍历根节点，即开始树的前序遍历。
九、二叉树的中序遍历
template < typename T >
void Tree < T > ::inOrder(TreeNode < T > * node) {
if (node) {
inOrder(node -> left); // (1)
visit(node); // (2)
inOrder(node -> right); // (3)
}
}
template < typename T >
void Tree < T > ::inOrderTraversal() {
inOrder(root); // (4)
}(1) 递归调用 `inOrder` 函数遍历当前节点的左子树。
(2) 调用 `visit` 函数访问当前树节点。
(3) 递归调用 `inOrder` 函数遍历当前节点的右子树。
(4) 调用 `inOrder` 函数遍历根节点，即开始树的中序遍历。
十、二叉树的后序遍历
template < typename T >
void Tree < T > ::postOrder(TreeNode < T > * node) {
if (node) {
postOrder(node -> left); // (1)
postOrder(node -> right); // (2)
visit(node); // (3)
}
}
template < typename T >
void Tree < T > ::postOrderTraversal() {
postOrder(root); // (4)
}(1) 递归调用 `postOrder` 函数遍历当前节点的左子树。
(2) 递归调用 `postOrder` 函数遍历当前节点的右子树。
(3) 调用 `visit` 函数访问当前树节点。
(4) 调用 `postOrder` 函数遍历根节点，即开始树的后序遍历。
实际上二叉树还有非递归遍历算法,但是不太好,双O(N)的复杂度,没必要仔细学习他们.
二叉树的高度在cpp里面怎么求?
若二叉树中各结点的值均不相同，则：
由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，
但由先序序列和后序序列却不一定能唯一地确定一棵二叉树。
十一、二叉树的完整源码
#include <iostream>
using namespace std;
template < typename T >
struct TreeNode {
T val;
TreeNode * left;
TreeNode * right;
TreeNode(): val(0), left(NULL), right(NULL) {}
TreeNode(T x): val(x), left(NULL), right(NULL) {}
};
template < typename T >
class Tree {
private:
TreeNode < T > * nodes;
TreeNode < T > * root;
size_t nodeSize;
TreeNode < T > * Create(T a[], int size, int nodeId, T nullNode);
void visit(TreeNode < T > * node);
void preOrder(TreeNode < T > * node);
void inOrder(TreeNode < T > * node);
void postOrder(TreeNode < T > * node);
public:
Tree();
Tree(int maxNodes);
~Tree();
TreeNode < T > * GetTreeNode(int id);
void CreateTree(T a[], int size, T nullNode);
void preOrderTraversal();
void inOrderTraversal();
void postOrderTraversal();
};
template < typename T >
Tree < T > ::Tree() {
nodeSize = 100001;
nodes = new TreeNode < T > [nodeSize];
}
template < typename T >
Tree < T > ::Tree(int maxNodes) {
nodeSize = maxNodes;
nodes = new TreeNode < T > [nodeSize];
}
template < typename T >
Tree < T > ::~Tree() {
delete[] nodes;
}
template < typename T >
TreeNode < T > * Tree < T > ::GetTreeNode(int id) {
return & nodes[id];
}
template < typename T >
void Tree < T > ::visit(TreeNode < T > * node) {
cout << node -> val;
}
template < typename T >
TreeNode < T > * Tree < T > ::Create(T a[], int size, int nodeId, T nullNode) {
if (nodeId >= size || a[nodeId] == nullNode) {
return NULL;
}
TreeNode < T > * nowNode = GetTreeNode(nodeId);
nowNode -> val = a[nodeId];
nowNode -> left = Create(a, size, nodeId * 2, nullNode);
nowNode -> right = Create(a, size, nodeId * 2 + 1, nullNode);
return nowNode;
}
template < typename T >
void Tree < T > ::CreateTree(T a[], int size, T nullNode) {
root = Create(a, size, 1, nullNode);
}
template < typename T >
void Tree < T > ::preOrder(TreeNode < T > * node) {
if (node) {
visit(node);
preOrder(node -> left);
preOrder(node -> right);
}
}
template < typename T >
void Tree < T > ::preOrderTraversal() {
preOrder(root);
}
template < typename T >
void Tree < T > ::inOrder(TreeNode < T > * node) {
if (node) {
inOrder(node -> left);
visit(node);
inOrder(node -> right);
}
}
template < typename T >
void Tree < T > ::inOrderTraversal() {
inOrder(root);
}
template < typename T >
void Tree < T > ::postOrder(TreeNode < T > * node) {
if (node) {
postOrder(node -> left);
postOrder(node -> right);
visit(node);
}
}
template < typename T >
void Tree < T > ::postOrderTraversal() {
postOrder(root);
}
int main()
{
const char nullNpde = '-';
char a[15] = {
nullNpde,
'a',
'b',
'c',
'd',
nullNpde,
'e',
'f',
'g',
'h',
nullNpde,
nullNpde,
nullNpde,
nullNpde,
'i'
};
Tree < char > T(15);
T.CreateTree(a, 15, nullNpde);
T.preOrderTraversal();
cout << endl;
T.inOrderTraversal();
cout << endl;
T.postOrderTraversal();
cout << endl;
return 0;
} 这个题目看看就好不用硬做
//递归算法求所有祖先
bool ancestor1(BiTree T，ElemType x)
{ if (T==NULL)
return false;
else if (T->lchild!=NULL && T->lchild->data==x
|| T->rchild!=NULL && T->rchild->data==x)
{ printf("%c "，T->data);
return true;
}
else if (ancestor1(T->lchild，x) || ancestor1(T->rchild，x))
{ printf("%c "，T->data);
return true;
}
else return false;
}
//后序非递归遍历算法求所有祖先
void ancestor2(BiTree T，ElemType x) //后序非递归遍历算法
{ BiTNode* p = T, * pre = NULL; SqStack st; InitStack(st); //定义一个顺序栈并初始化
while (p != NULL || !StackEmpty(st))
{ if (p) //扫描结点p的所有左下结点并进栈
{ Push(st, p); p = p->lchild; } //结点p进栈 //移动到左孩子
else
{ GetTop(st, p); //取出当前的栈顶结点赋给p
if(p->data==x)
{ Pop(st,p); while(!StackEmpty(st)) Pop(st,p); printf("%c ", p->data); return;}
if (p->rchild && p->rchild != pre)//右子树存在且未被访问
p = p->rchild; //转向处理其右子树
else //右子树不存在或已访问
{ Pop(st, p);
printf("%c ", p->data); //访问结点p
pre = p; //用pre记录刚访问过的结点
p = NULL; //结点访问完后重置p指针
}
}
}
DestroyStack(st);
}
Huffman树
具有最小带权路径长度的二叉树称为哈夫曼树（也称最优树）。
如何根据特征构造哈夫曼树，这个在离散数学中已有记载。
权值越大的叶结点越靠近根结点。权值越小的叶结点越远离根结点。
（1）给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F={T1，T2，…，Tn}。
（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和。
（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中。
（4）重复（2）、（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
实际就是先排序，按照 大小一个一个往上垒即可。
一棵有n个叶子结点的哈夫曼树有2n-1个结点。
规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。权值越大的字符编码越短，反之越长
设通信用的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为 { 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 }，试为这8个字母设计哈夫曼编码，并求出其WPL 。
三叉链表：由于在构造哈夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。所以，每个结点既需知道双亲的信息，又需知道孩子结点的信息。
typedef struct
{
int weight;
int parent,lchild,rchild;
} HTNode, *HuffmanTree;
//哈夫曼树的存储
//HuffmanTree HT = new HTNode[2*n]; //数组HT存储哈夫曼树,0号单元未用
//哈夫曼编码的存储
//n个叶子构成的哈夫曼树的高度最高为n，码长最长为n-1
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
//哈夫曼编码实现
void CreatHuffmanTree (HuffmanTree &HT,int n )
{ int i,m=2*n-1; if(n<=1) return;
HT = new HTNode[m+1]; //数组HT存储哈夫曼树,0号单元未用
for( i=1;i<=m;++i) //初始化
{ HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=0; }
for( i=1;i<=n;++i) cin>>HT[i].weight;
for( i=n+1;i<=m;++i) //构造 Huffman树
{ Select(HT,i-1, s1, s2); //在HT[1..i-1]中选择两个其双亲域为0,且权值最小的结点,并返回它们在HT中的序号s1和s2
HT[s1].parent=i; HT[s2] .parent=i; //表示从F中删除s1,s2
HT[i].lchild=s1; HT[i].rchild=s2 ; //s1,s2分别作为i的左右孩子
HT[i].weight=HT[s1].weight + HT[s2].weight; //权值为左右孩子权值之和
}
}
void Select(HuffmanTree HT,int i,int &s1,int &s2)
{ //在HT[1..i]中选择两个其双亲域为0，且权值最小的结点，并返回它们在HT中的序号s1和s2
int v1 = INFINITY, v2 = INFINITY;
s1 = 0; s2 = 0;
for(int k=1; k<=i; k++)
{ if(HT[k].parent == 0)
if(HT[k].weight < v1)
{ v2 = v1; s2 = s1; v1 = HT[k].weight; s1 = k; }
else if( HT[k].weight < v2 )
{ v2 = HT[k].weight; s2 = k; }
}
}
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{ //从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中
HC=new char *[n+1]; //分配存储n个字符的编码表空间
cd=new char [n]; //分配临时存放编码的动态数组空间
cd[n-1]=’\0’; //编码结束符
for(i=1; i<=n; ++i) //逐个字符求赫夫曼编码
{ start=n-1; //start开始时指向最后，即编码结束符位置
c=i; f=HT[i].parent; //f指向结点c的双亲结点
while(f!=0) //从叶子结点开始向上回溯，直到根结点
{ --start; //回溯一次start向前指一个位置
if (HT[f].lchild= =c) cd[start]=’0’; //结点c是f的左孩子，则生成代码0
else cd[start]=’1’; //结点c是f的右孩子，则生成代码1
c=f; f=HT[f].parent; //继续向上回溯
} //求出第i个字符的编码
HC[i]= new char [n-start]; // 为第i 个字符编码分配空间
strcpy(HC[i], &cd[start])； //将求得的编码从临时空间cd复制到HC的当前行中
}
delete cd; //释放临时空间
} // CreatHuffanCode
题集
1. 单值二叉树
2. 完全二叉树的节点个数
3. 二叉树的前序遍历
4. 二叉树的中序遍历
5. 二叉树的后序遍历
6. 翻转二叉树
7. 从根到叶的二进制数之和
性质
先序遍历
剑指 Offer II 049. 从根节点到叶节点的路径数字之和
中序遍历
后序遍历
层序遍历
剑指 Offer 32 - II. 从上到下打印二叉树 II
剑指 Offer 32 - III. 从上到下打印二叉树 III
构造 && 思维
LCA
多低调：性质里的第四题：[剑指 Offer 28. 对称的二叉树]链接错了，应该是(力扣
wian：性质里的第六题：[剑指 Offer 55 - I. 二叉树的深度]链接错了，应该是力扣
多低调：性质里的倒数第三题：[完全二叉树的节点个数] 链接错了，应该是(力扣
Ivor：后序遍历的第3~4题：二叉树剪枝、剑指offerII二叉树剪枝 链接错了，应该是 力扣 、力扣
Ivor：后序遍历的第五题，统计最高分节点数目 链接错了，应该是 力扣
多低调：先序遍历里的第五题：[1022. 从根到叶的二进制数之和]链接错了，应该是（力扣）
多低调：先序遍历里的第七题：[剑指 Offer II 049. 从根节点到叶节点的路径数字之和]链接错了，应该是（力扣）
多低调：先序遍历里的第九题：【404. 左叶子之和】链接错了，应该是（力扣）
多低调：先序遍历里的第十题：【112. 路径总和】链接错了，应该是（力扣）
多低调：先序遍历里的倒数第二题：【113. 路径总和 II】链接错了，应该是（力扣）
低调：先序遍历里的最后一题：【1448. 统计二叉树中好节点的数目】链接错了，应该是（https://leetcode.cn/problems/count-good-nodes-in-b...）
多低调：中序遍历里的最后一题：【94. 二叉树的中序遍历】链接错了，应该是（力扣）
切糕子：层序遍历里的第二题：[剑指 Offer 32 - I. 从上到下打印二叉树]链接错了，应该是（. - 力扣（LeetCode））
切糕子：层序遍历里的第九题：[二叉树的锯齿形层序遍历]链接错了，应该是（. - 力扣（LeetCode））
切糕子：层序遍历里的倒数第二题：[剑指 Offer II 046. 二叉树的右视图]链接错了，应该是（. - 力扣（LeetCode））
切糕子：构造 && 思维里的第四题：[序列化和反序列化二叉搜索树]链接错了，应该是(. - 力扣（LeetCode））
切糕子：构造 && 思维里的倒数第一题：[从先序遍历还原二叉树]链接错了，应该是(. - 力扣（LeetCode））
切糕子：LCA里的第一题：[剑指 Offer 68 - I. 二叉搜索树的最近公共祖先]链接错了，应该是（. - 力扣（LeetCode））
切糕子：LCA里的第三题：[二叉搜索树的最近公共祖先]链接错了，应该是（. - 力扣（LeetCode））
切糕子：LCA里的第四题：[二叉树的最近公共祖先]链接错了，应该是（. - 力扣（LeetCode））
切糕子：LCA里的倒数第三题：[具有所有最深节点的最小子树]链接错了，应该是（. - 力扣（LeetCode））
切糕子：LCA里的倒数第二题：[最深叶节点的最近公共祖先]链接错了，应该是（. - 力扣（LeetCode））
切糕子：LCA里的倒数第一题：[从二叉树一个节点到另一个节点每一步的方向]链接错了，应该是（. - 力扣（LeetCode））