添加：
前序遍历、中序遍历、后续遍历都利用了递归结构，形式简洁。层序遍历，没有递归，利用一个队列作为辅助工具。
步骤如下：
1、判断根节点是否为空，不为空入队列
2、判断队列是否为空，若不为空，获取队列首内容，并弹出，判断弹出的节点左右（注意先左后右）节点是否为空，不为空，则入队列
3、重复执行2，直至队列为空
一、定义
满二叉树：在一棵二叉树中，所有的叶子节点都在最后一层，除了叶子节点外的其他节点出度都为2。
完全二叉树：在一棵树中，所有的叶子节点都在最后两层，而且倒数第二层的叶子节点靠右侧连续排列，倒数第一层的叶子节点靠左侧连续排列。
满二叉树必然是完全二叉树，反之则不然。
二、二叉树性质
（根节点在第一层，编号为1）
1、在二叉树的第i层，最多有2i-1个节点。
2、深度为k的二叉树，总共最多有2k-1个节点。
3、对任何一棵二叉树，如果其叶子节点为n0，度为2的节点为n2，则n0=n2+1。
4、具有n个节点的完全二叉树，深度为(log2n)+1，向下取整。
5、对于一棵有n个节点的完全二叉树的节点按层编号i（根节点为1），从左往右。
a)如果i=1，是根节点，无双亲。i>1，它的双亲节点是i/2，向下取整。
b)如果2i>n，i节点没有左孩子，故肯定也没有右孩子；2i<=n，则i节点的左孩子是2i。
c)如果2i+1>n，i节点没有右孩子；2i+1<=n，则i节点的右孩子是2i+1。
三、二叉树的创建和遍历
1、遍历
几种遍历方式的记忆方式：一个遍历涉及3个节点，父节点、左孩子节点、右孩子节点，前中后遍历的是指父节点的在3个节点中访问的次序。
a)、前序遍历
父->左->右
b)、中序遍历
左->父->右
c)、后续遍历
左->右->父
d)、层序遍历
逐层，从左往右
2、创建
创建是基于遍历实现的，现只给出按照前序遍历方式创建二叉树。
a)将二叉树先变成“扩展二叉树”，就是所有空指针指向的内容为“#”
b)将扩展二叉树按照前序遍历，将树变成一个内容序列
c)按照前序遍历方式依次读入内容，并创建
3、代码
#include<iostream> #include<queue> using namespace std; typedef struct btnode { char data; struct btnode *lchild; struct btnode *rchild; }btnode, *BiTree; /* 输入序列： AB#D##C## 平衡二叉树 AB#D#E##C## 非平衡二叉树 */ void frontCreat(BiTree *T) { char temp; cin >> temp; if (temp == '#') { *T = NULL; } else { *T = (btnode*)malloc(sizeof(btnode)); (*T)->data = temp; frontCreat(&((*T)->lchild)); frontCreat(&((*T)->rchild)); } } void frontPrint(BiTree T) { if (T == NULL) return; cout << T->data << " "; frontPrint(T->lchild); frontPrint(T->rchild); } void midPrint(BiTree T) { if (T == NULL) return; midPrint(T->lchild); cout << T->data << " "; midPrint(T->rchild); } void backPrint(BiTree T) { if (T == NULL) return; backPrint(T->lchild); backPrint(T->rchild); cout << T->data << " "; } void cengPrint(BiTree T) { static queue<btnode *> q; if (T == NULL) return; q.push(T); while (!q.empty()) { btnode *temp = q.front(); cout << temp->data << " "; q.pop(); if (temp->lchild != NULL) q.push(temp->lchild); if (temp->rchild != NULL) q.push(temp->rchild); } } int main() { BiTree T; frontCreat(&T); cout << "前序遍历" << endl; frontPrint(T); cout << endl; cout << "中序遍历" << endl; midPrint(T); cout << endl; cout << "后序遍历" << endl; backPrint(T); cout << endl; cout << "层序遍历" << endl; cengPrint(T); system("pause"); return 0; }