在介绍二叉树之前大家一定要对树有一定的了解，二叉树是一种特殊的树结构，二叉树每个节点最多有两个孩子节点，分别为左孩子和右孩子。
*满二叉树：高度为N的满二叉树有2^n-1个节点的二叉树。
*完全二叉树：若设二叉树的深度为h,除第h层外，其他各层（1~h-1）的节点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树。
*数组存储表示
当在数据处理过程中，二叉树的大小和形态不发生剧烈的动态变化时，可以采用数组的方式来表示二叉树的抽象数据结构类型。
用数组方式存储二叉树结构，就是用一组连续的存储单元存储二叉树的数据元素，为了反映节点在二叉树中的存储位置及相互关系，必须适当安排节点的存储
序。下面用数组来存储一个完全二树和一般二叉树来。
*链表存储表示
根据二叉树定义，可以设计出二叉树节点的构造。二叉树的每个节点至少应该包括三个域：数据data、左子女节点指针和右子女节点指针rightChild,如图（a）所示。这种链
表结构称为二叉树链表，使用这种结构可以很方便地根据节点leftChild指针和rightChild指针找到他的左子女和右子女
*遍历二叉树的方法：
（1）前序遍历（先根遍历）：根节点->左子树->右子树；【123456】
（2）中序遍历：左子树->根节点->右子树；【324165】
（3）后序遍历：左子树->右子树->根节点；【342651】
（4）层序遍历：一层层节点依次遍历。【125346】
当然遍历二叉树的方法不知这些，这只是比较简单的几种。
*代码实现二叉树
#include<iostream> #include<stack> #include<queue> #include<assert.h> using namespace std;
//节点定义 template<class T> struct BinaryTreeNode { T _data;//数据 BinaryTreeNode<T>* _left;//左孩子 BinaryTreeNode<T>* _right;//右孩子 BinaryTreeNode(const T& x) :_data(x) ,_left(NULL) ,_right(NULL) {} }; //定义二叉树 template<class T>
class BinaryTree { typedef BinaryTreeNode<T> Node; public: BinaryTree() :root(NULL) {} BinaryTree(T* a,size_t n,const T&invalid) { size_t index=0; _root=CreateTree(a,n,invalid,index); } Node* _copy(Node* root) { if(root==NULL) return NULL; Node* newRoot=new Node(root->_data); newRoot->_left=_copy(root->_left); newRoot->_right=_copy(root->_right); return newRoot; } BinaryTree(const BinaryTree<T>& t) { _root=_copy(t._root); } BinaryTree<T>& operator=(BinaryTree<T> t) { swap(_root,t._root); return *this; } ~BinaryTree() { Destory(_root); } void Destory(Node* root) { if(root==NULL) return; Destory(root->_left); Destory(root->_right); delete root; } void PrevOrder() { _PrevOrder(_root); cout<<endl; } void InOrder() { _InOrder(_root); cout<<endl; } void PrevOrderNonR() { stack<Node*> s; Node* cur=_root; while(cur||!s.empty()) { while(cur) { cout<<cur->_data<<" "; s.push(cur); cur=cur->_left; } //top从栈取出来表示这个节点的左子树访问过了 //剩余右子树还没有访问，循环子问题访问右数 Node* top=s.top(); s.pop(); //子问题的方式访问右数 cur=top->_right; } cout<<endl; } void InOrderNonR()//非递归实现先序遍历 { Node* cur=_root; stack<Node*> s; while(cur||!s.empty()) { while(cur) { s.push(cur); cur=cur->_left; } Node* top=s.top; s.pop(); cout<<top->_data<<" "; //子问题 cur=top->_right; } } void PostOrderNonR()//非递归实现后序遍历 { Node* cur=_root; stack<Node*> s; Node* prev=NULL; while(cur||!s.empty()) { while(cur) { s.push(cur); cur=cur->_left; } Node* front=s.top(); if(front->_right==NULL||front->_right==prev) { cout<<front->_data<<" "; prev=front; s.pop(); } else { cur=front->_right; } } cout<<endl; } void LevelOrder()//层序遍历 { queue<Node*> q; if(_root) { q.push(_root); } while(!q.empty()) { Node* front=q.front(); cout<<front->_data<<" "; if(front->_left) q.push(front->_left); if(front->_right) q.push(front->_right); q.pop(); } cout<<endl; } size_t Size()//求树的大小 { return _Size(_root); } size_t LeafSize()//求叶子节点的个数 { return _LeafSize(_root); } size_t GetkLeavel(size_t k)//求第K层叶子结点的个数 { assert(k>0); return _GetkLeavel(_root,k); } Node* Find(const T& x)//查找某个节点 { return _Find(_root,x); } size_t Depth()//求1树的深度 { return _Depth(_root); } protected://真正实现的部分 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); } Node* CreateTree(T* a,size_t n,const T& invalid,size_t& index) { Node* root=NULL; if(index<n&&a[index]!=invalid) { root=new Node(a[index]); root->_left=CreateTree(a,n,invalid,++index); root->_right=CreateTree(a,n,invalid,++index); } return root; } size_t _Size(Node* root) { if(root==NULL) { return 0; } return _Size(root->_left)+_Size(root->_right)+1; } size_t _LeafSize(Node* root) { if(root==NULL) { return 0; } if(root->_left==NULL||root->_right==NULL) { return 1; } return _LeafSize(root->_left)+_LeafSize(root->_right); } size_t _GetkLeavel(Node* root,size_t k) { if(root==NULL) { return 0; } if(k==1) { return 1; } return _GetkLeavel(root->_left,k-1)+_GetkLeavel(root->_right,k-1); } size_t _Depth(Node* root) { if(root==NULL) return 0; if(root->_left==NULL&&root->_right==NULL) return 1; size_t left=_Depth(root->_left); size_t right=_Depth(root->_right); return left>right?left+1:right+1; } Node* _Find(Node* root,const T&x) { if(root==NULL) return NULL; if(root->_data==x) return root; Node* ret=_Find(root->_left,x); if(ret) return ret; return _Find(root->_right,x); } protected: Node* _root; }; void TestBinaryTree() { int array[10]={1,2,3,'#','#',4,'#','#',5,6}; BinaryTree<int> t1(array,sizeof(array)/sizeof(array[0]),'#'); t1.PrevOrder(); BinaryTree<int> t2(t1); t2.PrevOrderNonR(); t1.PrevOrderNonR(); t1.PostOrderNonR(); t1.InOrder(); t1.LevelOrder(); cout<<"Size:"<<t1.Size()<<endl; cout<<"kLeavel:"<<t1.GetkLeavel(4)<<endl; cout<<"LeafSize:"<<t1.LeafSize()<<endl; cout<<"Depth:"<<t1.Depth()<<endl; } int main() { TestBinaryTree(); return 0; }
