1.引入的概念：
结点：指树中的一个元素；
结点的度：指结点拥有的子树的个数，二叉树的度不大于2；
树的度：指树中的最大结点度数；
叶子：度为0的结点，也称为终端结点；
高度：叶子节点的高度为1，根节点高度最高；
层：根在第一层，以此类推；
2.树的存储结构：
（1）双亲表示法：以双亲作为索引的关键词的一种存储方式
每个结点只有一个双亲，所以选择顺序存储占主要以一组连续空间存储树的结点，同时在每个结点中，附设一个指示其双亲结点位置的指针域
（2）孩子表示法：类似于单链表的存储方式，指针域内的元素个数有子树个数决定。
（3）孩子兄弟表示法：任意一棵树，他的结点的第一个孩子如果存在就是唯一结点，他的右兄弟如果存在，也是唯一的，因此，可以设置两个指针，分别指向该结点的第一个孩子和该结点的右兄弟
3.特殊的二叉树
二叉树的定义：由一个结点和两颗互不相交、分别称为这个根的左子树和右子树的二叉树构成（递归定义）
（1）二叉树的性质：
1：二叉树的第i层上至多有2^(i-1)个结点
2：深度为k的二叉树，至多有2^k-1个结点
3：在一棵二叉树中,如果叶子结点数为n0,度为2的结点数为n2,则有: n0=n2+1
4：具有n个结点的完全二叉树的深度为 log2n +1
5：对一棵具有n个结点的完全二叉树中从1开始按层序编号,则对于任意的序号为i(1≤i≤n）的结点有：
(1)如果i>1, 则结点i的双亲结点的序号为 i/2;如果i=1, 则结点i是根结点,无双亲
(2)如果2i≤n, 则结点i的左孩子的序号为2i; 如果2i>n,则结点i无左孩子。
(3)如果2i+1≤n, 则结点i的右孩子的序号为2i+1;如果2i+1>n,则结点 i无右孩子。
（2）满二叉树：叶子节点一定要在最后一层，并且所有非叶子节点都存在左孩子和右孩子；
（3）最特别的二叉树：完全二叉树：从左到右、从上到下构建的二叉树；
二叉树的遍历(递归)：
1：先序遍历：根->左子树->右子树（先序）
2：中序遍历：左子树->根->右子树（中序）
3：后序遍历：左子树->右子树->根（后序）
这三种遍历方法只是访问结点的时机不同，访问结点的路径都是一样的，时间和空间复杂度皆为O(n)
4：层序遍历：逐层访问
代码实现：
#include <iostream>
using namespace std;
template<typename T>
struct BiNode
{
T data;
BiNode<T>*lchild;
BiNode<T>*rchild;
};
template<typename T>
class BiTree
{
private:
BiNode<T>*root;
BiNode<T>*Creat();
void Release(BiNode<T>*bt);
void PreOrder(BiNode<T>*bt);
void InOrder(BiNode<T>*bt);
void PostOrder(BiNode<T>*bt);
public:
BiTree(){
root = Creat();
}
~BiTree(){
Release(root);
}
void PreOrder(){
PreOrder(root);
}
void InOrder(){
InOrder(root);
}
void PostOrder(){
PostOrder(root);
}
};
template<typename T>
BiNode<T>*BiTree<T>::Creat()//创建一个二叉树
{
BiNode<T>*bt;
char ch;
cin>>ch;
if(ch=='#')
bt = NULL;
else
{
bt = new BiNode<T>;
bt->data = ch;
bt->lchild = Creat();
bt->rchild = Creat();
}
return bt;
}
template<typename T>
void BiTree<T>::PreOrder(BiNode<T>*bt)//前序遍历
{
if(bt==NULL)
return;
else
{
cout<<bt->data;
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
template<typename T>
void BiTree<T>::InOrder(BiNode<T>*bt)//中序遍历
{
if(bt==NULL)
return;
else
{
InOrder(bt->lchild);
cout<<bt->data;
InOrder(bt->rchild);
}
}
template<typename T>
void BiTree<T>::PostOrder(BiNode<T>*bt)//后序遍历
{
if(bt==NULL)
return;
else
{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
cout<<bt->data;
}
}
前序遍历的非递归实现：
1.栈s初始化（空栈）；
2.循环直到root为空且栈s为空
2.1 当root不空时循环
2.1.1 输出root->data;
2.1.2 将指针root的值保存到栈中；
2.1.3 继续遍历root的左子树（root=root->lchild）
2.2 如果栈s不空，则
2.2.1 将栈顶元素弹出至root（root=s.pop()）；
2.2.2 准备遍历root的右子树(root=root->rchild)；
template <class T>
void BiTree::PreOrder(BiNode<T> *root) {
SeqStack<BiNode<T> *> s;
while (root!=NULL | | !s.empty()) {
while (root!= NULL) {
cout<<root->data;
s.push（root）;
root=root->lchild;
}
if (!s.empty()) {
root=s.pop();
root=root->rchild;
}
}
}
中序遍历的非递归实现
1.栈s初始化（空栈）；
2.循环直到root为空且栈s为空
2.1 当root不空时循环
2.1.1 将指针root的值保存到栈中；
2.1.2 继续遍历root的左子树（root=root->lchild）
2.2 如果栈s不空，则
2.2.1 将栈顶元素弹出至root（root=s.pop()）；
2.2.2 输出root->data;
2.2.3 准备遍历root的右子树(root=root->rchild)；
template <class T>
void BiTree::InOrderwithoutD (BiNode<T> *root)
{
stack< BiNode<T> * > aStack;
}
while(!aStack.empty()||root) {
while(root){
aStack.push(root);
root=root->lchild;
}
if(!aStack.empty()){
root=aStack.top();
aStack.pop();
cout<<root->data;
root=root->rchild;
}
}
}
后序遍历的非递归实现：
1.定义一个栈；从根节点出发开始遍历，p=root，如果，root==NULL, 不进行遍历；
2.无条件进行下面的工作
(1)如果指针不空，指针打上left标记，并将指针进栈，执行（2）;否则，执行（3）
(2)p->lchild,重复(1）
(3)栈顶元素出栈P
(4)查看P的标志，如果标志为right,进行下面的工作，否则，执行（5）
a.访问当前节点P
b.如果栈空 ，算法结束；
c.否则，栈顶元素出栈，转（4）
(5)修改P的标志，让P重新入栈，p=P->rchild,执行2
#include <stack>
Using namespace std;
template<class T>
void BiTree<T>::PostOrderWithoutRecusion(BiTreeNode<T>* root){
StackElement<T> element;
stack<StackElement<T > > aStack;//栈申明
BiTreeNode<T>* pointer;
if(root==NULL)
return;//空树即返回
}
else
pointer=root;
while(true){
while(pointer!=NULL){//进入左子树
element.pointer=pointer;
element.tag=Left; //沿左子树方向向下周游
aStack.push(element);
pointer=pointer->lchild;
}
ement=aStack.pop();
pointer=element.pointer;
while(element.tag==Right){
cout<<pointer->data;
if(aStack.empty()) return;
else{
element=aStack.pop();
pointer=element.pointer;
}//end else
} //endwhile
element.tag=Right;
aStack.push(element);
pointer=pointer->rchild();
}//end while
（5）Huffman编码
Huffman是一种前缀编码；Huffman编码是建立在Huffman树的基础上进行的，因此为了进行Huffman编码，必须先构建Huffman树；树的路径长度是每个叶节点到根节点的路径之和；带权路径长度是（每个叶节点的路径长度*wi）之和；Huffman树是最小带权路径长度的二叉树；
构造Huffman树的过程：
(1)将各个节点按照权重从小到大排序；
(2)取最小权重的两个节点，并新建一个父节点作为这两个节点的双亲，双亲节点的权重为子节点权重之和，再将此父节点放入原来的队列；
(3)重复(2)的步骤，直到队列中只有一个节点，此节点为根节点；