树
二叉树的性质：
（1）二叉树的第i(i≥1)层最多有2^(i-1)个结点.
（2）深度为k（根节点的深度为1）的二叉树最多有2^k-1个结点.
（3）叶子的数目=度为2的结点数目+1.
满二叉树的性质：
（1）n个结点的满二叉树的深度=log2(n+1)
（2）顺序编号的满二叉树的性质：结点i的左小孩是结点2i；结点i的右小孩是结点2i+1；结点i的双亲是结点int(i/2)；结点i的层号int(log2 i)+1.
完全二叉树：
深度为k的有n个结点的二叉树,当且仅当每一个结点都与同深度的满二叉树中编号从1至n的结点一一对应。
二叉搜索树：
左子结点总是小于根结点，右子结点总是大于根结点。用中序遍历得到的结果是从小到大排序的。
面试题：3种遍历的6种实现方法；广度优先与深度优先；堆与红黑树
1、3种遍历的6种实现方法
#include<stdio.h> //printf，scanf需要的头文件 #include<stdlib.h> //malloc需要的头文件 #include "conio.h" //exit需要的头文件 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
//前序遍历 void PreOrderTraverse(BiTree T) { if(T==NULL) return; printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } //中序遍历 void InOrderTraverse(BiTree T) { if(T==NULL) return; InOrderTraverse(T->lchild); printf("%c",T->data); InOrderTraverse(T->rchild); } //后序遍历 void PostOrderTraverse(BiTree T) { if(T==NULL) return; PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c",T->data); }
前序遍历的非递归算法思路：从根节点开始，输出当前结点。遇到左结点不为空的情况，就输出当前结点，并把结点压栈。如果左结点为0，就转而搜索它的右结点，并把该结点出栈，说明该结点的左右结点已经全部被搜索过了。如果所有结点的左右结点结点都被搜索过，则搜索结束。
或者：首先将根结点入栈。弹出栈顶结点，输出结点值。将当前结点的右结点入栈，再将左结点入栈。循环知道栈为空。
中序遍历的非递归算法思路：从根结点开始，把当前结点压栈。如果其左结点存在，就把左结点压栈，继续向左搜索。遇到其左结点不存在的情况，输出当前结点值后，转而搜索它的右结点。并且要把该结点出栈，证明当前结点及左右结点都已经被访问过。
后续遍历的非递归算法思路：从根结点开始，把当前结点压栈。如果当前结点没有子节点或者是子节点已经被访问过了，则输出该结点的值，并且将该结点出栈。否则，如果它的左结点或者右结点存在，则按先右后左的方式压栈。
//前序遍历非递归 void PreOrderTraverse_t(BiTree T) { stack<BiTNode*> s; BiTNode* p=T; while(p!=NULL||!s.empty()) { while(p!=NULL) { printf("%c",p->data); s.push(p); p=p->lchild; } if(!s.empty()) { p=s.top(); s.pop(); p=p->rchild; } } } //中序遍历非递归 void InOrderTraverse_t(BiTree T) { stack<BiTNode*> s; BiTNode* p=T; while(p!=NULL||!s.empty()) { while(p!=NULL) { s.push(p); p=p->lchild; } if(!s.empty()) { p=s.top(); s.pop(); printf("%c",p->data); p=p->rchild; } } } //后续遍历非递归 void PostOrderTraverse_t(BiTree T) { stack<BiTNode*> s; BiTNode* cur=T; BiTNode* pre=NULL; s.push(T); while(!s.empty()) { cur=s.top(); if((cur->lchild==NULL&&cur->rchild==NULL)||(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild))) //如果当前点没有做结点并且没有右结点，或者是左右结点被访问过，则输出当前结点的值 { printf("%c",cur->data); //如果pre==cur->rchild，可以cur可以被输出了，因为如果一个点的右支已经被输出过了，就应该立刻输出当前点了。如果pre==cur->lchild，是因为右支不存在。左支已输出，并且右支不存在的情况下，则将当前点输出。 s.pop(); pre=cur; } //否则，左右支不全为空或者pre!=cur->lchild&&pre!=cur->rchild的情况下，说明当前结点的左右子结点还没有被访问过，则应该继续入栈。
else { if(cur->rchild!=NULL) s.push(cur->rchild); if(cur->lchild!=NULL) s.push(cur->lchild); } } }
2.广度搜索与深度搜索
广度优先搜索：层序遍历。按每一层从左到右的顺序输出。
用队列的思想来解决：将根结点压入队列。如果队列不为空，弹出队列的首结点，并输出该结点。如果该结点的左右子结点存在，就把左右结点依次压入队列中。
//层序遍历。用队列的思想解决 void LevelOrderTraverse(BiTree T) { if(T==NULL) return; queue<BiTNode*> q; q.push(T); while(q.size()) { BiTNode* pNode=q.front(); q.pop(); printf("%c",pNode->data); if(pNode->lchild!=NULL) q.push(pNode->lchild); if(pNode->rchild!=NULL) q.push(pNode->rchild); } }
深度优先搜索：就是前序遍历。
3.根据前序遍历结果和中序遍历结果构建二叉树（剑指offer面试题6）
思想：前序遍历的第一个点是根结点。在中序遍历中，根结点左边的为左子树的中序遍历结果，根结点右边的为右子树的中序遍历结果。中序遍历左子树结点的个数N_left，右子树的结点为N_right。那么在前序遍历结果中，紧挨着跟结点的N_left个结点为左字数的前序遍历结果，剩下的为右子树的前序遍历结果。然后递归分别构建左子树和右子树。