怎么样创建二叉树呢?
发布网友
发布时间：2022-04-29 18:26
共3个回答
热心网友
时间：2022-06-19 01:09
#define ASD_H
#include <iostream>
using namespace std;
#include <queue>
struct bitnode //结构体创建树节点
{
char data;
bitnode *lch,*rch;
};
struct bitnode * bit;
template<class Type>
class BinaryTree //定义 二叉树类 class
{
public:
BinaryTree(); //构造函数
~BinaryTree(); //析构函数
void CreatBTree(char* a);
//创建树
bool BTEmpty(); //判断树是否为空
void insert(char x);
int height(bitnode* b); //求树的高度
void visit(); //遍历
void preorder(bitnode* b);
void inorder(bitnode* b);
void postorder(bitnode* b);
void ClearBTree(bitnode* & b);
int max(int x,int y);
int tree_height();
private:
bitnode* root;
};
template <class Type>
BinaryTree<Type>::BinaryTree()
{
root=NULL;
}
template <class Type>
BinaryTree<Type>::~BinaryTree()
{
if(root!=NULL)
{
ClearBTree(root->lch);
ClearBTree(root->rch);
delete root;
root=NULL;
}
}
template <class Type>
void BinaryTree<Type>::CreatBTree(char* a)
{
int i;
queue<bitnode*> s; //创建队列
root=NULL;
i=0;
bitnode *p,*w;
p=new bitnode;
p->data=a[i];
root=p;
s.push(p); //入列
i=1;
while(a[i]!='#')//以#作为输入结束标志
{
if(i%2!=0)//判断是左右子树
{//如果为左子树，执行以下
p=s.front();
//队头赋给P
s.pop();
w=new bitnode;
//动态分配节点空间
w->data=a[i];
//接收输入字符
w->lch=NULL;
w->rch=NULL;
if(a[i]=='/')
//以’/’作为输入空标志
p->lch=NULL;
else
p->lch=w;
//先赋予左指针
s.push(w);//保存节点
}
else
{
w=new bitnode;
//分配节点空间
w->data=a[i]; //接收输入字符
w->lch=NULL;
w->rch=NULL;
if(a[i]=='/')
p->rch=NULL;
else
p->rch=w;
//再赋予右指针
s.push(w); //保存节点
}
i++;//继续接收字符
}
}
template <class Type>
bool BinaryTree<Type>::BTEmpty()
{
return root==NULL;
}
template <class Type>
void BinaryTree<Type>::ClearBTree(bitnode* & b)
{
if(b!=NULL)
{
ClearBTree(b->lch);
ClearBTree(b->rch);
delete b;
b=NULL;
}
}
template <class Type>
void BinaryTree<Type>::visit()
{
cout<<"前序遍历为:";
preorder(root);
cout<<endl<<"中序遍历为:";
inorder(root);
cout<<endl<<"后序遍历为:";
postorder(root);
}
template <class Type>
int BinaryTree<Type>::max(int x,int y)
{
if(x>y)
return x;
else
return y;
}
template <class Type>
int BinaryTree<Type>::height(bitnode* b)
{ //递归计算树的高度
if (b == NULL)
return 0;
else
return 1 + max(height(b->lch), height(b->rch));
}
template<class Type>
int BinaryTree<Type>::tree_height()
{
bitnode *p=root;
return height(p);
}
template <class Type>
void BinaryTree<Type>::insert(char x)
{
bitnode* p,*q;//创建节点指针
p=root; //将根节点指针赋给P
if(p==NULL)
p->data=x;
//如果根节点为空则直接将X赋给p->data
else
{
while(p->lch!=NULL||p->rch!=NULL)
{//否则其左右指针不为空时
if(height(p->lch)<=height(p->rch))
{
//如果左子树不高于右子树,则插在左子树
if(p->lch!=NULL)
p=p->lch;
else
{//动态分配节点空间
q=new bitnode;
q->data=x;
q->lch=NULL;
q->rch=NULL;
p->lch=q;
goto next;
}
}
else
{
//如果右子树低于右子树,则X插在右子//树
if(p->rch!=NULL)
p=p->rch;
else
{//动态分配节点空间
q=new bitnode;
q->data=x;
q->lch=NULL;
q->rch=NULL;
p->rch=q;
goto next;
}
}
}
}
//当为空树时,X直接插在左子树 //动态分配节点空间
q=new bitnode;
cout<<endl;
q->data=x;
q->lch=NULL;
q->rch=NULL;
p->lch=q;
next:
cout<<endl;
}
template <class Type>
void BinaryTree<Type>::preorder(bitnode* b)
{ //前序遍历
if(b!=NULL)
{
cout<<b->data<<",";
preorder(b->lch);
preorder(b->rch);
}
}
template <class Type>
void BinaryTree<Type>::inorder(bitnode* b)
{ //中序遍历
if(b!=NULL)
{
inorder(b->lch);
cout<<b->data<<",";
inorder(b->rch);
}
}
template <class Type>
void BinaryTree<Type>::postorder(bitnode* b)
{ //后序遍历
if(b!=NULL)
{
postorder(b->lch);
postorder(b->rch);
cout<<b->data<<",";
}
}
#endif
<<.CPP文件>>
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <conio.h>
#include "asd.h"
void main()
{
int m;
BinaryTree<char> S;//定义为char
char b[20],x; //定义数组
cout<<"请输入数列:"<<endl;
cin>>b;
S.CreatBTree(b);
cout<<endl;
S.visit();
m=S.tree_height();
cout<<endl<<树的高度为:"<<m<<endl;
cout<<"请输入一个字符:"<<endl;
cin>>x;
S.insert(x);
S.visit();
getch();
}
参考资料：http://ban102.qyun.net/
热心网友
时间：2022-06-19 01:10
2.为了直观的输出树，那么可以选择广度遍历。查查书应该有。
3.深度的话我这刚好有两个函数
#include <stdlib.h>
typedef struct{
char data;
}TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode, *BiTree;
void CreateBiTree(BiTree &T)
{
char ch;
TElemType elem;
printf("请输入树节点, 空树以#代替:");
scanf("\n%c", &ch);
elem.data = ch;
if(ch == '#')
{
T = NULL;
}
else
{
T = (BiTNode * )malloc(sizeof(BiTNode));
if(!T) exit(-1);
T->data = elem; //生成根
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);// 构造右子树
}
}
void main()
{
BiTree T;
CreateBiTree(T);
}
热心网友
时间：2022-06-19 01:10
typedef struct BNode //二叉树结点结构体
{
ElemType data;
struct BNode *lch,*rch;
}BNode;
BNode *creat_bt0() //利用二叉树的性质，借助一维数组v建立二叉树
{
BNode *t,*p,*v[20];
printf("\n i data=?");
scanf("%d%d",&i,&e);
while(i!=0&&e!=0)
{
p=(BNode*)malloc(sizeof(BNode));
p->data=e;
p->lch=NULL;
p->rch=NULL;
v[i]=p;
if(i==1)
t=p;
else
{
j=i/2;
if(i%2==0)
v[j]->lch=p;
else
v[j]->rch=p;
}
printf("\n i data=?");
scanf("%d%d",&i,&e);
}
return(t);
}
