二叉树的一些基本知识：
二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
定义
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二 叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；
对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
相关术语
双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；
兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；
祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙
结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；
二叉树性质
(1) 在非空二叉树中，第i层的结点总数不超过
, i>=1；
(2) 深度为h的二叉树最多有
个结点(h>=1)，最少有h个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果I>1，则其父结点的编号为[I/2](取下)；
如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；
如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。
二叉树的顺序存储
对于完全二叉树，结点的层次顺序反映了其结构，可按层次顺序给出一棵完全二叉树结点的编号。
可以利用一维数组A来存储一棵含有n个结点的完全二叉树。
A[1]存储二叉树的根结点，
A[i]存储二叉树编号为i的结点，
A[i]的左孩子（若存在）存放在A[2i]处，
A[i]的右孩子（若存在）存放在A[2i+1]处。
二叉树相关算法的实验验证代码：
1 #include 2 #include "stdio.h" 3 #include 4 #include 5 #include 6 using namespace std; 7 8 typedef struct Node 9 { 10 char data;//数据域 11 struct Node *left,*right;//左孩子，右孩子指针域 12 }node; 13 14 /*void C(char a) 15 { 16 cout<<"OK"< < data< left); 47 FirstRoot1(t->right); 48 } 49 /*else 50 cout<<"#"< S; 57 node* p=t; 58 loop: while(p!=NULL) 59 { 60 S.push(p); 61 cout< data< left; 63 } 64 /*if(p==NULL) 65 cout<<"#"< right; 73 goto loop; 74 75 } 76 //中根遍历（递归） 77 void BinaryTree::MiddleRoot1(node *t) 78 { 79 /*if(t==NULL) 80 cout<<"#"< left); 84 cout< data< right);} 86 } 87 //中根遍历（非递归） 88 void BinaryTree::MiddleRoot2(node *t) 89 { 90 stack S; 91 node* p=t; 92 loop: while(p!=NULL) 93 { 94 S.push(p); 95 p=p->left;//压栈不输出数据，弹栈输出数据，先压根节点，再压左孩子结点，弹栈输出后，再压右孩子结点 96 } 97 /*if(p==NULL) 98 cout<<"#"< data< right;107 goto loop;108 }109 //后根遍历（递归）110 void BinaryTree::LastRoot1(node *t)111 {112 /*if(t==NULL)113 cout<<"#"< left);118 LastRoot1(t->right);119 cout< data< left压入栈，同时将0压入栈，准备遍历其左子树。127 2.如果i=1，此时表明已经遍历完p的左子树，将p压入栈，同时将i=2压入栈；若p的右孩子不为空，则将p->right压入栈，同时将0压入栈，准备遍历其右子树。128 3.如果i=2，此时已经遍历完p的右子树，访问结点p129 130 本段代码采用两个辅助堆栈来实现131 */132 void BinaryTree::LastRoot2(node *t)133 {134 node* p;135 int i;136 if(t==NULL)137 {138 /*cout<<"#"< Sa;//二叉树的结点栈141 stack Sb;//辅助判断参数i的栈142 Sa.push(t);143 Sb.push(0);//先把根节点和0入栈144 while((!Sa.empty())&&(!Sb.empty()))145 {146 //先弹栈，然后对判断系数i进行判断147 p=Sa.top();Sa.pop();148 i=Sb.top();Sb.pop();149 if(i==0)150 {151 Sa.push(p);152 Sb.push(1);153 if(p->left!=NULL)154 {155 Sa.push(p->left);156 Sb.push(0);157 }158 /*else159 cout<<"#"< right!=NULL)166 {167 Sa.push(p->right);168 Sb.push(0);169 }170 /*else171 cout<<"#"< data< Q;189 node* p=t;190 if(p!=NULL)191 Q.push(p);192 while(!Q.empty())193 {194 p=Q.front();195 Q.pop();196 cout< data< left!=NULL)198 Q.push(p->left);199 if(p->right!=NULL)200 Q.push(p->right);201 }202 203 }204 //寻找父节点205 node* BinaryTree::Father(node *t,node *p)206 {207 node* q,*qL,*qR;208 if(t==NULL)209 {210 q=NULL;211 return q;212 }213 if(t->left==p||t->right==p)214 {215 q=t;216 return q;217 }218 qL=Father(t->left,p);//递归判断，t的左子树是否是所给结点的父节点219 if(qL!=NULL)220 {221 q=qL;222 return q;223 }224 else225 {226 qR=Father(t->right,p);//递归判断，t的右子树是否是所给结点的父节点227 q=qR;228 return q;229 230 }231 232 }233 //寻找符合数据域的点234 node* BinaryTree::Find(node *t,char item)235 {236 node* q,*p;237 if(t==NULL)238 {239 q=NULL;240 return q;241 }242 if(t->data==item)243 {244 q=t;245 return q;246 }247 p=Find(t->left,item);248 if(p!=NULL){q=p;return q;}//如果不空，即为所求解，如果空，则向右搜索249 q=Find(t->right,item);250 return q;251 }252 //输入拓展先根序列创建二叉树253 node* BinaryTree::InputByExtend(node *p)254 {255 256 char a;257 258 cin>>a;259 if(a=='#')260 {261 p=NULL;262 return p;263 }264 else265 {266 p=new node;267 p->data=a;268 }269 //构建左子树270 p->left=InputByExtend(p->left);271 //构建右子树272 p->right=InputByExtend(p->right);273 return p;274 275 276 }277 //删除某个节点及其左右子树278 void BinaryTree::DelTwo(node *t)279 {280 node *p,*q;281 if(t==NULL)282 return;283 if(t==root)284 {285 Del(t);root=NULL;return;286 }287 p=t;288 //寻找t的父节点q289 q=Father(root,p);290 //修改q的指针域291 if(q->left==p)292 q->left=NULL;293 if(q->right==p)294 q->right=NULL;295 //删除p及其子树296 Del(p);297 298 }299 //递归删除释放300 node* BinaryTree::Del(node *p)301 {302 if(p==NULL) return p;303 //递归删除304 Del(p->left);305 Del(p->right);306 delete [] p;307 }308 //输出当前树形309 //暴力手工输出，只能输出前三行，象征性表示310 void BinaryTree::TreeShow(node* t)311 {312 313 if(t==NULL){cout<<"该二叉树不存在，无树形可言"< left,*q=t->right;315 cout<<"*****"< data<<"*****"< data;321 cout<<"*****";322 if(q==NULL)323 cout<<"*";324 else325 cout< data;326 cout<<"**"< left,*p2=p->right;332 if(p1!=NULL)333 cout< data<<"*";334 else335 cout<<"**";336 if(p2!=NULL)337 cout< data<<"*";338 else339 cout<<"**";340 }341 else342 cout<<"****";343 cout<<"**";344 if(q!=NULL)345 {346 if(q->left!=NULL)347 cout< left->data<<"*";348 if(q->left==NULL)349 cout<<"**";350 if(q->right!=NULL)351 cout< right->data<<"*"< right==NULL)353 cout<<"**"< >a;371 while(a!=0)372 {373 cout< >b;387 if(b==1)388 {cout<<"当前二叉树的树形为："< < <<"先根遍历（递归）的序列为："< < >a;409 node *p,*q;410 p=tree.Find(tree.root,a);411 if(p==tree.root)412 {cout<<"所查询的结点为根节点，无父结点"< < data< >a;423 node *p,*q;424 p=tree.Find(tree.root,a);425 if(p!=NULL)426 {427 cout<<"查询成功！"< data< left!=NULL)435 cout<<"所查询结点的左孩子结点的数据为："< left->data< right!=NULL)439 cout<<"所查询结点的右孩子结点的数据为："< right->data< >b;458 node*p;459 460 p=tree.Find(tree.root,b);461 462 tree.DelTwo(p);463 464 cout<<"删除成功，删除后的树形为："< >a;480 cout<
View Code
, i>=1； 
个结点(h>=1)，最少有h个结点； 