二叉树
1、定义
binary tree的递归定义：根结点的子树仍然是一棵二叉树，到达空子树的时候递归结束。
2、性质
（1）第i层至多有2^(i-1)个结点
（2）深度为k的二叉树最少有k个结点，最多有2^k-1个结点
（3）对于任一棵非空二叉树，若其叶子结点的个数为N0，度为2的非叶子结点的个数为N2，则有N0=N2+1
（4）具有n个结点的完全二叉树的深度为int_up(log(2,n+1))
（5）
3、特殊二叉树
（1）满二叉树
所有的分支结点都存在左右子树，所有的叶子结点都在同一层。
（2）完全二叉树
对于一棵具有n个结点的二叉树按层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点位置完全相同，则这颗树就是完全二叉树；满二叉树一定是一棵完全二叉树，反之不一定。
4、二叉树c++实现
（1）存储方式
使用顺序存储的空间利用率太低，一般采用的是链式存储的方式，称之为二叉链表；二叉树的结点类如下：
template <typename T>
struct BinTreeNode
{
T data;
BinTreeNode<T> *left,*right;
BinTreeNode():left(NULL),right(NULL){}
BinTreeNode(T x,BinTreeNode<T>* l = NULL ,BinTreeNode<T>* r = NULL):data(x),left(l),right(r){}
} （2）二叉树的遍历
【1】前序遍历：根左右
//递归实现
void PreOrder(BinTreeNode<T>*& root)
{
if(root)
{
cout << root->data << endl;
PreOrder(root->left);
PreOrder(root->right);
}
}
//非递归实现
//使用栈先进后出的存储特性来记录遍历时候的回退路径
//具体而言，为了保证是根左右的顺序，即先左子树后右子树，在进栈的时候先进右子树的结点，后进左子树的，这样出栈的时候刚好是左右的顺序
void PreOrder1(BinTreeNode<T>*& root)
{
stack<BinTreeNode<T>*> s;
BinTreeNode* temp = NULL;
s.push(root);
while(!s.empty())
{
temp = s.top();
s.pop();
cout << temp->data << endl;
if(temp->right)
s.push(temp->right);
if(temp->left)
s.push(temp->left);
}
}
//非递归实现的第二种方式
void PreOrder2(BinTreeNode<T>*& root)
{
BinTreeNode<T>* temp = root;
stack<BinTreeNode<T>*> s;
s.push(NULL);//初始push一个空指针进栈，这样到最后一个没有左右子树的叶子结点的时候，栈里只有一个NULL了，令指针root指向这个NULL就可以结束循环
while(temp)
{
cout << temp->data << endl;
if(temp->right)
s.push(temp->right);//预留右子树指针在栈中
if(temp->left)
temp = temp->left;//进入左子树
else//左子树为空
{
temp = s.top();
s.pop();
}
}
} 【2】中序遍历：左根右 //递归实现
void InOrder(BinTreeNode<T>*& root)
{
if(root)
{
InOrder(root->left);
cout << root->data << endl;
InOrder(root->right);
}
}
//非递归实现
//同样使用栈来记录遍历过程中回退的路径
//如果某结点的右子树为空，就说明以这个节点为根的二叉树遍历完了，此时从栈中退出到更上层的结点并访问它
void InOrder1(BinTreeNode<T>*& root)
{
if(!root)
return;
stack<BinTreeNode<T>*> s;
s.push(root);
while(!s.empty())
{
while(s.top()->left)//左子树依次入栈
{
s.push(s.top()->left);
}
while(!s.empty())
{
BinTreeNode<T>* cur = s.top();
cout << cur->data << endl;
s.pop();
if(cur->right)
{
s.push(cur->right);
break;
}
}
}
}
【3】后序遍历：左右根 //后序遍历的递归实现
void PostOrder(BinTreeNode<T>*& root)
{
if(root)
{
PostOrder(root->left);
PostOrder(root->right);
cout << root->data << endl;
}
}
//非递归实现
void PostOrder1(BinTreeNode<T>*& root)
{
if(!root) return;
stack<BinTreeNode<T>*> s;
s.push(root);
BinTreeNode<T>* last = NULL;
while(!s.empty())
{
while(s.top()->left)//左结点依次入栈，循环遍历到二叉树的最左结点处
s.push(s.top()->left);
while(!s.empty())
{
if(last == s.top()->right || s.top()->right == NULL)//上一次出栈的结点是当前栈顶结点的右节点，或者当前栈顶结点不存在右节点
{
cout << s.top()->data << endl;
last = s.top();
s.pop();
}
else if(s.top()->right)//当前栈顶结点存在右节点，那么右节点压栈
{
s.push(s.top()->right)
break;
}
}
}
} 【4】层序遍历
void levelOrder(BinTreeNode<T>*& root)
{
queue<BinTreeNode<T>*> q;
if(root)
q.push(root);
BinTreeNode<T>* node;
while(!q.empty())
{
node = q.front();
cout << node->data << endl;
q.pop();
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
}
}
（3）二叉树创建
【1】广义表
例如，使用广义表：A(B(D,E(G,)),C(,F))#建立的二叉树：
BinTreeNode<T>* CreatBinTree(string s)
{
stack<BinTreeNode<T>*> s;
BinTreeNode<T>* root = NULL , *p = NULL , *t = NULL;
int k;
for(int i = 0;i < s.length();++i)
{
switch(s[i])
{
case '(':
s.push(p);
k=1;
break;
case ')':
s.pop();
break;
case ',':
k = 2;
break;
default:
p = new BinTreeNode<T>*(ch);
if(root == NULL)
root = p;
else if(k == 1)
t = s.top();t->left = p;
else
t = s.top();t->right = p;
}
}
} 5、线索二叉树
（1）定义
将结点结构进行扩容，如下：ltag和rtag用来指示lchild和rchild存放的是指向孩子结点的指针还是指向前驱结点和后继结点的线索。
（2）结点类
//结点结构
template<typename T>
struct threadNode
{
int ltag,rtag;
treadNode<T>* left,*right;
T data;
threadNode(T x):data(x),left(NULL),right(NULL),ltag(0),rtag(0){}
} （3）二叉树线索化
//利用函数重载来实现中序遍历对创建好的普通二叉树进行线索化
void creatInThread()
{
threadNode<T>* pre = NULL;
if(root != NULL)
{
creatInThread(root,pre);
pre->right = NULL;
pre->rtag = 1;
}
}
void creatInThread(threadNode<T>*& cur,threadNode<T>*& pre)
{
if(!cur == NULL) return;
creatInThread(cur->left , pre);//递归左子树的线索化
if(!cur->left)
{
cur->left = pre;
cur->ltag = 1;
}
if(pre != NULL && pre->right == NULL)
{
pre->right = cur;
pre->rtag = 1;
}
pre = cur;
creatInThread(cur->right , pre);//递归右子树的线索化
} 6、二叉搜索树（二叉查找树、二叉排序树，Binary Search Tree（BST））
（1）定义
（2）性质
【1】二叉搜索树是set和map的底层结构
【2】二叉搜索树用中序遍历输出的序列式升序排列的，如上图的二叉搜素树，用中序遍历输出的话：1,6,10,9，10,12,16,17,18,25
（3）查找操作
Node* Find(const K& val)
{
Node* cur = _root;
while(cur)
{
if(val == cur->_data)
return cur;
else if(val > cur->_data)
cur = cur->right;
else
cur = cur->left;
}
return nullptr;
} 7、平衡二叉树（AVL）---搜索性能的优化
（1）定义
二叉搜索树可以缩短查找的效率，但是如果插入的元素基本有序的话就会退化为单支树，等同于在有序表中查找元素。为了优化这一点，就出现了平衡二叉树AVL，使得无论按照什么次序插入关键码，二叉树的性能都是最佳的。其主要特点如下：
（2）性能分析
8、红黑树（RBT）
（1）定义
（2）性质
