二叉树是一种树形结构，它每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）。

所谓度是结点拥有的子树数。

对于二叉树，它具有以下的性质：

1、在二叉树的第i层上至多有2^(i-1)个结点（i>=1）。

2、深度为k的二叉树至多有2^k-1个结点。

3、对任何一棵二叉树，如果它的叶子结点个数为n0，度为2的结点为n2，那么m = n + 1;

eg.如果设一个二叉树中度为1的结点个数为n1

故总结点数 N = n0 + n1 + n2; (1)

二叉树除了根结点外，其余结点都有一个分支，设M为分支总数，则 N = M + 1;由于这些分支是由度为1或2的结点射出的，则M = n1 + 2*n2;

则有 N = n1 + 2*n2 + 1 (2)

由（1）（2）得 n0 = n2 + 1;

4、具有n个结点的完全二叉树的深度为∟log 2 n」+1.(其中“∟x」 ”表示不大于x的最大整数)。

5、如果对一棵有n个结点的完全二叉树的结点按层序编号（每一层从左到右，直到∟log 2 n」+1），则对任意一结点i（1=<i<=n）有

（1）如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点∟i/2」.

（2）如果2i>n,则结点i无左右孩子（结点i为叶子结点）否则其左孩子是结点2i；

（3）如果2i+1>n，则结点i无左右孩子；否则其右孩子是结点2i+1；

#pragmaonce#include<queue>#include<stack>#include<iostream>usingnamespacestd;template<classT>structBinaryTreeNode{BinaryTreeNode<T>*_left;BinaryTreeNode<T>*_right;T_data;public:BinaryTreeNode(constT&x):_data(x),_right(NULL),_left(NULL){}};template<classT>classBinaryTree{typedefBinaryTreeNode<T>Node;public:BinaryTree():_root(NULL){}BinaryTree<T>(constT*a,size_tsize,constT&invalid){size_tindex=0;_root=_CreatTree(a,size,index,invalid);}BinaryTree<T>(constBinaryTree<T>&t){_root=_Copy(t._root);}BinaryTree<T>&operator=(BinaryTree<T>t){swap(_root,t._root);return*this;}~BinaryTree(){_Clear(_root);_root=NULL;}voidPrevOrder(){cout<<"先序："<<endl;_PrevOrder(_root);}voidInOrder(){cout<<"中序："<<endl;_InOrder(_root);}voidPostOrder(){cout<<"后序："<<endl;_PostOrder(_root);}//层序//思想：队列//1.先判断根节点是否为NULL//2.如果根节点不为空，节点入队（不是入值）//3.判断队列是否为空，如果不为空，出队//4.判断左右子树节点是否为空，//5.如果不为空，入队左右节点，跳至2voidLeveLorder()//层序{cout<<"层序："<<endl;queue<Node*>tmp;if(_root==NULL)return;else{tmp.push(_root);while(!tmp.empty()){Node*Front=tmp.front();cout<<Front->_data<<"";tmp.pop();if(Front->_left){tmp.push(Front->_left);}if(Front->_right){tmp.push(Front->_right);}}}}size_tSize(){return_Size(_root);}size_tDepth(){_Depth(_root);}size_tLeafSize(){return_leafSize(_root);}protected:Node*_CreatTree(constT*a,size_tsize,size_t&index,constT&invalid){Node*root=NULL;if(a[index]!=invalid&&index<size){root=newNode(a[index]);root->_left=_CreatTree(a,size,++index,invalid);//++index返回indexindex++返回临时变量（在此编译不通过）root->_right=_CreatTree(a,size,++index,invalid);}returnroot;}//先序遍历递归形式void_PrevOrder(Node*root){if(root==NULL)return;cout<<root->_data<<"";_PrevOrder(root->_left);_PrevOrder(root->_right);}//先序遍历非递归借助栈//和层序实现差不多，只是一个是借助队，一个是借助栈void_PrevOrder(Node*root){stack<Node*>cur;if(root==NULL)//1.先判断根结点是否为空return;else{cur.push(root);//2,压栈while(!cur.empty())//3.判断栈是否为空，不为空，先压右再压左子树{Node*temp=cur.top();cout<<temp->_data<<"";cur.pop();if(temp->_right){cur.push(temp->_right);}if(temp->_left){cur.push(temp->_left);}}}}//中序遍历递归形式void_InOrder(Node*root){if(root==NULL)return;_InOrder(root->_left);cout<<root->_data<<"";_InOrder(root->_right);}//中序遍历非递归借助栈void_InOrder(Node*root){Node*cur=root;stack<Node*>tack;while(cur||!tack.empty()){while(cur){tack.push(cur);cur=cur->_left;}if(!tack.empty()){Node*Top=tack.top();tack.pop();cout<<Top->_data<<"";cur=Top->_right;}}}//后序遍历递归形式void_PostOrder(Node*root){if(root==NULL)return;_PostOrder(root->_left);_PostOrder(root->_right);cout<<root->_data<<"";}//后序遍历非递归借助栈void_PostOrder(Node*root){Node*prev=NULL;Node*cur=root;stack<Node*>tmp;while(cur||!tmp.empty()){while(cur){tmp.push(cur);cur=cur->_left;}Node*Top=tmp.top();if(Top->_right==NULL||Top->_right==prev){cout<<Top->_data<<"";tmp.pop();prev=Top;cur=NULL;}else{cur=Top->_right;}}}void_Size(Node*root){if(root==NULL)return0;return_Size(root->_left)+_Size(root->_right)+1;}size_t_Depth(Node*root){if(root==NULL)return0;intleftdepth=_Depth(root->_left);intrightdepth=_Depth(root->_right);returnleftdepth>rightdepth?leftdepth+1:rightdepth+1;}size_t_leafSize(Node*root){staticsize_tsize=0;if(root==NULL)return0;if(root->_left==NULL&&root->_right==NULL){++size;returnsize;}_leafSize(root->_left);_leafSize(root->_right);returnsize;}void_Clear(Node*root){if(root){_Clear(root->_left);_Clear(root->_right);deleteroot;}}Node*_Copy(Node*root){if(root==NULL){returnNULL;}Node*tem=newNode(root->_data);tem->_left=_Copy(root->_left);tem->_right=_Copy(root->_right);returntem;}private:Node*_root;};