求用c++建立一棵二叉树的程序代码
#include
#include
typedef char datatype;
typedef struct BinNode{
datatype data;
struct BinNode* lchild;
struct BinNode* rchild;
}BinNode;
typedef BinNode* bintree; //bintree本身是个指向结点的指针
//前序遍历生成二叉树
void createtree(bintree *t){
datatype c;
c=getchar();
if(c == '#')
*t = NULL;
else{
*t = (bintree)malloc(sizeof(BinNode));
(*t)->data = c;
createtree(&(*t)->lchild);
createtree(&(*t)->rchild);
}
}
//中序遍历
void midorder(bintree t){
if(t){
midorder(t->lchild);
printf("%c ",t->data);
midorder(t->rchild);
}
}
//查找
bool search_tree(bintree t,datatype x){
if(!t){
return false;
}
if(t->data == x){
return t;
}else{
if(!search_tree(t->lchild,x)){
return search_tree(t->rchild,x);
}
return true;
}
}
//求深度
int height_tree(bintree t){
int h,left,right;
if(!t){
return 0;
}
left = height_tree(t->lchild);
right = height_tree(t->rchild);
h = (left>right?left:right)+1;
return h;
}
void main()
{
bintree Tree;
printf("Create tree in preorder:
");
createtree(&Tree);
printf("Display tree in midorder:
");
midorder(Tree);
printf("
");
int height=height_tree(Tree);
printf("height:%d
",height);
search_tree(Tree,'e')?printf("Found!
"):printf("Not Found!
");
return ;
}
我有C语言版的,要不???
先建立一个头文件"bitree.h"(以下都要用到):
#include
#include
#include
typedef char DataType;
typedef struct Node
{
DataType data;
struct Node *LChild;
struct Node *RChild;
}BiTNode, *BiTree;
void CreateBiTree(BiTree *bt)
{
char ch;
ch = getchar();
if(ch=='.') *bt=NULL;
else
{
*bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点
(*bt)->data=ch;
CreateBiTree(&((*bt)->LChild)); //生成左子树
CreateBiTree(&((*bt)->RChild)); //生成右子树
}
}
程序如下:
(1)
#include "bitree.h"
void preOrder(BiTree root)
/*先序遍历二叉树, root为指向二叉树根结点的指针*/
{
if (root!=NULL)
{
printf("%c",root->data); /*输出结点*/
preOrder(root ->LChild);/*先序遍历左子树*/
preOrder(root ->RChild); /*先序遍历右子树*/
}
}
void inOrder(BiTree root)
{
if(root!=NULL)
{
inOrder(root->LChild);/*中序遍历左子树*/
printf("%c",root->data); /*输出结点*/
inOrder(root->RChild);/*中序序遍历右子树*/
}
}
void postOrder(BiTree root)
{
if(root!=NULL)
{
postOrder(root->LChild);/*后序遍历左子树*/
postOrder(root->RChild);/*后序遍历右子树*/
printf("%c",root->data);/*输出结点*/
}
}
void main()
{
BiTree T;
printf("建立二叉树,请输入序列:
");
CreateBiTree(&T);
printf("
输出前序序列为:");
preOrder(T);
printf("
输出中序序列为:");
inOrder(T);
printf("
输出后序序列为:");
postOrder(T);
getch();
}
(2)
#include "bitree.h"
int leaf(BiTree root)//求二叉树中叶子结点的数目
{
int LeafCount;
if(root==NULL)
LeafCount=0;
else if((root->LChild==NULL)&&(root->RChild==NULL))
LeafCount=1;
else
LeafCount=leaf(root->LChild)+leaf(root->RChild);
return LeafCount;
}
void main()
{
BiTree T;
int LeafCount;
printf("按扩展先序遍历序列建立二叉树,请输入序列:
");
CreateBiTree(&T);
LeafCount=leaf(T);
printf("
输出叶子结点的个数:");
leaf(T);
printf("%d",LeafCount);
}
(3)
#include "bitree.h"
int PostTreeDepth(BiTree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=PostTreeDepth(bt->LChild);
hr=PostTreeDepth(bt->RChild);
max=hl>hr? hl:hr;
return(max+1);
}
else return(0);
}
void main()
{
BiTree T;
int max;
printf("建立二叉树,请输入序列:
");
CreateBiTree(&T);
max=PostTreeDepth(T);
printf("
输出二叉树的高度为:");
PostTreeDepth(T);
printf("%d",max);
}
这里基本上包括二叉树所有操作了,楼主自取所需吧:
#include<iostream>
using namespace std;
// 二叉树结点类
struct BinTreeNode
{
// 数据成员:
double data; // 数据域
BinTreeNode *leftChild; // 左孩子指针域
BinTreeNode *rightChild; // 右孩子指针域
BinTreeNode(){ leftChild = rightChild = NULL;}; // 无参数的构造函数
BinTreeNode(double &val,BinTreeNode *lChild = NULL, BinTreeNode *rChild = NULL);
};
BinTreeNode::BinTreeNode(double &val, BinTreeNode *lChild,BinTreeNode *rChild)
{
data = val; // 数据元素值
leftChild = lChild; // 左孩子
rightChild = rChild; // 右孩子
}
//节点类,其数据成员为二叉节点类型的指针
struct Node
{
BinTreeNode *data; // 数据域
Node *next; // 指针域
Node(){ next = NULL;};
Node( BinTreeNode *item, Node *link = NULL){ data = item; next = link;};
};
//队列类,作为层次遍历的辅助数据结构用
class LinkQueue
{
protected:
Node *front, *rear;
public:
LinkQueue(){rear = front = new Node; };
void OutQueue(BinTreeNode * &e); // 出队操作
void InQueue(BinTreeNode * &e); // 入队操作
bool Empty(){return front==rear;};
};
void LinkQueue::OutQueue(BinTreeNode * &e)
{ Node *tmpPtr = front->next;
e = tmpPtr->data;
front->next = tmpPtr->next;
if (rear == tmpPtr)
{
rear = front;
}
delete tmpPtr;
}
void LinkQueue::InQueue(BinTreeNode * &e)
{
Node *tmpPtr = new Node(e);
rear->next = tmpPtr;
rear = tmpPtr;
}
// 二叉树类
class BinaryTree
{
protected:
BinTreeNode *root;
// 辅助函数:
void DestroyHelp(BinTreeNode * &r);
void PreOrderHelp(BinTreeNode *r) const ;
void InOrderHelp(BinTreeNode *r) const ;
void PostOrderHelp(BinTreeNode *r) const ;
int HeightHelp(const BinTreeNode *r) const;
int NodeCountHelp(const BinTreeNode *r) const;
int leafNodeCountHelp(const BinTreeNode *r) const;
public:
BinaryTree();
virtual ~BinaryTree();
BinTreeNode *GetRoot() const;
void InOrder() const;
void PreOrder() const;
void PostOrder() const;
void LevelOrder() const;
int NodeCount() const;
int leafNodeCount() const;
void InsertLeftChild(BinTreeNode *cur, double &e);
void InsertRightChild(BinTreeNode *cur, double &e);
int Height() const;
BinaryTree( double &e);
};
BinaryTree ::BinaryTree()
{
root = NULL;
}
BinaryTree ::~BinaryTree()
{
DestroyHelp(root);
}
BinTreeNode *BinaryTree ::GetRoot() const
{
return root;
}
void BinaryTree ::PreOrderHelp(BinTreeNode *r) const
{
if (r != NULL)
{
cout<<(r->data)<<" ";
PreOrderHelp(r->leftChild);
PreOrderHelp(r->rightChild);
}
}
void BinaryTree ::PreOrder() const
{
PreOrderHelp(root);
}
void BinaryTree ::InOrderHelp(BinTreeNode *r) const
{
if (r != NULL)
{
InOrderHelp(r->leftChild);
cout<<(r->data)<<" ";
InOrderHelp(r->rightChild);
}
}
void BinaryTree ::InOrder() const
{
InOrderHelp(root);
}
void BinaryTree ::PostOrderHelp(BinTreeNode *r) const
{
if (r != NULL)
{
PostOrderHelp(r->leftChild);
PostOrderHelp(r->rightChild);
cout<<(r->data)<<" ";
}
}
void BinaryTree ::PostOrder() const
{
PostOrderHelp(root);
}
void BinaryTree ::LevelOrder() const
{
LinkQueue q; // 队列
BinTreeNode *t = root; // 从根结点开始进行层次遍历
if (t != NULL) q.InQueue(t);
while (!q.Empty())
{ q.OutQueue(t);
cout<<(t->data)<<" ";
if (t->leftChild != NULL)
q.InQueue(t->leftChild);
if (t->rightChild != NULL)
q.InQueue(t->rightChild);
}
}
int BinaryTree ::HeightHelp(const BinTreeNode *r) const
{
if(r == NULL)
{ return 0;
}
else
{ int lHeight, rHeight;
lHeight = HeightHelp(r->leftChild); // 左子树的高
rHeight = HeightHelp(r->rightChild); // 右子树的高
return (lHeight > rHeight ? lHeight : rHeight) + 1;
}
}
int BinaryTree ::Height() const
{
return HeightHelp(root);
}
BinaryTree ::BinaryTree( double &e)
{
root = new BinTreeNode (e);
}
int BinaryTree ::NodeCountHelp(const BinTreeNode *r) const
{
if (r ==NULL) return 0;
else return NodeCountHelp(r->leftChild) + NodeCountHelp(r->rightChild) + 1;
}
int BinaryTree ::NodeCount() const
{
return NodeCountHelp(root);
}
int BinaryTree ::leafNodeCountHelp(const BinTreeNode *r) const
{ int lt,rt;
if (r==NULL) return 0;
else if(r->leftChild==NULL &&r->rightChild==NULL)
return 1;
else
{lt=leafNodeCountHelp(r->leftChild);
rt=leafNodeCountHelp(r->leftChild);
return lt+rt;}
}
int BinaryTree ::leafNodeCount() const
{
return leafNodeCountHelp(root);
}
void BinaryTree ::InsertLeftChild(BinTreeNode *cur, double &e)
{
if (cur == NULL)
{
return;
}
else
{ // 插入左孩子
BinTreeNode *child = new BinTreeNode (e);
if (cur->leftChild != NULL)
{child->leftChild = cur->leftChild;
}
cur->leftChild = child;
return;
}
}
void BinaryTree ::InsertRightChild(BinTreeNode *cur, double &e)
{
if (cur == NULL)
{ return;
}
else
{ // 插入右孩子
BinTreeNode *child = new BinTreeNode (e);
if (cur->rightChild != NULL)
{ child->rightChild = cur->rightChild;
}
cur->rightChild = child;
return;
}
}
void BinaryTree ::DestroyHelp(BinTreeNode *&r)
{
if(r != NULL)
{ DestroyHelp(r->leftChild); // 销毁左子树
DestroyHelp(r->rightChild); // 销毁右子树
delete r; // 销毁根结点
r = NULL;
}
}
int main(void)
{ double e;
BinTreeNode *cur;
cout<<"请输入根节点的数值:";
cin>>e;
cur = new BinTreeNode(e);
BinaryTree bt(e); // 建立二叉树
cur = bt.GetRoot();
cout<<"请输入根节点左孩子的数值:";
cin>>e;
bt.InsertLeftChild(cur, e);
cout<<"请输入根节点右孩子的数值:";
cin>>e;
bt.InsertRightChild(cur, e);
cout<<"请输入根节点左孩子的左孩子的数值:";
cin>>e;
bt.InsertLeftChild(cur->leftChild, e);
cout<<"请输入根节点右孩子的左孩子的数值:";
cin>>e;
bt.InsertLeftChild(cur->rightChild, e);
cout<<"请输入根节点右孩子的右孩子的数值:";
cin>>e;
bt.InsertRightChild(cur->rightChild,e);
cout << "先序遍历:" << endl;
bt.PreOrder();
cout<<endl;
system("PAUSE");
cout << "中序遍历:" << endl;
bt.InOrder();
cout<<endl;
system("PAUSE");
cout << "后序遍历:" << endl;
bt.PostOrder();
cout<<endl;
system("PAUSE");
cout << "层次遍历:" << endl;
bt.LevelOrder();
cout<<endl;
system("PAUSE");
cout<<"树的高度为"<<bt.Height()<<endl;
cout<<"树中节点数为"<<bt.NodeCount()<<endl;
cout<<"树中叶子节点数为"<<bt.leafNodeCount()<<endl;
return 0;
}
(C语言)构造一棵二叉树并显现出来
typedef struct BiTNode { char data;struct BiTNode *lchild;struct BiTNode *rchild;}BiTNode,*BiTree;int CreateBiTree(BiTree &T){ char c;scanf("%s",&c);if('*'==c){ T=NULL;return 0;} else { BiTNode* T=(BiTNode*)malloc(sizeof(BiTNode*));T->data=c;T->lchild=NULL;T-...
用C语言建立一棵二叉树,使用二杈链表存储,对其进行后续遍历,输出后序...
BTNode *p,*st[Maxsize];int top=-1;p=NULL;b=NULL;int j=0,k;char ch=str[j];while(ch!='\\0'){ switch(ch){ case '(':top++;st[top]=p;k=1;break;case ')':top--;break;case ',':k=2;break;default:p=(BTNode *)malloc(sizeof(BTNode));p->data=ch;p->lchild=p...
用C语言建立一棵含有n个结点的二叉树,采用二叉链表存储,然后分别实现...
int creat(list*root){ \/\/创建一棵二叉树,root使用的是二维指针 char n;scanf(" %c",&n); \/\/注%C前面加空格是为了起间隔作用 scanf不读入空格 if (n=='0') \/\/0为间隔 { root=NULL; return 0; \/\/输入结束 } root=(list)malloc(sizeof(bt));if (!*root) return 0;(*root...
数据结构试验(用C语言)建立一棵二叉树,并用递归或者非递归的算法分别用...
define LEN sizeof(struct tree)define NULL 0 include<stdio.h> include<malloc.h> struct tree { char data;struct tree *lchild,*rchild;};\/\/创建二叉树 struct tree *creat(){ char c;struct tree *t;c=getchar();if(c==' ')t=NULL;else { t=(struct tree*)malloc(LEN);t->dat...
C语言演示二叉树算法
二叉树的第i层至多有2i − 1个结点;深度为k的二叉树至多有2k − 1个结点;对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。首先打开VC++6.0 选择文件,新建 选择C++ source file 新建一个空白文档 首...
C语言,给定一组值,建立一棵二叉树,求二叉树的数深
void Create(struct BiTreeNode *&Tnode) \/\/先序创建2叉链表 { char ch;scanf("%c",&ch);if(ch=='#'){ Tnode=NULL;} else { Tnode=new BiTreeNode;Tnode->data=ch;Create(Tnode->lchild);Create(Tnode->rchild);} } void PreOrder(struct BiTreeNode *&Tnode) \/\/先序遍历2叉...
数据结构 c语言版二叉树(1) 建立一棵含有n个结点的二叉树,采用二叉链 ...
printf("%c",ptr->ch);} } void main(){ printf("构建一个二叉树(结点数为n):\\n");root=create(root);printf("前序遍历二叉树:\\n");preorder(root);printf("\\n");printf("中序遍历二叉树:\\n");inorder(root);printf("\\n");printf("后序遍历二叉树:\\n");postorder(root);...
急!~编写一个C++语言程序,对二叉树实现操作
1. 建立一棵二叉树 Status CreateBiTree(BiTree &T)\/\/按先序次序输入二叉树中结点的值(一个字符),#字符表示空树,\/\/构造二叉链表表示的二叉树T。scanf(&ch);if (ch=='#') T=NULL;else { if (!(T=(BiTNode *) malloc(sizeof(BiTNode))) exit (OVERFLOW);T->data = ch; ...
建立一棵二叉树,并对其进行遍历(先序、中序、后序),打印输出遍历结果...
include<stdio.h> typedef datatype;typedef struct BinTNode{ datatype data;struct BinTNode *lchild,*rchild;}BinTNode,*BinTree;void CreateBinTree(BinTree*T){char ch;scanf("\\n%c",&ch);if(ch=='0')*T=NULL;else{*T=(BinTNode*)malloc(sizeof(BinTNode));(*T)->data=ch;C...
用C++开发一个二叉树类
利用学习数据结构关于二叉树的知识,建立一棵二叉树C++类,基本功能要求:a)包括根据关键字生成、插入节点,删除节点等功能。b)提供遍历功能。c)统计数叶子结点的个数。d)求二叉树的深... 利用学习数据结构关于二叉树的知识,建立一棵二叉树C++类,基本功能要求:a) 包括根据关键字生成、插入节点,删除节点等功能。b) ...
喻帜明欣: #include typedef char datatype; typedef struct BinNode{ datatype data; struct BinNode* lchild; struct BinNode* rchild; }BinNode; typedef BinNode* bintree; //bintree本身是个指向结点的指针//前序遍历生成二叉树 void createtree(bintree *t){datatype c...
宝清县15380168358: 求一段简单的建立二叉树的C++代码! - ?
喻帜明欣: /*---二叉树的建立---*/ BTNode *createbintree() { BTNode *t; char x; scanf("%c",&x); if (x=='#') t=NULL; else { t=(BTNode *)malloc(sizeof(BTNode)); t->data=x; t->lchild=createbintree(); t->rchild=createbintree(); } return(t); }
宝清县15380168358: C++建立二叉树 - ?
喻帜明欣: 根据楼主给出的图,可以用下面的代码来进行构建来构建,代码经过实际的运行验证,无错,运行结果是楼主所给的二叉树. 思想:结合先序和中序遍历来构建给定的二叉树. 所给的二叉树图中,先序:A,B,D,E,C,F,G 中序:D,B,E,A,F,C,G 下...
宝清县15380168358: 如何用c++建造一颗二叉树 - ?
喻帜明欣: #include<iostream> using namespace std;// 二叉树结点类 struct BinTreeNode {// 数据成员: double data; // 数据域 BinTreeNode *leftChild; // 左孩子指针域 BinTreeNode *rightChild; // 右孩子指针域 BinTreeNode(){ leftChild = rightChild = ...
宝清县15380168358: C++ 建立二叉树?
喻帜明欣: bool Maketree(NODE<T>* t,const T (&s)[10],int i) 改为 bool Maketree(NODE<T>* &t,const T (&s)[10],int i) 这样对t的修改才能反映到函数之外
宝清县15380168358: C++: 编写程序,创建一个二叉树.实现统计二叉树叶子结点的个数和二叉树的深度 - ?
喻帜明欣: #include typedef int ElemType; //数据类型//定义二叉树结构,与单链表相似,多了一个右孩子结点 typedef struct BiTNode{ ElemType data; //数据域 struct BiTNode*lChild, *rChlid; //左右子树域 }BiTNode, *BiTree;//先序创建二叉树 int ...
宝清县15380168358: C++中生成一个二叉树 - ?
喻帜明欣: 我的VC6的WIN32的,不能用拉倒.#include using namespace std; struct tree { int data; struct tree *l,*r; }; void insert(tree *&proot,tree *pnode) { if(proot==NULL) { proot=pnode; return; } else { if(proot->datadata) { insert(proot->l,pnode); } else insert(...
宝清县15380168358: 用C++实现输出一个二叉树的程序 - ?
喻帜明欣: // 旋转90度打印指定的二叉树 void PrintTree(BTreeNode *t, int n) { int i; if(t != NULL){ PrintTree(t -> right, n + 1); for(i = 0; i < n - 1; i++) cout << " "; if(n > 0) cout << "--"; cout << t -> data << endl; PrintTree(t -> left, n + 1); } }
宝清县15380168358: 求二叉树树形输出C++代码 - ?
喻帜明欣: 用层次遍历二叉树的代码如下:void print(tree& t) { if(t == NULL) return; tree p; tree qu[n]; int front, rear; front = rear = -1; rear++; qu[rear] = t; while (front != rear) { front = (front + 1) % n; p = qu[front]; cout<<p->data<<" "; if (p->L != NULL) { rear = (...
宝清县15380168358: c++创建一个二叉树 - ?
喻帜明欣: 用引用或双重指针,否则T是形参,值传不回去.void BinaryTree::createTree(Node* &T)