二叉树的建立和遍历(C++)

Question

[问题描述]
建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
要求:
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。
测试数据:
ABCфDEфGфффFффG（其中ф表示空格字符）
则输出结果为：
先序：ABDFCEG
中序：BFDACEG
后序：FDBGECA

Answer 1

фinclude<iostream>
фinclude<windows.h>
фinclude<string>
фinclude<stdlib.h>
фinclude<fstream>
using namespace std;

//------------------------------二叉树节点------------------------------------------

class bitnode
{
public:
char data;
bitnode *lchild,*rchild;
};

//-------------------------------函数-------------------------------------------------

void visit(bitnode *T); //访问二叉树节点
void create(bitnode *&T); //生成二叉树
void zhongbianli(bitnode *T); //中序遍历二叉树
void houbianli(bitnode *T); //后序遍历二叉树
void xianbianli(bitnode *T); //先序遍历二叉树
int pd(bitnode *T); //判断是否是完全二叉树
int depth(bitnode *T); //二叉树的深度

//------------------------------访问二叉树节点---------------------------------------

void visit(bitnode *T)
{
cout<<T->data<<ends;
return;
}

//------------------------------生成二叉树------------------------------------------

void create(bitnode *&T)
{
//bitnode T;
char a;
//cin>>a;
cin>>a;
cout<<a;
if(a=='ф')
{
T=NULL;
}
else
{
T=new bitnode;

T->data=a;
T->lchild=NULL;
T->rchild=NULL;

// cout<<"create "<<T->data<<"'s lchild";
create(T->lchild);
// cout<<"create "<<T->data<<"'s rchild";
create(T->rchild);
}

}

//------------------------------中序遍历二叉树----------------------------------------

void zhongbianli(bitnode *T)
{
if(T)
{
zhongbianli(T->lchild);
visit(T);
zhongbianli(T->rchild);
}
}

//------------------------------先序遍历二叉树-----------------------------------------

void xianbianli(bitnode *T)
{
if(T)
{
visit(T);
xianbianli(T->lchild);
xianbianli(T->rchild);
}
}

//------------------------------后序遍历二叉树------------------------------------------

void houbianli(bitnode *T)
{
if(T)
{
houbianli(T->lchild);
houbianli(T->rchild);
visit(T);
}
}

//------------------------------二叉树的深度-----------------------------------------

int depth(bitnode *T)
{
int dep1,dep2;
if (T==NULL) return 0;
else
{
dep1=depth(T->lchild);
dep2=depth(T->rchild);
return dep1>dep2?dep1+1:dep2+1;
}
}

//------------------------------判断是否是完全二叉树-----------------------------------

int pd(bitnode *T)
{
int l,r,h;
if(T->lchild)
{
l=pd(T->lchild);
}
else
l=0;

if(T->rchild)
{
r=pd(T->rchild);
}
else
r=0;
if(l==0&&r==0)
{
return 2;
h=0;
}
if(l==0&&(r==1||r==2||r==3))
{
return 3;
}
if(l==1&&r==0)
{
return 1;
}
if(l==1&&(r==1||r==3))
{
return 3;
}
if(l==1&&r==2)
{
if(depth(T->lchild)==depth(T->rchild)+1)
return 1;
else
return 3;
}
if(l==2&&r==0)
{
return 1;
}
if(l==2&&r==1)
{
if(depth(T->lchild)==depth(T->rchild))
return 1;
else
return 3;
}
if(l==2&&r==2)
{
if(depth(T->lchild)==depth(T->rchild))
return 2;
else if(depth(T->lchild)==depth(T->rchild)+1)
return 1;
else
return 0;
}
if(l==2&&r==3)
{
return 3;
}
if(l==3)
{
return 3;
}
else return 4;

}

//------------------------------主函数---------------------------------------------

int main(void)
{
bitnode *T=NULL;
//printf("文件输入为：\n");
//ifstream in;
//in.open("cy.txt",ios::in);
create(T);
cout<<endl;
cout<<"中序遍历为："<<endl;
zhongbianli(T);
cout<<endl;
cout<<"先序遍历为："<<endl;
xianbianli(T);
cout<<endl;
cout<<"后序遍历为："<<endl;
houbianli(T);
cout<<endl;
cout<<endl;
int t;
t=pd(T);
if(t==1||t==2)
cout<<"这个二叉树是完全二叉树。"<<endl;
else
cout<<"这个二叉树不是完全二叉树。"<<endl;
getchar();
getchar();

return 0;
}

Answer 2

#include <iostream>

using namespace std;

#include <iomanip>

typedef int T;

class bst{

struct Node{

T data;

Node* L;

Node* R;

Node(T const& d):data(d),L(NULL),R(NULL){}
};

Node* root;

int num;

void clear(Node*& t){

if(t==NULL) return;

clear(t->L);

clear(t->R);

delete t;

t = NULL;

}

void midtravel(Node* t){

if(t==NULL) return;

travel(t->L);

cout << t->data << ' ';

travel(t->R);

}

void fronttravel(Node* t){

if(t==NULL) return;

cout << t->data << ' ';

travel(t->L);

travel(t->R);

}

void backtravel(Node* t){

if(t==NULL) return;

travel(t->L);

travel(t->R);

cout << t->data << ' ';

}

void insert(Node*& t, Node* p){

if(t==NULL) t=p;

else if(p->data < t->data) insert(t->L, p);

else insert(t->R, p);

}

void printTree(Node* t, int space, char c){

if(t==NULL) return;

printTree(t->R, space+4, '/');

cout << setw(space) << c << t->data << endl;

printTree(t->L, space+4, '\\');

}

Node*& find(Node*& t, T const& d){

if(t==NULL) return t;

if(t->data==d) return t;

if(d<t->data) return find(t->L, d);

return find(t->R, d);
}

int getHeight (Node* p)

{

int Llevel, Rlevel;

if (NULL == p)

return 0;

Llevel = getHeight (p->L);

Rlevel = getHeight (p->R);

return (Llevel>Rlevel)?(Llevel+1):(Rlevel+1);

}

public:
bst():root(NULL),num(0){}
~bst(){clear();}

void clear(){clear(root);num=0;}

void Midtravel(){travel(root);cout<<endl;}

bst& insert(T const& d){

Node* p = new Node(d);

num++;

insert(root, p);

return *this;

}

void Fronttravel(){travel(root);cout<<endl;}

bst& insert(T const& d){

Node* p = new Node(d);

num++;

insert(root, p);

return *this;

}

void Backtravel(){travel(root);cout<<endl;}

bst& insert(T const& d){

Node* p = new Node(d);

num++;

insert(root, p);

return *this;

}

bool find(T const& d){

return (find(root, d)!=NULL);
}

int count(T const& d){

int cnt=0;

Node* p=root;

while( (p=find(p, d))!=NULL ){

cnt++;

p = p->R;

}

return cnt;

}

bool remove(T const& d){

Node*& pn = find(root, d);

if(pn==NULL) return false;

Node* p = pn;

if(pn->L!=NULL) insert(pn->R, pn->L);

pn = pn->R;

delete p;

num--;

return true;

}

int removeall(T const& d){

int cnt=0;

while(remove(d))

cnt++;

return cnt;
//
return 1 + remove(d);

}

void printTree(){

printTree(root, 1, '*');

}

int update(T const& olddata, T const& newdata){

int cnt = remove(olddata);

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

insert(newdata);

return cnt;

}

int size(){return num;}

bool empty(){return root==NULL;}

T const& getRootData()throw(char const*){

if(empty()) throw "empty tree!";

return root->data;
}

int getHeight()

{

return getHeight(root);

}

};

类给你了
实现自己看看吧 Midtravel中序遍历 Fronttravel前序 Backtravel后续注意大写 小写的是给类内部用的

Answer 3

Answer 4

#include<stdio.h>
#include<stdlib.h>
typedef struct BNode
{
char data;
struct BNode *lchild;
struct BNode *rchild;
}BTNode;
typedef BTNode *BinTree;
void CreateBinTree(BinTree *root)//以先序来建立二叉树
{
char ch;
if((ch=getchar())==' ')//这个代表空格，可换别的字符
*root=NULL; //建立空二叉树
else
{
*root=(BTNode*)malloc(sizeof(BTNode));//开辟空间，生成节点
(*root)->data=ch;
CreateBinTree(&((*root)->lchild));
CreateBinTree(&((*root)->rchild));
}
}
void PreOrder(BinTree root)//先序遍历
{
if(root!=NULL)
{
printf("%c",root->data);//访问根节点
PreOrder(root->lchild);//遍历左子树
PreOrder(root->rchild);//遍历右子树
}
}
void InOrder(BinTree root)//中序遍历
{
if(root!=NULL)
{
PreOrder(root->lchild); //遍历左子树
printf("%c",root->data);//访问根节点
PreOrder(root->rchild);//遍历右子树
}
}
void PostOrder(BinTree root)//后序遍历
{
if(root!=NULL)
{
PreOrder(root->lchild);//遍历左子树
PreOrder(root->rchild);//遍历右子树
} printf("%c",root->data);//访问根节点
}
void main()
{
BinTree root;
CreateBinTree(&root);
printf("先序:");
PreOrder(root);
printf("\n");
printf("中序:");
InOrder(root);
printf("\n");
printf("后序:");
PostOrder(root);
printf("\n");
}本回答被提问者采纳