数据结构-二叉树的递归实现

二叉树的概念篇>

(1).二叉树是一颗特殊的树,二叉树每个结点最多有两个孩子结点,即就是左孩子和右孩子

(2).满二叉树：若一颗树的高度为h,则h层均满

(3).完全二叉树：若一棵树的高度为h,则前h-1层均满最后一层可以不满,且最后一层的结点都连续集中在最左边. 我们知道一个数组可以表示一颗树,它的思想是如果该处有结点则直接将该结点放在对应的下标处，如果没有结点则以符号占位 

(1).假若一个子结点的下标为i,那仫它的父节点的下标为:(i-1)/2;

(2).假若一个父结点的下标为i，那仫它的左孩子的下标为:2*i+1,它的右孩子的下标为:2*i+2.

(3).缺点：如果不是满二叉树和完全二叉树则有太多的内存浪费，且插入删除不便. 用数组表示一个树适用于满二叉树和完全二叉树.

实例分析篇>

如果一个数组表示的二叉树:int array={1,2,’#’,3,’#’,’#’,4,5,’#’,6,’#’,7,’#’,’#’,8},’#’代表该位置没有结点，该树被还原之后为: 递归求一个树的前序遍历，中序遍历，后序遍历，层序遍历,树的叶子节点的数量，树的总结点的数量，树的深度，统计每一层的结点总数.

(1).前序遍历：先访问根结点，再递归访问左子树，最后访问右子树.

(2).中序遍历：先访问左子树，再访问根结点，最后访问右子树.

(3).后序遍历：先访问左子树，再访问右子树，最后访问根结点.

(4).层序遍历：一层层结点依次遍历，在实现层序遍历的时候用到了队列先进先出的性质,将每一层的数据一次进队列，而每次出队列的元素就是层序遍历的当前元素.

(5).树的总结点数：根结点+左子树的结点数+右子树的结点数.

(6).树的叶子节点数:叶子节点(即没有左子树也没有右子树),左子树的叶子节点总数+右子树的叶子节点总数.

代码实现>,

BinaryTree.h

#pragma once template struct BinaryTreeNode { BinaryTreeNode(const T& data=T()) :_data(data) ,_left(NULL) ,_right(NULL) {} T _data; BinaryTreeNode *_left; BinaryTreeNode *_right; }; template class BinaryTree { typedef BinaryTreeNode Node; public: BinaryTree() :_root(NULL) {} BinaryTree(const T *array,size_t size,const T& invalid) { size_t index=0; _root=_CreatTree(array,size,index,invalid); } BinaryTree(const BinaryTree& bt) { _root=_Copy(bt._root); } //BinaryTree& 
operator=(const BinaryTree& bt) //{ // //传统的写法 // if (this != &bt) // { // Node *root=_Copy(bt._root); // _Destroy(_root); // _root=root; // } // return *this; //} BinaryTree& operator=(const BinaryTree& bt) { //现代的写法 if (this != &bt) //防止自赋值 { BinaryTree tmp(bt); std::swap(_root,tmp._root); } return *this; } ~BinaryTree() { _Destroy(_root); } public: void PrevOrder() //前序遍历 { _PrevOrder(_root); cout<<endl; } void InOrder() //中序遍历 { _InOrder(_root); cout<<endl; } void PostOrder() //后序遍历 { _PostOrder(_root); cout<<endl; } void LevelOrder() //层序遍历 { _LevelOrder(_root); cout<<endl; } size_t Size() //求该树的总结点数 { size_t size=_Size(_root); return size; } size_t Depth() //求该树的深度 { size_t depth=_Depth(_root); return depth; } size_t LeafSize() //求一个树叶子节点的总数 { size_t leaf=_LeafSize(_root); return leaf; } size_t GetKLevel(int level) //level层的所有节点的个数 { size_t count=_GetKLevel(_root,level); return count; } protected: Node *_CreatTree(const T *array,size_t size,size_t& index,const T& invalid) { assert(array); Node *root=NULL; if (index < size && array[index] != invalid) { root=new Node(array[index]); root->_left=_CreatTree(array,size,++index,invalid); root->_right=_CreatTree(array,size,++index,invalid); } return root; } Node *_Copy(Node *root) { //proot是拷贝的新树的根节点 Node *cur=root; Node *proot=NULL; if (cur) { proot=new Node(cur->_data); proot->_left=_Copy(cur->_left); proot->_right=_Copy(cur->_right); } return proot; } void _Destroy(Node *root) { Node *cur=root; if (cur) { _Destroy(cur->_left); _Destroy(cur->_right); delete cur; cur=NULL; } } protected: void _PrevOrder(Node *root) { Node *cur=root; if (cur) { cout<_data<<” “; _PrevOrder(root->_left); _PrevOrder(root->_right); } } void _InOrder(Node *root) { Node *cur=root; if (cur) { _InOrder(cur->_left); cout<_data<<” “; _InOrder(cur->_right); } } void _PostOrder(Node *root) { Node *cur=root; if (cur) { _PostOrder(cur->_left); _PostOrder(cur->_right); cout<_data<<” “; } } void _LevelOrder(Node *root) { queue<Node > q; Node \cur=root; q.push(cur); while(!q.empty()) { Node *t=q.front(); cout<_data<<” “; if (t->_left != NULL) { q.push(t->_left); } if (t->_right != NULL) { q.push(t->_right); } q.pop(); } } size_t _Size(Node *root) { if (root == NULL) { return 0; //空树 } return 1+_Size(root->_left)+_Size(root->_right); } size_t _Depth(Node *root) { Node *cur=root; if (root == NULL) { return 0; } return 1+(_Depth(cur->_left)>_Depth(cur->_right) ?_Depth(cur->_left):_Depth(cur->_right)); } size_t _LeafSize(Node *root) { Node *cur=root; if (cur == NULL) //空树 { return 0; } else if ((cur->_left == NULL) && (cur->_right == NULL)) { //叶子结点–一个结点即没有左子树也没有右子树 return 1; } else return _LeafSize(cur->_left)+_LeafSize(cur->_right); } size_t _GetKLevel(Node *root,int level) { size_t count=0; if (root == NULL) { return 0; } if (level == 1) { count++; } else { count += _GetKLevel(root->_left,level-1); count += _GetKLevel(root->_right,level-1); } return count; } protected: Node *_root; }; [/cpp] test.cpp [cpp] void testBinaryTree() { int array[]={1,2,’#’,3,’#’,’#’,4,5,’#’,6,’#’,7,’#’,’#’,8}; size_t sz=sizeof(array)/sizeof(array[0]); BinaryTree bt(array,sz,’#’); bt.PrevOrder(); //1 2 3 4 5 6 7 8 bt.InOrder(); //2 3 1 5 6 7 4 8 bt.PostOrder(); //3 2 7 6 5 8 4 1 bt.LevelOrder(); //1 2 4 3 5 8 6 7 cout<<bt.Size()<<endl; //8 cout<<bt.Depth()<<endl; //5 BinaryTree bt1(bt); bt1.PrevOrder(); bt1.InOrder(); bt1.PostOrder(); bt1.LevelOrder(); cout<<bt1.Size()<<endl; //8 cout<<bt1.Depth()<<endl; //5 BinaryTree bt2; bt2=bt; bt2.PrevOrder(); bt2.InOrder(); bt2.PostOrder(); bt2.LevelOrder(); cout<<bt2.Size()<<endl; //8 cout<<bt2.Depth()<<endl; //5 cout<<bt2.LeafSize()<<endl; //3 //该树的每一层共有多少个结点 cout<<bt2.GetKLevel(1)<<endl;; //1 cout<<bt2.GetKLevel(2)<<endl;; //2 cout<<bt2.GetKLevel(3)<<endl;; //3 cout<<bt2.GetKLevel(4)<<endl;; //1 cout<<bt2.GetKLevel(5)<<endl;; //1 }