这里基本上包括二叉树所有 *** 作了，楼主自取所需吧：
#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) qInQueue(t);
while (!qEmpty())
{ qOutQueue(t);
cout<<(t->data)<<" ";
if (t->leftChild != NULL)
qInQueue(t->leftChild);
if (t->rightChild != NULL)
qInQueue(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 = btGetRoot();
cout<<"请输入根节点左孩子的数值:";
cin>>e;
btInsertLeftChild(cur, e);
cout<<"请输入根节点右孩子的数值:";
cin>>e;
btInsertRightChild(cur, e);
cout<<"请输入根节点左孩子的左孩子的数值:";
cin>>e;
btInsertLeftChild(cur->leftChild, e);
cout<<"请输入根节点右孩子的左孩子的数值:";
cin>>e;
btInsertLeftChild(cur->rightChild, e);
cout<<"请输入根节点右孩子的右孩子的数值:";
cin>>e;
btInsertRightChild(cur->rightChild,e);
cout << "先序遍历:" << endl;
btPreOrder();
cout<<endl;
system("PAUSE");
cout << "中序遍历:" << endl;
btInOrder();
cout<<endl;
system("PAUSE");
cout << "后序遍历:" << endl;
btPostOrder();
cout<<endl;
system("PAUSE");
cout << "层次遍历:" << endl;
btLevelOrder();
cout<<endl;
system("PAUSE");
cout<<"树的高度为"<<btHeight()<<endl;
cout<<"树中节点数为"<<btNodeCount()<<endl;
cout<<"树中叶子节点数为"<<btleafNodeCount()<<endl;
return 0;
}
ps：该程序包含二叉树的建立，以及前序遍历、中序遍历、后续遍历。
如有不懂，我再详解
#include<stdioh>
#include<stdlibh>
typedef
struct
node
{
char
data;
struct
node
lchild,rchild;
}binary_tree,tree;
void
creat_tree(tree
&t)
{
char
ch;
ch=getchar();
//使用if((ch=getchar())=='#')
或者ch=getchar();都只能一下子输入所有字符，而用c语言的cin可以一个个输入。
if(ch=='#')
t=NULL;
//表示空子树
else
{
t=(binary_tree)malloc(sizeof
(binary_tree));
//
如果用c++语言
t=new
binary_tree;
if(!t)
exit(1);
//exit(1)表示异常退出这个1是返回给 *** 作系统的不过在DOS好像不需要这个返回值
;exit(0)表示正常退出
t->data=ch;
creat_tree(t->lchild);
creat_tree(t->rchild);
}
}
void
pre_travel(tree
&t)
//前序遍历：根结点->左子树->右子树
{
if(t)
{
printf("%c",t->data);
pre_travel(t->lchild);
pre_travel(t->rchild);
}
}
void
mid_travel(tree
&t)
//中序遍历：左子树->根结点->右子树
{
if(t)
{
mid_travel(t->lchild);
printf("%c",t->data);
mid_travel(t->rchild);
}
}
void
post_travel(tree
&t)
//后序遍历：左子树->右子树->根结点
{
if(t)
{
post_travel(t->lchild);
post_travel(t->rchild);
printf("%c",t->data);
}
}
void
main()
{
tree
t;
printf("输入二叉树的数据(#
代表
空子树)
比如:
fca##db###e#gh##p##\n");
creat_tree(t);
printf("前序遍历:\n");
pre_travel(t);
printf("\n");
printf("中序遍历:\n");
mid_travel(t);
printf("\n");
printf("后续遍历:\n");
post_travel(t);
printf("\n");
}
修改好了。
1、输入的时候，要对本次输入进行清空一下，以免对后续的输入产生影响
2、创建树的参数，要用指针的指针，否则无法将赋的NULL值，传递出来
正确的程序如下：
#include<stdioh>
#include<malloch>
typedef struct node
{
char data;
struct node lchild,rchild;
}Tree;
void Init(Tree t)
{
char ch;
printf("input a char:\n");
scanf("%c",&ch);
fflush(stdin);
if(ch=='#') (t)=NULL;
//if(ch=='%')return;
else
{
(t)=(Tree)malloc(sizeof(Tree));
(t)->data=ch;
Init(&(t)->lchild);
Init(&(t)->rchild);
}
}
void Xbl(Tree t)
{
if(t)//while(t)
{
printf("%c ",t->data);
Xbl(t->lchild);
Xbl(t->rchild);
}
}
main()
{
Tree t;
Init(&t);
Xbl(t);
getchar();
}
分太少啊
#include <stdlibh>
#include <stdioh>
#define MAXL 100
typedef char Elemtype ;
typedef struct
{
Elemtype e;
} Elem;
typedef struct BTree
{
Elem data;
struct BTree lchild,rchild;
} BITnode,BTree;
void Createtree(BTree T) //创建二叉树
{
Elemtype a;
scanf("%c",&a);
if (a == '@' )
{
T = NULL;
}
else
{
T = (BTree)malloc(sizeof(BITnode));
if(!T)
{
exit(1);
}
(T)->datae = a;
Createtree(&(T)->lchild);
Createtree(&(T)->rchild);
}
return ;
}
//前序遍历
void PreTravel(BTree T)
{
if(T)
{
printf(" %c",T->datae);
PreTravel(T->lchild);
PreTravel(T->rchild);
}
}
//中序遍历
void MidTravel(BTree T)
{
if(T)
{
MidTravel(T->lchild);
printf(" %c",T->datae);
MidTravel(T->rchild);
}
}
//后序遍历
void PostTravel(BTree T)
{
if(T)
{
PostTravel(T->lchild);
PostTravel(T->rchild);
printf(" %c",T->datae);
}
}
//递归计算叶子数
int Count_leaf(BTree T)
{
if (T == NULL)
{
return 0;
}
else if (T->lchild == NULL && T->rchild == NULL)
{
return 1;
}
else
{
return Count_leaf(T->lchild) + Count_leaf(T->rchild);
}
}
///非递归计算叶子结点个数
///用栈存放节点 Not_Leaf_Count计算叶子结点个数
typedef struct
{
int top;
BTree MAXSIZE[MAXL];
} Stack, Le_Node;
int Not_Count_Leaf(BTree T)
{
int Not_Leaf_Count = 0;
Stack s;
s = (Stack )malloc(sizeof(Le_Node));
s ->top =0;
while (T != NULL || s->top != 0)
{
if (T != NULL)
{
s->MAXSIZE[s->top] = T;
s->top ++;
T = T->lchild;
}
else
{ s->top --;
T = s->MAXSIZE[s->top];
if (T->lchild == NULL && T->rchild == NULL)
{
Not_Leaf_Count++;
}
T = T->rchild;
}
}
return Not_Leaf_Count;
}
//计算二叉树的高度
int Height_Bitree(BTree T)
{
int h1,h2;
if (T != NULL)
{
h1 = Height_Bitree(T->lchild);
h2 = Height_Bitree(T->rchild);
if (h1 > h2)
{
return h1+1;
}
else
{
return h2+1;
}
}
else
return 0;
}
//非递归计算二叉树高度
int Not_Height_Bitree(BTree T)
{
BTree Que[MAXL];
int hp = 0,dp = 0,rear = 0,tp = 1,lc = 1;
BTree p;
if (T != NULL) //根节点入队
{
Que[rear++] = T;
}
while (rear != 0)
{
p = Que[--rear];//队头元素出队
hp ++; //为已访问的节点数
if (p->lchild != NULL)
{
Que[rear++] = p->lchild;
tp ++; //记录历史入队的节点数
}
if (p->rchild != NULL)
{
Que[rear++] = p->rchild;
tp ++;
}
if(hp == lc) //当hp = lc时，表明本层节点均已访问完
{
dp ++;
lc = tp;
}
}
return dp;
}
//按层次遍历
void Level_Travel(BTree T)
{
BTree Que[MAXL];
int front = 0,rear = 0;
BTree p;
if (T != NULL) //根节点入队
{
Que[rear] = T;
rear = (rear+1)%MAXL;
}
while (front != rear)
{
p = Que[front];//队头元素出队
front = (front +1)% MAXL;
printf(" %c",p->datae);
if (p->lchild != NULL)
{
Que[rear] = p->lchild;
rear = (rear + 1)%MAXL;
}
if (p->rchild != NULL)
{
Que[rear] = p->rchild;
rear = (rear+1)%MAXL;
}
}
return ;
}
//非递归先序遍历
void NPreTravel(BTree T)
{
BTree stack[MAXL];
BTree p;
int top ;
if (T != NULL)
{
top = 0;
p = T;
while (p != NULL || top > 0)
{
while (p != NULL)
{
printf(" %c",p->datae);
stack[top] = p;
top ++;
p = p->lchild;
}
if (top > 0)
{
top--;
p = stack[top];
p = p->rchild;
}
}
}
}
//非递归中序遍历
void NMidTravel(BTree T)
{
BTree stack[MAXL];
BTree p;
int top;
if (T != NULL)
{
top = 0;
p = T;
while (p != NULL || top > 0)
{
while (p != NULL)
{
stack[top] = p;
top ++;
p = p->lchild;
}
if (top > 0)
{
top--;
p = stack[top];
printf(" %c",p->datae);
p = p->rchild;
}
}
}
}
//非递归后续遍历
typedef struct
{
BTree ptr;
int tag;
} stacknode;
void NPostTravel(BTree T)
{
stacknode s[MAXL];
stacknode x;
BTree p = T;
int top;
if (T != NULL)
{
top = 0;
p = T;
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 = xptr;
printf(" %c",p->datae); //tag 为2 表示右子数访问完毕，故访问根节点
}
if (top > 0)
{
s[top-1]tag = 2; //遍历右子树
p = s[top-1]ptr->rchild;
}
}
while (top > 0);
}
}
void menu()
{
printf("----------------------------------------------\n\n");
printf("0:退出\n");
printf("1:创建二叉树\n");
printf("2:递归前序遍历\n3:非递归前序遍历\n");
printf("4:递归中序遍历\n5:非递归中序遍历\n");
printf("6:递归后续遍历\n7:非递归后续遍历\n");
printf("8:递归计算叶子数\n9:非递归计算叶子数\n");
printf("10:递归计算高度 \n11:非递归计算高度\n");
printf("12:按层次遍历\n");
printf("-----------------------------------------------\n");
return ;
}
int main()
{
BTree T = NULL;
int select ;
menu();
do
{
printf("输入您的选择：");
scanf("%d",&select);
switch (select)
{
case 0:
{
printf("退出\n");
break ;
}
case 1:
{
printf("创建二叉树\n");
printf("输入数据，以@结束\n");
Createtree(&T);
break;
}
case 2:
{
printf("递归前序遍历\n");
PreTravel(T);
break;
}
case 3:
{
printf("非递归前序遍历\n");
NPreTravel(T);
break;
}
case 4:
{
printf("递归中序遍历\n");
MidTravel(T);
break;
}
case 5:
{
printf("非递归中序遍历\n");
NMidTravel(T);
break;
}
case 6:
{
printf("递归后序遍历\n");
PostTravel(T);
break;
}
case 7:
{
printf("非递归后序遍历\n");
NPostTravel(T);
break ;
}
case 8:
{
printf("递归计算叶子数为：%d\n",Count_leaf(T));
break ;
}
case 9:
{
printf("非递归计算叶子数为：%d\n",Not_Count_Leaf(T));
break;
}
case 10:
{
printf("递归计算高度\n");
printf("高度为：%d\n",Height_Bitree(T));
break;
}
case 11:
{
printf("非递归计算高度\n");
printf("高度为：%d\n",Not_Height_Bitree(T));
break;
}
case 12:
{
printf("按层次遍历二叉树\n");
Level_Travel(T);
break;
}
default :
;
}
}
while (select);
printf("-------------欢迎-----------\n");
system("pause");
return 0;
}
先看下creat这个函数:
status creat(bitnode t)/先序建立二叉树/
{
char ch;
ch=getch();putch(ch);
if(ch=='0') t=NULL;
else
{
t=(bitnode )malloc(sizeof(bitnode));
if(!t)
exit(OVERFLOW);
t->data=ch;
creat(t->lchild);
creat(t->rchild);
}
return OK;
}
其中有句代码是t=(bitnode )malloc(sizeof(bitnode));
这是给t赋值，由于t是参数，这样做是不能返回的。
我知道你的意思是想通过指针返回，但是那样的用法应该是对t所指向的变量赋值，也就是对t赋值。
如果你还没理解的话看下函数里的递归调用：creat(t->lchild);调用函数后，本意是要给t->lchild赋值的，但是是做不到的，因为要改变一个变量的值的话，应该传的是它的地址。
可能你觉得有点乱了，我举个函数中用指针做参数来返回的例子：
假如要用指针返回一个整型的变量，那么指针应该是指向整型变量的，即int
这里应该是要返回一个struct bitnode 类型的，也就是返回的值就是个指针，那么参数就应该是一个指向这种指针的指针，即struct bitnode
可以这么修改：
status creat(bitnode t) //多了个
{
char ch;
ch=getch();putch(ch);
if(ch=='0') t=NULL; //多了个
else
{
t=(bitnode )malloc(sizeof(bitnode)); //多了个
if(!t) //多了个
exit(OVERFLOW);
(t)->data=ch;
creat(&(t)->lchild); //注意不同
creat(&(t)->rchild);
}
return OK;
}
主函数这么改
status main()
{
bitnode t1; //多了个
creat(&t1);
pre(t1,print); //少了个&
getch();
return 0;
}
另外一个编译错误就是
int pre(bitnode t,status (visit)())
指针函数后面应该带参数，改为
int pre(bitnode t,status (visit)(bitnode ))
以上就是关于求用c++建立一棵二叉树的程序代码全部的内容，包括:求用c++建立一棵二叉树的程序代码、急求二叉树的创建和递归遍历程序代码C++、请教关于建立二叉树程序（c语言的）等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）