二叉树基本功能的汇集(C++类实现) - linux编程基础

r=node.tp; //将栈顶的BTreeNode*部分赋给r
if(node.flag==1)
{
cout<data<<" ";
r=0; //表示已经访问了该结点
}
else
{
node.flag=1;
s.push(node);
r=r->rChild;
}
}
}
}

//重载形式
int BTree::BTreeSize()
{
return BTreeSize(root);
}

//求二叉树结点个数的函数
int BTree::BTreeSize(BTreeNode* r)
{
//二叉树的结点个数为左右子树的高度之和再+1
if(r==0) return 0;
else
return 1+BTreeSize(r->lChild)+BTreeSize(r->rChild);
}

//重载形式
int BTree::BTreeLeaves()
{
return BTreeLeaves(root);
}

//求二叉树叶子结点个数的函数
int BTree::BTreeLeaves(BTreeNode* r)
{
//当为空时，返回0；当找到叶子时返回1
if(r==0) return 0;
else
if(r->lChild==0&&r->rChild==0)
return 1;
else
return BTreeLeaves(r->lChild)+BTreeLeaves(r->rChild);
}

//重载形式
int BTree::BTreeHeight()
{
return BTreeHeight(root);
}

//求二叉树高度的函数
int BTree::BTreeHeight(BTreeNode* r)
{
if(r==0) return 0;
else
{
//二叉树的高度为左右子树的最大者+1

int lHei=BTreeHeight(r->lChild);
int rHei=BTreeHeight(r->rChild);
return (lHei>rHei) lHei+1:rHei+1;
}
}

//层次遍历求树高需要利用的新结构
struct LayerBTreeNode
{
BTreeNode* ptr;
int height;
};

//层次遍历求高度
int BTree::layerHeight()
{
queue que;
LayerBTreeNode temp,lTemp,rTemp; //牺牲空间来获得算法的清晰度

BTreeNode* r=getRoot();

int hei=1;
temp.ptr=r;
temp.height=1;
que.push(temp); //先将根对应的LayerBTreeNode对象进队

//不为空时
while(!que.empty())
{
//BTreeNode* btreePtr=0;

temp=que.front(); //取出队首元素
que.pop();

r=temp.ptr;

//用当前的高度跟取出的队首进行比较
if(hei hei=temp.height;

if(r->lChild!=0||r->rChild!=0)
{
//如果它的左右子树不为空，则进队列
if(r->lChild!=0)
{
lTemp.ptr=r->lChild;
lTemp.height=temp.height+1; //在原来高度基础上加1,再入队列
que.push(lTemp);
}
if(r->rChild!=0)
{
rTemp.ptr=r->rChild;
rTemp.height=temp.height+1;
que.push(rTemp);
}

}
}
return hei;
}

二叉树基本功能的汇集(C++类实现)(二)