输出二叉树所有叶结点C++
希望各位高手哥哥姐姐帮帮忙啊````
参考答案://///////////////////////
////////简易二叉树///////
//////作者:baihacker//////
/////时间:11.12.2006/////
/////////////////////////
/*
说明:
1.root为第一层
2.节点左节点和右节点层数为当前节点层数加1
3.同一层最左边的元素为第一个
4.同一层,某元素为空,在计数时占一个位置
*/
/*
template<class T>
int BinTree<T>::sumleaf()
{
if (IsNull()) return 0;
return sumleaf(root);
}
template<class T>
int BinTree<T>::sumleaf(TreeNode<T>* curr)
{
if (curr==NULL) return 0;
if (curr->Left==NULL && curr->Right==NULL)
return 1;
return sumleaf(curr->Left)+sumleaf(curr->Right);
}
*/
/*为你所需要的函数,进行如下改动
template<class T>
int BinTree<T>::sumleaf()
{
if (IsNull()) return 0;
return sumleaf(root);
}
template<class T>
int BinTree<T>::sumleaf(TreeNode<T>* curr)
{
if (curr==NULL) return 0;
if (curr->Left==NULL && curr->Right==NULL)
{
输出结点curr的数据;
return 1;
}
return sumleaf(curr->Left)+sumleaf(curr->Right);
}
*/
#include <iostream>
#include <deque>
#include <stack>
using namespace std;
#ifndef BINTREE_H
#define BINTREE_H
template<class T>
class BinTree;
enum LeftRight
{
_Left = 0,
_Right
};
template<class T>
class TreeNode
{
friend class BinTree<T>;
private:
TreeNode* Left;
T data;
TreeNode* Right;
public:
TreeNode(T d):Left(NULL),Right(NULL),data(d){};
};
template<class T>
class BinTree
{
TreeNode<T>* root;
TreeNode<T>* GetParent(int,int,LeftRight&);
public:
BinTree():root(NULL) {};
~BinTree(){deltree();};
bool IsNull(){return root==NULL;}
bool Insert(const T&, int, int);//插入字符,层数,位置
void inorder();
void inorder(TreeNode<T>* curr);
void preorder();
void preorder1();
void preorder(TreeNode<T>* curr);
void postorder();
void postorder(TreeNode<T>* curr);
void view();
int sumnode();
int sumnode(TreeNode<T>* curr);
int sumleaf();
int sumleaf(TreeNode<T>* curr);
void deltree();
void deltree(TreeNode<T>* curr);
};
template<class T>
TreeNode<T>* BinTree<T>::GetParent(int row, int pos, LeftRight& left_right)
{
unsigned long maxpos = 1;
for (int k=0;k<row-1;k++)
maxpos+=maxpos;
if( pos<1 || pos > maxpos) return NULL;
TreeNode<T>* temp;
temp = root;
for (int i=2;i<row;i++)
{
maxpos/=2;
if (pos<=maxpos)
{
if (temp->Left==NULL)
return NULL;
temp = temp->Left;
}
else
{
if (temp->Right==NULL)
return NULL;
temp = temp->Right;
pos -= maxpos;
}
}
if (pos==1)
left_right = _Left;
else
left_right = _Right;
return temp;
}
template<class T>
bool BinTree<T>::Insert(const T& data, int row, int pos)
{
if (IsNull())
{//空树插入
TreeNode<T>* newnode =new TreeNode<T>(data);
root = newnode;
return true;
}
else
if (row==1)
{
return false;
}
else
if (row==2)
{
TreeNode<T>* newnode =new TreeNode<T>(data);
if (pos==1)
root->Left = newnode;
else
root->Right = newnode;
return true;
}
else
{
LeftRight lr;
TreeNode<T>* s;
s = GetParent(row, pos, lr);
if (s==NULL)
return false;
if (lr==_Left)
{
if(s->Left!=NULL)
return false;
TreeNode<T>* newnode =new TreeNode<T>(data);
s->Left = newnode;
return true;
}
if (lr==_Right)
{
if(s->Right!=NULL)
return false;
TreeNode<T>* newnode =new TreeNode<T>(data);
s->Right = newnode;
return true;
}
}
return false;
}
template<class T>
void BinTree<T>::inorder()
{
inorder(root);
cout<<endl;
}
template<class T>
void BinTree<T>::inorder(TreeNode<T>* curr)
{
if (curr!=NULL)
{
inorder(curr->Left);
cout<<curr->data;
inorder(curr->Right);
}
}
template<class T>
void BinTree<T>::preorder()
{
preorder(root);
cout<<endl;
}
template<class T>
void BinTree<T>::preorder(TreeNode<T>* curr)
{
if (curr!=NULL)
{
cout<<curr->data;
preorder(curr->Left);
preorder(curr->Right);
}
}
template<class T>
void BinTree<T>::postorder()
{
postorder(root);
cout<<endl;
}
template<class T>
void BinTree<T>::postorder(TreeNode<T>* curr)
{
if (curr!=NULL)
{
postorder(curr->Left);
postorder(curr->Right);
cout<<curr->data;
}
}
template<class T>
void BinTree<T>::view()
{
if (IsNull()) return;
deque<TreeNode<T>*> q;
TreeNode<T>* temp;
q.push_back(root);
while(!q.empty())
{
temp = q.front();
q.pop_front();
cout<<temp->data;
if (temp->Left!=NULL)
q.push_back(temp->Left);
if (temp->Right!=NULL)
q.push_back(temp->Right);
}
cout<<endl;
}
template<class T>
int BinTree<T>::sumnode()
{
if (IsNull()) return 0;
return sumnode(root);
}
template<class T>
int BinTree<T>::sumnode(TreeNode<T>* curr)
{
if (curr==NULL) return 0;
if (curr->Left==NULL && curr->Right==NULL)
return 0;
return 1+sumnode(curr->Left)+sumnode(curr->Right);
}
template<class T>
int BinTree<T>::sumleaf()
{
if (IsNull()) return 0;
return sumleaf(root);
}
template<class T>
int BinTree<T>::sumleaf(TreeNode<T>* curr)
{
if (curr==NULL) return 0;
if (curr->Left==NULL && curr->Right==NULL)
return 1;
return sumleaf(curr->Left)+sumleaf(curr->Right);
}
template<class T>
void BinTree<T>::deltree()
{
if (IsNull()) return;
deltree(root);
}
template<class T>
void BinTree<T>::deltree(TreeNode<T>* curr)
{
if (curr==NULL) return;
deltree(curr->Left);
deltree(curr->Right);
delete curr;
}
template<class T>
void BinTree<T>::preorder1()
{
if (IsNull()) return;
stack<TreeNode<T>*> s;
TreeNode<T>* temp;
s.push(root);
while(s.size()>0)
{
temp = s.top();
s.pop();
cout<<temp->data;
if (temp->Right!=NULL)
s.push(temp->Right);
if (temp->Left!=NULL)
s.push(temp->Left);
}
cout<<endl;
}
#endif