树无疑是数据结构中占着举足轻重的地位，因此需要细嚼慢咽。
比如满二叉树，完全二叉树，线索二叉树，遍历二叉树，AVL树（平衡二叉树），BST树（二叉排序树），B树，B+树，赫夫曼树，堆排序，树形选择排序以及有关图的知识！

鉴于二叉树的应用型，对于树只做知识梳理：

• 树的结点：一个数据元素及若干指向其子树的分支

• 结点的度：结点拥有的子树数

• 叶子或终端结点：度为0的结点

• 分支结点或非终端结点：度不为0的结点

• 树的度：树内各结点的度的最大值

• 孩子和双亲：结点的子树的根称为该结点的孩子，该结点的孩子的双亲

• 兄弟：同一个双亲的孩子之间互称兄弟

• 子孙：以某结点为根节点的任意节点都称为该结点的子孙

• 堂兄弟：其双亲在同一层的结点

• 层次：结点的层次从根开始定义起，根为第一层

• 深度：树中结点的最大层次

• 有序树和无序树：树中结点的各子树看成从左到右是有次序的，否则为无序树

二叉树：binary tree，每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，不能任意颠倒

二叉树五种基本形态：（我没找到图啊对8起）

• 空树
• 只有一个根节点
• 根节点+左子树
• 根节点+右子树
• 根节点+左子树+右子树

二叉树的性质：

• 在二叉树的第i层至多有2**（i-1）个结点（i >= 1）;
• 深度为k的二叉树至多有2**k -1个结点（k >= 1）;
• 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1；
  一棵深度为k且有2的k次方 -1个结点的二叉树叫做满二叉树；
  深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树
• 具有n个结点的完全二叉树的深度为[log2**n] + 1;
• 如果i=1，则无双亲结点；如果i>1，则双亲结点为[i/2]

二叉树的存储结构
顺序存储结构：

#define MAXSIZE 100
typedef TElemType SqBiTree[MAXSIZE];
SqBiTree bt;

链式存储结构（划重点！链式用的最多！）

typedef struct BiTree {
	ElemType data;
	struct BiTree *lchild, *rchild;
}BiTNode, *BiTree;

遍历二叉树（traversing binary tree）

先序遍历：

• 访问根节点
• 访问左子树
• 访问右子树

// 根节点，左子树，右子树
void PreOrder(BiTree T) {
	if(T!=NULL) {
        visit(T);
        // 此处是递归
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
// 打印出该结点的数据域
void visit(BiTree T) {
	std::cout << T->data << std::endl;
}

中序遍历

• 访问左子树
• 访问根节点
• 访问右子树

// 左子树，根节点，右子树
void InOrder(BiTree T) {
	if(T!=NULL) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

后序遍历

• 访问左子树
• 访问右子树
• 访问根节点

// 右子树，左子树，根节点
void PostOrder(BiTree T) {
	if(T!=NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

除此之外，此处再介绍两种遍历方法

中序遍历非递归算法（上述三个遍历均为递归）

• 初始时一次扫描根节点的所有左侧结点并将它们一一进栈
• 出栈一个结点，访问他
• 扫描该结点的右孩子结点并将其进栈
• 一次扫描右孩子结点的所有左侧结点并一一进栈
• 反复该过程直到栈空为止

void InOrder(BiTree T) {
	stack<BiTree> S;		// 初始化一个栈存放树的结点
	BiTree P = T;		// 复制这个二叉树的地址，以便后面可以找到这个二叉树的根节点
	while (P || !S.empty()) {
		if (P) {
			S.push(P);		// 进栈
			P = P->lchild;
		}
		else {
			P = S.top();		// 返回栈顶元素
			S.pop();
			P = P->rchild;
		}
	}
}

层次遍历

• 初始将跟入队并访问根节点，然后出队
• 若有左子树，则将左子树的根入队
• 若有右子树，则将右子树的根入队
• 然后出队，访问该结点
• 反复该过程直到队列为空为止

#include <queue>
void levelOrder(BiTree T) {
    queue<BiTree> q;
    Bitree p;
    q.push(p);
    while(!q.emtpy()) {
        q.pop(p);
        if(p->lchild != nullptr) {
            q.push(p->lchild);
        }
        if(p->rchild != nullptr) {
            q.push(p->rchild);
        }
    }
}

线索二叉树遍历二叉树是以一定规则将二叉树中农结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列，这实质上是对一个非线性结构进行线性操作，使每一个结点在这些线性序列中有且只有一个直接前驱和直接后继，但是在存储结构中，不能直接得到结点在某一序列中的前驱和后继信息，如何在遍历中保存前驱和后继信息？
在每个结点上加上两个指针域，分布指示前驱和后继信息，
如图的存储结构，叫做线索链表，其中指向前驱和后继的指针，叫做线索，对二叉树的以某种遍历使其变成线索二叉树的过程就做线索化

其中：（前指左，右指后）

• LTag = 0：lchild域指示结点的左孩子

• LTag = 1：lchild域指示结点的前驱

• LTag = 0：rchild域指示结点的右孩子

• LTag = 1：rchild域指示结点的后继

typedef struct BiThrNode {
	TElemType data;
	struct BiThrNode *lchild, *rchild;
	int ltag, rtag;
}BiThrNode, *BiThrTree;

中序线索二叉树线索化：先来回忆下，中序遍历：左根右，正常情况下，左子树是根节点的前驱结点，根节点是右子树的前驱结点

// p指该结点，pre值该结点的前驱结点
void InThread(ThreadTree& p, ThreadTree& pre) {
	if (p != NULL) {
		InThread(p->lchild, pre);
		// 要注意此处，对没有左孩子，左指针指向前驱结点是
		// 在此处进行，但是对没有右孩子，右指针指向后继结点
		// 是在下一个结点完成的，也就是在下一个结点完成上一个结点的事情
		if (p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL && pre->rchild == NULL) {
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
		InThread(p->rchild, pre);
	}
}
void CreateInThread(ThreadTree T) {
	ThreadTree pre = NULL;
	if (T != NULL) {
		InThread(T, pre);
		pre->rchild = NULL;
		pre->rtag = 1;
	}
}

树的存储结构：不做概述

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

赫夫曼树（最优二叉树）：含有n个带权叶子结点带权路径长度最小的二叉树

基本概念：

• 路径长度：路径上所经历边的个数
• 结点的权：结点被赋予的数值
• 树的带权路径长度：WPL，树中所有叶结点的带权路径长度之和

构造方法：

• 将n个结点作为n棵仅含有一个根节点的二叉树，构成森林F；
• 生成一个新结点，并从F中找出根节点权值最小的两棵树作为他的左右子树，且新结点的权值为两棵根节点的权值之和
• 从F中删除这两个树，并将新生成的树加入到F中；
• 重复2,3步骤，直到F中只有一棵树为止

哈夫曼树的性质：

• 每个初始结点都会成为叶结点，双支结点都为新生成的结点
• 权值越大离根节点越近，反之权值越小离根节点越远
• 哈夫曼树中没有结点的度为1
• n个叶子结点的哈夫曼树的结点总数为2n-1，其中度为2的结点数为n-1

赫夫曼树的应用（这个有必要讲一下子）：前缀编码

原编码：
在可变编码中，不可进行编码的认识

用赫夫曼树编码后，如下：没有任何一个编码是其他编码的前缀

回溯法和树的遍历

二叉排序树（BST树）

平衡二叉树（AVL树）

B树

B+树