/////////////////////////
////////简易二叉树///////
//////作者:baihacker//////
/////时间:11.12.2006/////
/////////////////////////
/*
说明:
1.root为第一层
2.节点左节点和右节点层数为当前节点层数加1
3.同一层最左边的元素为第一个
4.同一层,某元素为空,在计数时占一个位置
*/
/*
template
int BinTree::sumleaf()
{
if (IsNull()) return 0;
return sumleaf(root);
}
template
int BinTree::sumleaf(TreeNode* curr)
{
if (curr==NULL) return 0;
if (curr->Left==NULL && curr->Right==NULL)
return 1;
return sumleaf(curr->Left)+sumleaf(curr->Right);
}
*/
/*为你所需要的函数,进行如下改动
template
int BinTree::sumleaf()
{
if (IsNull()) return 0;
return sumleaf(root);
}
template
int BinTree::sumleaf(TreeNode* curr)
{
if (curr==NULL) return 0;
if (curr->Left==NULL && curr->Right==NULL)
{
输出结点curr的数据;
return 1;
}
return sumleaf(curr->Left)+sumleaf(curr->Right);
}
*/
#include
#include
#include
using namespace std;
#ifndef BINTREE_H
#define BINTREE_H
template
class BinTree;
enum LeftRight
{
_Left = 0,
_Right
};
template
class TreeNode
{
friend class BinTree;
private:
TreeNode* Left;
T data;
TreeNode* Right;
public:
TreeNode(T d):Left(NULL),Right(NULL),data(d){};
};
template
class BinTree
{
TreeNode* root;
TreeNode* 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* curr);
void preorder();
void preorder1();
void preorder(TreeNode* curr);
void postorder();
void postorder(TreeNode* curr);
void view();
int sumnode();
int sumnode(TreeNode* curr);
int sumleaf();
int sumleaf(TreeNode* curr);
void deltree();
void deltree(TreeNode* curr);
};
template
TreeNode* BinTree::GetParent(int row, int pos, LeftRight& left_right)
{
unsigned long maxpos = 1;
for (int k=0;kRight==NULL)
return NULL;
temp = temp->Right;
pos -= maxpos;
}
}
if (pos==1)
left_right = _Left;
else
left_right = _Right;
return temp;
}
template
bool BinTree::Insert(const T& data, int row, int pos)
{
if (IsNull())
{//空树插入
TreeNode* newnode =new TreeNode(data);
root = newnode;
return true;
}
else
if (row==1)
{
return false;
}
else
if (row==2)
{
TreeNode* newnode =new TreeNode(data);
if (pos==1)
root->Left = newnode;
else
root->Right = newnode;
return true;
}
else
{
LeftRight lr;
TreeNode* s;
s = GetParent(row, pos, lr);
if (s==NULL)
return false;
if (lr==_Left)
{
if(s->Left!=NULL)
return false;
TreeNode* newnode =new TreeNode(data);
s->Left = newnode;
return true;
}
if (lr==_Right)
{
if(s->Right!=NULL)
return false;
TreeNode* newnode =new TreeNode(data);
s->Right = newnode;
return true;
}
}
return false;
}
template
void BinTree::inorder()
{
inorder(root);
coutRight);
}
coutRight==NULL)
return 0;
return 1+sumnode(curr->Left)+sumnode(curr->Right);
}
template
int BinTree::sumleaf()
{
if (IsNull()) return 0;
return sumleaf(root);
}
template
int BinTree::sumleaf(TreeNode* curr)
{
if (curr==NULL) return 0;
if (curr->Left==NULL && curr->Right==NULL)
return 1;
return sumleaf(curr->Left)+sumleaf(curr->Right);
}
template
void BinTree::deltree()
{
if (IsNull()) return;
deltree(root);
}
template
void BinTree::deltree(TreeNode* curr)
{
if (curr==NULL) return;
deltree(curr->Left);
deltree(curr->Right);
delete curr;
}
template
void BinTree::preorder1()
{
if (IsNull()) return;
stack s;
TreeNode* temp;
s.push(root);
while(s.size()>0)
{
temp = s.top();
s.pop();
coutRight!=NULL)
s.push(temp->Right);
if (temp->Left!=NULL)
s.push(temp->Left);
}
cout |
转播
