二叉树：每个节点最多两个孩子节点。

二叉树的结构： struct TreeNode

{

DataType _value; //节点值

TreeNode* _left; //左孩子

TreeNode* _ridht; //右孩子

};

二叉树的基础： 构造、拷贝构造、析构、赋值运算符的重载

二叉树的知识点： 高度、节点的个数、子节点的个数

二叉树的遍历： 前序、中序、后序遍历(递归及非递归)

遍历顺序： 前序——根左右 中序——左根右 后序——左右根

注意: 递归遍历时，应该注意不要出现栈溢出现象。

因为++index返回对象，index++返回临时变量，所以传引用做参数时有++index。

#pragmaonce#include<queue>#include<stack>//二叉树的结构template<classT>structBinaryTreeNode{BinaryTreeNode<T>*_left;BinaryTreeNode<T>*_right;T_data;//构造函数BinaryTreeNode(constT&x):_left(NULL),_right(NULL),_data(x){}};template<classT>classBinaryTree{typedefBinaryTreeNode<T>Node;public://构造BinaryTree():_root(NULL){}//a--树的节点前序遍历的数组size--数组中元素个数invaild--无效值即节点为空BinaryTree(constT*a,size_tsize,constT&invalid){size_tindex=0;_root=_CreateTree(a,size,invalid,index);}//析构~BinaryTree(){_Destory(_root);_root=NULL;}//拷贝BinaryTree(constBinaryTree<T>&t){_root=_Copy(t._root);}//赋值重载(传统)//BinaryTree<T>&operator=(constBinaryTree<T>&t)//{//if(this!=&t)//{//Node*tmp=_Copy(t._root);//_Destory(_root);//_root=tmp;//}//return*this;//}//赋值重载(现代)BinaryTree<T>&operator=(BinaryTree<T>t){swap(_root,t._root);return*this;}T&operator->(){return_root;}public:voidPrevOrder()//前序{_PrevOrder(_root);cout<<endl;}voidInOrder()//中序{_InOrder(_root);cout<<endl;}voidPostOrder()//后序{_PostOrder(_root);cout<<endl;}size_tSize()//节点个数{return_Size(_root);}size_tDepth()//树的深度{return_Depth(_root);}size_tLeafSize()//叶子节点个数{return_LeafSize(_root);}//层次遍历voidLevelOrder(){queue<Node*>q;if(_root){q.push(_root);}while(!q.empty()){Node*front=q.front();cout<<front->_data<<"";q.pop();if(front->_left){q.push(front->_left);}if(front->_right){q.push(front->_right);}}cout<<endl;}public://非递归的前中后序遍历（栈）voidPrevOrder_NonR(){stack<Node*>s;if(_root)s.push(_root);while(!s.empty()){Node*top=s.top();cout<<top->_data<<"";s.pop();//栈后进先出，所以右先进，左先出if(top->_right)s.push(top->_right);if(top->_left)s.push(top->_left);}cout<<endl;}voidInOrder_NonR(){//压左树//取出一个节点即它的左路走完了，在访问右树（看作子问题）stack<Node*>s;Node*cur=_root;while(cur||!s.empty()){//压树的左路节点直至最左段节点while(cur){s.push(cur);cur=cur->_left;}if(!s.empty()){Node*top=s.top();s.pop();cout<<top->_data<<"";cur=top->_right;}}cout<<endl;}voidPostOrder_NonR(){Node*prev=NULL;Node*cur=_root;stack<Node*>s;while(cur||!s.empty()){//压树的左路节点直至最左段节点while(cur){s.push(cur);cur=cur->_left;}Node*top=s.top();if(top->_right==NULL||top->_right==prev){cout<<top->_data<<"";s.pop();prev=top;}else{cur=top->_right;}}cout<<endl;}protected://注意此处index要用引用传参Node*_CreateTree(constT*a,size_tsize,constT&invalid,size_t&index){Node*root=NULL;if((index<size)&&(a[index]!=invalid)){root=newNode(a[index]);//注意下面只能用++index。此处传的是引用//因为++index返回对象，index++返回临时变量。root->_left=_CreateTree(a,size,invalid,++index);root->_right=_CreateTree(a,size,invalid,++index);}returnroot;}void_Destory(Node*root){if(root==NULL)return;_Destroy(root->_left);_Destroy(root->_right);deleteroot;}Node*_Copy(Node*root){if(root==NULL)returnNULL;NOde*newRoot=newNode(root->_data);newRoot->_left=_Copy(root->_left);newRoot->_right=_Copy(root->_right);returnnewRoot;}//////////////void_PrevOrder(Node*root){if(root==NULL)return;cout<<root->_data<<"";_PrevOrder(root->_left);_PrevOrder(root->_right);}void_InOrder(Node*root){if(root==NULL)return;_InOrder(root->_left);cout<<root->_data<<"";_InOrder(root->_right);}void_PostOrder(Node*root){if(root==NULL)return;_PostOrder(root->_left);_PostOrder(root->_right);cout<<root->_data<<"";}size_t_Size(Node*root){if(root==NULL)return0;return(_Size(root->_left)+_Size(root->_right)+1);}size_t_Depth(Node*root){if(root==NULL)return0;size_tLeftDepth=_Depth(root->_left);size_tRightDepth=_Depth(root->_right);return(LeftDepth>RightDepth)?(LeftDepth+1):(RightDepth+1);}size_t_LeafSize(Node*root){if(root==NULL)return0;if((root->_left==NULL)&&(root->_right==NULL))return1;return(_LeafSize(root->_left)+_LeafSize(root->_right));}private:Node*_root;};