#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
typedef char ElemType;//定义二叉树结点值的类型为字符型
const int MaxLength=10;//结点个数不超过10个
typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;
void CreateBiTree(BiTree &T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树
// if(T) return;
char ch;
ch=getchar(); //不能用cin来输入，在cin中不能识别空格。
if(ch==' ') T=NULL;
else{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) coutlchild);
CreateBiTree(T->rchild);
}
}
void PreOrderTraverse(BiTree T){//先序遍历
if(T){
coutlchild);
coutrchild);
cout0)
{ top--; p=stack[top]; p=p->rchild; }
}
}
}
//非递归的中序遍历算法
void NRInOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top];coutrchild; }
}
}
}
//非递归的后序遍历算法
/*bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。
需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈
(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。
首先将bt和tag(为1)入栈，遍历左子树；
返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。*/
typedef struct
{
BiTree ptr;
int tag;
}stacknode;
void NRPostOrder(BiTree bt)
{
stacknode s[MaxLength],x;
BiTree p=bt;
int top;
if(bt!=NULL){
top=0;p=bt;
do
{
while (p!=NULL) //遍历左子树
{
s[top].ptr = p;
s[top].tag = 1; //标记为左子树
top++;
p=p->lchild;
}
while (top>0 && s[top-1].tag==2)
{
x = s[--top];
p = x.ptr;
cout0)
{
s[top-1].tag =2; //遍历右子树
p=s[top-1].ptr->rchild;
}
}while (top>0);}
}//PostOrderUnrec
int BTDepth(BiTree T){//求二叉树的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}
int Leaf(BiTree T){//求二叉树的叶子数
if(!T) return 0;
else if(!T->lchild&&!T->rchild) return 1;
else return(Leaf(T->lchild)+Leaf(T->rchild));
}
int NodeCount(BiTree T){//求二叉树的结点总数
if(!T) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
} |
转播
