C++:1.设计算法求二叉树的结点个数2.设计算法按前序次序打印二叉树中的叶子结点3.设计算法求二叉树的深度

Question

C++程序设计
1.设计算法求二叉树的结点个数
2.设计算法按前序次序打印二叉树中的叶子结点
3.设计算法求二叉树的深度

Answer 1

同学，你们老师和我们老师留的作业是一模一样的阿，我有现成的做好了的程序，调试成功。这个程序的难点就在于这种很别扭的输入形式，所以我为它设计了一个结构体形式存放输入内容，再将它转化成了线性结构。

#include <iostream.h>
#include <stdlib.h>

struct inform /*建立输入信息结构体inform*/
{ char data;

int l;

int r;

int signl; /*作为标记的signl,signr*/

int signr;
};

struct leafnode /*建立叶子节点结构体*/
{
char leaf;

leafnode* lchild;

leafnode* rchild;

};

void print(inform* ps, int n);

void judge ( inform* ps );

leafnode* creatree(); /*声明二叉树的建立函数*/

void preorder (leafnode* T); /*声明先序遍历函数*/

void inorder (leafnode* T); /*声明中序遍历函数*/

void postorder (leafnode* T); /*声明后序遍历函数*/

char a[100];

int k=1;
int s=0;

inform *p;

void main()
{
/*-------------------------------按格式输入信息-----------------------------------*/

int n;

cout<<"请输入二叉树内容：第一行为节点总数n ，后面的n行是节点的具体形式："<<endl;

cout<<"n= ";

cin>>n;

p=(inform* )malloc( n*sizeof(inform) ); /*开辟的一个叶子结构体型的指针数组*/
inform *p1; p1=p;

for(int i=0; i<n; i++)

{
cin>>(p+i)->data>>(p+i)->l>>(p+i)->r;
if((p+i)->l != -1) (p+i)->signl=1; /*用signl signr 的0，1标示输入的信息中是否有左或右孩子*/
else (p+i)->signl= 0;
if((p+i)->r !=-1) (p+i)->signr=1;
else (p+i)->signr= 0;
}

/*--------------------------------------------------------------------------------------------*/
a[0]= p->data;

judge ( p1 ); /*用递归算法将输入数据信息转为线性字符串*/

cout<<endl<<"输出转换的线性字符串： "<<endl;

cout<<a<<endl<<endl;
/*------------------------------------------遍历-----------------------------------*/
leafnode* T;

T= creatree();

/*先续遍历二叉树*/
cout<<"先序遍历二叉树： "<<endl;
preorder( T );

cout<<endl<<"中序遍历二叉树： "<<endl;
inorder ( T );

cout<<endl<<"后序遍历二叉树： "<<endl;
postorder( T );
cout<<endl<<endl;

}

/*------------------------------------------函数定义-------------------------------*/

void judge( inform* ps ) /*用函数的递归来将输入的信息转化为线性的数组*/
{
inform* b;

if (ps->signl==0)
{
a[k]='@';
k++;
}
else
{
b = p+(ps->l);
a[k] = b->data;
k++;
judge(b);
}

if ((ps->signr) == 0)
{
a[k]='@';
k++;
}
else
{
b = p+(ps->r );
a[k] = b->data;
k++;
judge(b);
}

}

leafnode* creatree() /*建立二叉树函数*/
{
char ch;

leafnode *t;

ch= a[s];
s++;

if(ch=='@')
{
t=NULL;
}
else
{
t=(leafnode* )malloc(sizeof(leafnode));
t->leaf=ch;
t->lchild=creatree();
t->rchild=creatree();
}
return t;

}

/*先序遍历的递归函数*/
void preorder (leafnode* T)
{
if(T)
{
cout<<T->leaf;
preorder(T->lchild);
preorder(T->rchild);
}
}
/*中序遍历的递归函数*/
void inorder (leafnode* T)
{
if(T)
{
inorder(T->lchild);
cout<<T->leaf;
inorder(T->rchild);
}
}
/*后序遍历的递归函数*/
void postorder (leafnode* T)
{
if(T)
{
postorder(T->lchild);
postorder(T->rchild);
cout<<T->leaf;
}
}

Answer 2

我给你的的类吧

#include <iostream>
#include <queue>
#include <stack>
#include <conio.h>
using namespace std;

#include "Node.h"

template <class T>

class BTree
{
public:
char Leaf[50]; //记录叶结点
BTree(); //构造函数

Node<T>* createBTree();//按先序遍历序列建立二叉树

void PreOrder(Node<T>* r); //先序遍历的递归算法
void InOrder(Node<T>* r); //中序遍历的递归算法
void PostOrder(Node<T>* r); //后序遍历的递归算法
int GetSum(); //求节点数
int GetLeaves(); //求叶结点数
int GetDeep(); //求数的深度
void Destroy(Node<T>* r);
Node<T>* getRoot();
void Print(Node<T>* r,int level);

private:
Node<T>* root;
int Sum;
int Deep;
int Leaves;

};

template <class T>
BTree<T>::BTree()
{
root = NULL;
Sum=0;
Deep=0;
Leaves=0;
}

template <class T>
Node<T>* BTree<T>::getRoot()
{
return root;
}

//求二叉树的高度
template <class T>
int BTree<T>::GetDeep()
{
return Deep;
}
//求二叉树的结点数
template <class T>
int BTree<T>::GetSum()
{
return Sum;
}
//求二叉树的叶结点数
template <class T>
int BTree<T>::GetLeaves()
{
return Leaves;
}
//二叉树先序遍历 递归算法
template <class T>
void BTree<T>::PreOrder(Node<T>* r)
{
if(r!=NULL)
{
cout << r->data << " ";
PreOrder(r->lChild);
PreOrder(r->rChild);
}
}

//二叉树中序遍历 递归算法
template <class T>
void BTree<T>::InOrder(Node<T>* r)
{
if(r)
{

InOrder(r->lChild);
cout << r->data << " ";
InOrder(r->rChild);
}

}

//二叉树后序遍历 递归算法
template <class T>
void BTree<T>::PostOrder(Node<T>* r)
{
if(r!=NULL)
{

PostOrder(r->lChild);
PostOrder(r->rChild);
cout << r->data << " ";
}

}

template <class T>
void BTree<T>::Print(Node<T>* r, int level)
{
if(level>Deep)
Deep=level;
//二叉树r第level层结点数据域值的横向显示
if(r != NULL)
{
//二叉树r->rChild第level+1层结点数据域值的横向显示
Print(r->rChild , level+1);

if(level != 0)
{ //走过6*(level-1)个空格
for(int i = 0; i < 6*(level); i++)
cout<<" ";
cout << " ----";
}
cout << r->data << endl;

//二叉树r->lCHild第level+1层结点数据域值的横向显示
Print(r->lChild, level+1);
}
}

template <class T>
void BTree<T>::Destroy(Node<T>* r)
{
if(r !=NULL)
{
if(r->lChild != NULL)
Destroy(r->lChild);
if(r->rChild != NULL)
Destroy(r->rChild);
cout << r->data << " "; //此语句只是为了方便测试
delete r;
}

Sum=0;
Deep=0;
Leaves=0;
}

template <class T>
Node<T>* BTree<T>::createBTree()//按先序遍历序列建立二叉树
{
Node<T> * r;

char ch;
cin>>ch;
if(ch=='#')
return NULL;
else
{
int t=++Sum;
r = new Node<T>(ch);
r->lChild=createBTree();
r->rChild=createBTree();
if(Sum==t)
{
Leaf[Leaves++]=ch;
}

}
root=r;
return r;
}

Answer 3

// 头文件什么的我就不写了
// 结点的定义
typedef struct node
{
int value;
struct node *lchild;
struct node *rchild;
}Node, *Tree;

// 1.设计算法求二叉树的结点个数
void GetTreeNodeCount( Tree* t, int& count )
{
if( t != NULL )
{
count++;
GetTreeNodeCount( t->lchild, count );
GetTreeNodeCount( t->rchild, count );
}
}
int GetTreeNodeCount( Tree t )
{
int count = 0;
GetTreeNodeCount( t, count );
return count;
}

// 2.设计算法按前序次序打印二叉树中的叶子结点
void PrintLeapNode( Tree t )
{
if( t != NULL )
{
PrintLeapNode( t->lchild );
PrintLeapNode( t->rchild );
if( t->lchild == NULL && t->rchild == NULL )
printf( "%d", t->value );
}
}

// 3.设计算法求二叉树的深度
void GetTreeDeep( Tree t, int i, int& deep )
{
if( t != NULL )
{
GetTreeDeep( t->lchild, i+1, deep );
GetTreeDeep( t->rchild, i+1, deep );
}
else
{
if( i > deep )
deep = i;
}
}
int GetTreeDeep( Tree t )
{
int deep = 0;
GetTreeDeep( t, 0, deep );
return deep;
}