二叉树是每个节点最多有两个子节点的有序树。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。
二叉树的第i层至多有2^(i -1)个节点；
深度为k的二叉树至多有2^k - 1个节点；
对任何一颗二叉树，若其终端节点数为n0,度为2的节点数为n2,则 n0 = n2 + 1;
------------------------------------------------------------------------------------------------------------------------------------------------------------
二叉树的中序遍历：顾名思义，先访问左节点，再访问根节点，最后访问右节点。中序遍历的特点需要使用到栈这种先进后出的数据结构。
首先还是定义二叉树这种链式存储结构的结构体：
typedef struct BiTNode{ char data; struct BiTNode* lchild, *rchild; }BiTNode, *BiTree;
创建二叉树的过程：
void CreateBiTree(BiTree &T) // 创建二叉树 { char data; scanf("%c", &data); if(data == '#'){ // '#'表示空节点 T = NULL; } else { T = (BiTree)malloc(sizeof(BiTNode)); T->data = data; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } }
------------------------------------------------------------------------------------------------------------------------------------------------------------
递归遍历是比较容易理解的：
void MidOrder(BiTree T) // 中序递归遍历 { if(T != NULL) { MidOrder(T->lchild); visit(T); MidOrder(T->rchild); } }
///
非递归遍历：
和先序非递归遍历差不多只不过根节点的输出顺序不一样。
1.一直遍历到左子树最下边，边遍历边保存根节点到栈中,
2.出栈，然后输出，再进入右子树，开始新的一轮左子树遍历。
程序代码：
#include<iostream> #include<iomanip> #include<stack> #include<malloc.h> using namespace std; typedef struct BiTNode{ char data; BiTNode *lchild, *rchild; }BTNode, *BiTree;
void CreateBiTree(BiTree & T) // 先序遍历的方式创建二叉树 { char data; cin>>data; if(data == '#') { T = NULL; } else { T = ( BiTree)malloc(sizeof(BiTNode)); T->data = data; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } //中序遍历 void InOrder(BTNode* root) { //空树 if (root == NULL) return; //树非空 BTNode* p = root; stack<BTNode*> s; while (!s.empty() || p) { //一直遍历到左子树最下边，边遍历边保存根节点到栈中 while (p) { s.push(p); p = p->lchild; } //当p为空时，说明已经到达左子树最下边，这时需要出栈了 if (!s.empty()) { p = s.top(); s.pop(); cout << setw(4) << p->data; //进入右子树，开始新的一轮左子树遍历(这是递归的自我实现) p = p->rchild; } } } int main() { BiTree T; CreateBiTree(T); InOrder(T); return 0; }
