二叉树的定义：
是一颗空树或者具有以下性质
1.结点最多只有两个孩子，且有左右之分。不能交换左右孩子
2.结点点的左子树和右子树也是二叉树。
例图
二叉树的基本形态：
二叉树中的术语：
1).结点度：节点所拥有的字数的个数成为该节点的度，在二叉树中度的取值只能是0,1,2.
2).叶节点：度为0的节点成为叶结点或终端结点。
3).左孩子、右孩子、双亲：树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。
4).路径、路径长度：如果一棵树的一串结点n1,n2,…,nk有如下关系：结点ni是ni+1的父结点（1≤i<k）,就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。
5).结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
6).树的深度：树中所有结点的最大层数称为树的深度。
7).满二叉树。 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。
8).完全二叉树。一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为 i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左 部。
二叉树的性质：
1).非空二叉树叶子结点数等于度为2的结点数加1，即N0=N2+1.（其中N0和N2分别是叶结点和度为2结点的个数）。
2).非空二叉树第K层上最多有 2^(k - 1)个结点(K>= 1).
3).高度为H的节点，最多有2^H - 1个节点(H >= 1).
二叉树的基本操作：
1 #include <iostream> 2 #include <stack> 3 #include <vector> 4 #include <deque> 5 /* 6 以下为二叉树的常用操作 7 采用二叉链表的存储结构 8 */ 9 #define DataType char 10 11 typedef struct BiTNode //二叉树的节点 12 { 13 DataType m_Value; 14 BiTNode *m_pLeft; 15 BiTNode *m_pRight; 16 }BiTNode; 17 18 //创建二叉树 19 void createBiTree(BiTNode * &pCurrent) 20 { 21 cout << "先序输入节点："; 22 DataType value; 23 cin >> value ; 24 if(value == ‘#‘) 25 pCurrent = NULL; 26 else 27 { 28 pCurrent = (BiTNode *)malloc(sizeof(BiTNode)); 29 pCurrent->m_Value = value; 30 createBiTree(pCurrent->m_pLeft); 31 createBiTree(pCurrent->m_pRight); 32 } 33 34 } 35 36 //递归实现前序遍历二叉树 37 void preOrderVisitUseRecur(const BiTNode * pCurrent) 38 { 39 if(pCurrent) 40 { 41 cout << pCurrent->m_Value; 42 preOrderVisitUseRecur(pCurrent->m_pLeft); 43 preOrderVisitUseRecur(pCurrent->m_pRight); 44 } 45 } 46 47 //用栈，不用递归实现前序排列 48 void preOrderVisitUseStack(const BiTNode * pCurrent) 49 { 50 stack<const BiTNode *> pNodeStack; 51 const BiTNode *p = pCurrent; 52 while(p||!pNodeStack.empty()) 53 { 54 if(p) //如果该节点不是NULL 55 { 56 cout << p->m_Value; //访问节点的值 57 pNodeStack.push(p); //将节点压栈 58 p = p->m_pLeft; 59 } 60 else 61 { 62 //如果该节点是NULL 63 p = pNodeStack.top(); //获取栈顶元素 64 pNodeStack.pop(); //删除栈顶元素 65 p = p->m_pRight; //访问右节点 66 } 67 68 } 69 } 70 71 //递归实现中序遍历 72 void inOrderVisitUseRecur(const BiTNode * pCurrent) 73 { 74 if(pCurrent) 75 { 76 inOrderVisitUseRecur(pCurrent->m_pLeft); 77 cout << pCurrent->m_Value; 78 inOrderVisitUseRecur(pCurrent->m_pRight); 79 } 80 } 81 //用栈实现中序遍历 82 void inOrderVisitUseStack(const BiTNode * pCurrent) 83 { 84 stack<const BiTNode *> pNodeStack; 85 const BiTNode * p = pCurrent; 86 while(p||!pNodeStack.empty()) 87 { 88 if(p) //如果该节点不是NULL 89 { 90 pNodeStack.push(p); //将节点压栈 91 p = p->m_pLeft; 92 } 93 else 94 { 95 //如果该节点是NULL 96 p = pNodeStack.top(); //获取栈顶元素 97 pNodeStack.pop(); //删除栈顶元素 98 cout << p->m_Value; //访问节点的值 99 p = p->m_pRight; //访问右节点 100 } 101 } 102 } 103 104 //递归实现后序遍历 105 void afterOrderVisitUseRecur(const BiTNode * pCurrent) 106 { 107 if(pCurrent) 108 { 109 afterOrderVisitUseRecur(pCurrent->m_pLeft); 110 afterOrderVisitUseRecur(pCurrent->m_pRight); 111 cout << pCurrent->m_Value; 112 } 113 } 114 115 //用栈实现后序遍历 116 void afterOrderVisitUseStack(const BiTNode * pCurrent) 117 { 118 stack<const BiTNode *> pNodeStack1; 119 stack<const BiTNode *> pNodeStack2; 120 const BiTNode * p =pCurrent; 121 while(p||!pNodeStack1.empty()) 122 { 123 if(p) //如果该节点不是NULL 124 { 125 pNodeStack1.push(p); //将节点压栈 126 pNodeStack2.push(p); //将节点压栈 127 p = p->m_pRight; 128 } 129 else 130 { 131 //如果该节点是NULL 132 p = pNodeStack1.top(); //获取栈顶元素 133 pNodeStack1.pop(); //删除栈顶元素 134 p = p->m_pLeft; //访问左节点 135 } 136 } 137 p = NULL; 138 while(!pNodeStack2.empty()) 139 { 140 p = pNodeStack2.top(); //获取栈顶元素 141 pNodeStack2.pop(); //删除栈顶元素 142 cout << p->m_Value; 143 } 144 } 145 /* 146 //按层次进行遍历,代码有点问题，但是思想绝对正确。 147 void levelOrderVisit(const BiTNode *pCurrent) 148 { 149 deque<const BiTNode *> pNodedeue; 150 const BiTNode * p = NULL; 151 if(pCurrent) 152 { 153 pNodedeue.push_back(pCurrent); //第一次将节点放到队列 154 } 155 while(!pNodedeue.empty()||p) 156 { 157 p = *pNodedeue.begin(); //返回队列首元素，但不删除 158 pNodedeue.pop_front(); //删除队首元素 159 if(p) 160 { 161 cout << p->m_Value; 162 if(p->m_pLeft) 163 pNodedeue.push_back(p); //左孩子不空则进入队列 164 if(p->m_pRight) 165 pNodedeue.push_back(p); //右孩子不空则进入队列 166 } 167 } 168 } 169 */ 170 //计算树的深度 171 int getTreeDepth(const BiTNode * pCurrent) 172 { 173 int leftDepth = 0,rightDepth = 0; 174 if(!pCurrent) 175 { 176 //空的话返回0 177 return 0; 178 } 179 else 180 { 181 leftDepth = getTreeDepth(pCurrent->m_pLeft); //获得左子树的高度 182 rightDepth = getTreeDepth(pCurrent->m_pRight); //获得右子树的高度 183 return (leftDepth>rightDepth?leftDepth:rightDepth) + 1; 184 } 185 } 186 //计算树节点的个数 187 int coutTreeNodeNums(const BiTNode *pCurrent) 188 { 189 int leftNums,rightNums; 190 if(!pCurrent) 191 { 192 return 0; 193 } 194 else 195 { 196 leftNums = coutTreeNodeNums(pCurrent->m_pLeft); 197 rightNums = coutTreeNodeNums(pCurrent->m_pRight); 198 } 199 return leftNums + rightNums + 1; 200 } 201 int main() 202 { 203 BiTNode * root = NULL; 204 cout << "start to create a tree:" << endl; 205 createBiTree(root); 206 cout << "visit a tree use 递归先序:" << endl; 207 preOrderVisitUseRecur(root); 208 cout << endl; 209 cout << "visit a tree use 栈先序:" << endl; 210 preOrderVisitUseStack(root); 211 cout << endl; 212 cout << "visit a tree use 递归中序:" << endl; 213 inOrderVisitUseRecur(root); 214 cout << endl; 215 cout << "visit a tree use 栈中序:" << endl; 216 inOrderVisitUseStack(root); 217 cout << endl; 218 cout << "visit a tree use 递归后序:" << endl; 219 afterOrderVisitUseRecur(root); 220 cout << endl; 221 cout << "visit a tree use 栈后序:" << endl; 222 afterOrderVisitUseStack(root); 223 cout << endl; 224 //cout << "层次遍历：" << endl; 225 //levelOrderVisit(root); 226 cout << "树中节点的个数：" << coutTreeNodeNums(root) << endl; 227 cout << "树的深度为：" << getTreeDepth(root) << endl; 228 return 0; 229 }
原文：http://www.cnblogs.com/zhuwbox/p/3632802.html