1.二叉树的概念
二叉树是一种树型结构，每个节点至多有两个子结点，或者称两个子树，左子树和右子树。树的顶点成为根节点，终端节点称为叶子节点。节点拥有的子树个数称为节点的度。二叉树得深度可以理解为树得层数。
2.二叉树的性质
在二叉树的第i层，至多有2^（i - 1）个节点，一颗深度为k的二叉树最多有2^k - 1个节点。
对于任何一个二叉树T来说，其度为0的节点的个数等于度为2的节点个数＋1，即n0 ＝ n2 ＋ 1. 设节点总个数为n，n等于度为0，度为1，度为2的节点个数的和，n ＝ n0 ＋ n1 ＋ n2. 又每一个度为2的节点连接了2个节点，每一个度为1的节点连接了1个节点，根节点没有上层节点，所以 n ＝ 2 ＊ n2 ＋ n1 ＋ 1. 两个等式代换得 n0 ＝ n2 ＋ 1.
一颗深度为k且又2^k －1个节点的二叉树称为满二叉树。深度为k有n个节点的二叉树，当满足每一个节点的编号与满二叉树中1-n的节点编号相同，称之为完全二叉树。
有n个节点的完全二叉树，其深度k满足 2^(k-1) - 1 < n <= 2^k - 1.
3.二叉树的存储方式
1.顺序存储方式，将二叉树从上到下，从左到右依次将编号为i的节点存入顺序存储结构，但是这个只是用于完全二叉树。
2.链式存储结构，一个数据元素和两个指向子结点的指针。
4.二叉树的遍历
- 先（根）序遍历：先访问根节点，在访问左子树，最后访问右子树。
- 中（根）序遍历：先访问左子树，在访问根节点，最后访问右子树。
- 后（根）序遍历：先访问左子树，在访问右子树，最后访问根节点。
void createBTree(BTree *T){
char a;
cin >> a;
if(a == '#') T = NULL;
else{
T = new BTree(a);
createBTree(T -> left);
createBTree(T -> right);
}
}
5.线索二叉树
二叉树的遍历是将节点以一定的规则来输出，当用二叉链表做存储结构时，只能查找到节点的左右子节点信息，而无法查找到节点的前驱和后继节点，只有在动态操作时才能得到。为了可以得到节点的前驱后继信息，设计出一种新的数据结构，有n个节点的二叉树肯定有n＋1个空链域，利用这个空链域来存放前驱后继节点。
void InOrderThreading(BTree *T){
if(!T) return;
BTree * head = new BTree(), *pre = head;
head -> ltag = 0;
head -> rtag = 1;
head-> right = head;
if(!T) head -> left = head;
else{
head -> left = T;
InThreading(T);
pre -> right = head;
pre -> rtag = 1;
head -> right = pre;
}
}
void InThreading(BTree* T){
if(T){
InThreading(T -> left);
if(!T -> left) {T -> ltag = 1; T -> left = pre;}
if(!pre -> right) {pre -> rtag = 1; pre -> right = T;}
pre = T;
InThreading(T -> right);
}
}
遍历线索二叉树也和一般中序不同，我们得到一个节点后，只要去遍历它的后继节点就行了。
void InOrder_T(BTree* T){
BTree *p = T -> left;
while(p != T){
while(p -> ltag == 0) p = p -> left;
show(p -> data);
while(p -> rtag == 1 && p -> right != T){
p = p -> right;
show(p -> data);
}
p = p -> right;
}
}