二叉树的创建和遍历，帮忙看下这段程序，总是出错
目的是编写二叉树的创建和遍历，用前序遍历法创建二叉树，以及二叉树的输出，然后实现前序，中序，后序遍历，我的这段老是出错，说前序，后序，中序等等都没有定义，请高手帮忙看看好吗？
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
#include<queue>?
struct BinTreeNode { //二叉树结点类定义
? char data; //数据域
? BinTreeNode *leftChild, *rightChild; //左子女、右子女链域
? BinTreeNode () //构造函数
? { leftChild = NULL; rightChild = NULL; }
BinTreeNode (char x, BinTreeNode *l = NULL, ?
? BinTreeNode *r = NULL)
? { data = x; leftChild = l; rightChild = r; }
};
class BinaryTree {//二叉树类定义
public:
? BinaryTree () : root (NULL) { } //构造函数
? BinaryTree (char value) : RefValue(value), root(NULL) { } //构造函数
BinaryTree (BinaryTree & s); //复制构造函数
? ～BinaryTree () { destroy(root); } //析构函数
? bool IsEmpty () { return root = = NULL;} //判二叉树空否
? int Height () { return Height(root); } //求树高度
? int Size () { return Size(root); } //求结点数
BinTreeNode *Parent (BinTreeNode *t) ?
{ return (root == NULL || root == t) ?
? NULL : Parent (root, t); } //返回双亲结点
? BinTreeNode *LeftChild (BinTreeNode *t)
? { return (t != NULL)？t->leftChild : NULL; } //返回左子女
? BinTreeNode *RightChild (BinTreeNode *t)
? { return (t != NULL)？t->rightChild : NULL; } //返回右子女
? BinTreeNode *getRoot () const { return root; } //取根
void preOrder (void (*visit) (BinTreeNode *t)) ?
? { preOrder (root, visit); } //前序遍历
? void inOrder (void (*visit) (BinTreeNode *t))
? { inOrder (root, visit); } //中序遍历
? void postOrder (void (*visit) (BinTreeNode *t))
? { postOrder (root, visit); } //后序遍历
? void levelOrder (void (*visit)(BinTreeNode *t)); //层次序遍历
? //插入新元素
? //搜索
protected:
? BinTreeNode *root; //二叉树的根指针
? char RefValue; //数据输入停止标志
? void CreateBinTree (istream& in, BinTreeNode *& bt); //从文件读入建树
? //插入
? void destroy (BinTreeNode *& subTree); //删除
? bool Find (BinTreeNode *subTree, T& x); //查找
BinTreeNode *Copy (BinTreeNode *r); //复制
? int Height (BinTreeNode *subTree); //返回树高度
? int Size (BinTreeNode *subTree); //返回结点数
? BinTreeNode *Parent (BinTreeNode * subTree, BinTreeNode *t); //返回父结点
? ?
//搜寻x
void Traverse (BinTreeNode *subTree, ostream& out); //前序遍历输出
? void preOrder (BinTreeNode& bt, void (*visit) (BinTreeNode *t)); //前序遍历
? void inOrder (BinTreeNode& bt, void (*visit) (BinTreeNode *t)); //中序遍历
? void postOrder (BinTreeNode& bt, void (*visit) (BinTreeNode *t));
void PrintBTree(BinTreeNode *bt);
//后序遍历
friend istream& operator >> (istream& in, BinaryTree& Tree); ?
//重载操作：输入
? friend ostream& operator << (ostream& out, BinaryTree& Tree); ?
//重载操作：输出?
? friend int operator= =(const BinaryTree&s,
? const BinaryTree&t); //重载操作：判断两棵二叉树相等
};
void BinaryTree:: CreateBinTree (istream& in, BinTreeNode *& bt){
? char item;
? if (in>>item) {
? if (item != '#') {
? bt = new BinTreeNode(item);
? CreateBinTree (in, bt->leftChild);
? CreateBinTree (in, bt->rightChild);
? }
? else subTree = NULL;
? }
}
void BinaryTree:: PrintBTree (BinTreeNode *bt){
? if(bt!=null)
? {
? cout<<bt->data;
if(bt->leftChild!=null || bt->rightChild !=null){
cout<<'(';
PrintBTree(vt->leftChild);
cout<<',';
if(bt->rightChild!=null)
PrintBTree(bt->rightChild);
cout<<')';
}
? }
}
void BinaryTree:: inOrder (BinTreeNode &bt,void(* visit)(BinTreeNode *t)){
if(bt!=null){
InOrder(bt->leftChild);
visit(bt);
InOrder(bt->rightChild);
}
}
void BinaryTree:: preOrder (BinTreeNode &bt,void(* visit)(BinTreeNode *t)){
if(bt!=null){
? visit(bt);
InOrder(bt->leftChild);
InOrder(bt->rightChild);
}
}
void BinaryTree:: postOrder (BinTreeNode &bt,void(* visit)(BinTreeNode *t)){
if(bt!=null){
InOrder(bt->leftChild);
InOrder(bt->rightChild);
visit(bt);
}
}
void print(BinTreeNode *bt){
cout<<bt->data;
}
void main()
{
void print(BinTreeNode *bt);
? istream& myin;
?BinTreeNode * root;
?CreateBinTree (myin , root);
PrintBTree(root);
inOrder(root,print);
preOrder(root,print);
postOrder(root,print);
}
[解决办法]
哥们，估计没人会花时间看这么长的代码喔。
[解决办法]
楼主说下出错信息，或者出错的什么个情况？
[解决办法]
LZ代码贴进去试了试，错误太多，而且C++与C混用.....
贴一个先序遍历的代码作为参考
#include <iostream>using namespace std;template<class T>void Visit(T& x){ cout<<x<<" ";}template<class T>struct BTNode{BTNode(){ lChild=rChild=NULL;}BTNode(const T& x){element=x; lChild=rChild=NULL; }BTNode(const T& x, BTNode<T>* l,BTNode<T>* r){element=x; lChild=l; rChild=r;}T element;BTNode<T>* lChild, *rChild;};template<class T>class BinaryTree{public: BinaryTree(){root=NULL;} //~BinaryTree(){Clear();} //bool IsEmpty()const; //void Clear(); bool Root(T &x)const; void MakeTree(const T &e ,BinaryTree<T>&left, BinaryTree<T>& right); void BreakTree(T &e ,BinaryTree<T>&left, BinaryTree<T>& right); void PreOrder(void (*Visit)(T& x)); //void InOrder(void (*Visit)(T& x)); //void PostOrder(void (*Visit)(T& x));protected: BTNode<T>* root;private: //void Clear(BTNode<T>* t); void PreOrder(void (*Visit)(T& x),BTNode<T>*t); //void InOrder(void (*Visit)(T& x),BTNode<T>*t); //void PostOrder(void (*Visit)(T& x),BTNode<T>*t);};template <class T>bool BinaryTree<T>::Root(T &x)const{if(root){ x=root->element; return true; } else return false;}template <class T>void BinaryTree<T>::MakeTree(const T &x ,BinaryTree<T>&left,BinaryTree<T>& right){ if(root||&left==&right) return; root=new BTNode<T>(x,left.root, right.root); left.root=right.root=NULL;}template <class T>void BinaryTree<T>::BreakTree(T &x, BinaryTree<T>&left, BinaryTree<T>& right){ if (!root||&left==&right||left.root||right.root)return; x=root->element; left.root=root->lChild;right.root=root->rChild; delete root;root=NULL;}template <class T>void BinaryTree<T>::PreOrder(void (*Visit)(T& x)){PreOrder(Visit,root);}template <class T>void BinaryTree<T>::PreOrder(void (*Visit)(T& x),BTNode<T>* t){if (t){ Visit(t->element); PreOrder(Visit,t->lChild); PreOrder(Visit,t->rChild); }}int main(){ BinaryTree<char> a,b,x,y,z; y.MakeTree('E',a,b); z.MakeTree('F',a,b); x.MakeTree('C',y,z); y.MakeTree('D',a,b); z.MakeTree('B',y,x); z.PreOrder(Visit); x.PreOrder(Visit); y.PreOrder(Visit); return 0;}
[解决办法]
楼主照着上面的改吧 你程序错误点太多了
[解决办法]
你的错误太多：
二叉树的建立与遍历//* * * * * * * * * * * * * * * * * * * * * * * *//*PROGRAM :二叉树 *//*CONTENT :建立，前序、中序、后序遍历 *//* * * * * * * * * * * * * * * * * * * * * * * *#include <dos.h>#include <conio.h>#include <stdio.h>#include <stdlib.h>enum BOOL{False,True};typedef struct BiTNode //定义二叉树节点结构{char data; //数据域struct BiTNode *lchild,*rchild; //左右孩子指针域}BiTNode,*BiTree;void CreateBiTree(BiTree &); //生成一个二叉树void PreOrder(BiTree); //先序递归遍历二叉树void InOrder(BiTree); //中序递归遍历二叉树void PostOrder(BiTree); //后序递归遍历二叉树void main(){BiTree T; char ch,j;int flag=1;BOOL temp;textbackground(3); //设定屏幕颜色textcolor(15);clrscr();//---------------------程序解说-----------------------printf("本程序实现二叉树的操作。\n");printf("可以进行建立二叉树，递归先序、中序、后序遍历等操作。\n");//----------------------------------------------------printf("请将先序遍历二叉树的结果输入以建立二叉树。\n");printf("对于叶子结点以空格表示。\n");printf("例如:abc de g f (回车)，建立如下二叉树：\n");printf(" a \n");printf(" / \n");printf(" b \n");printf(" / \\ \n");printf(" c d \n");printf(" / \\ \n");printf(" e f \n");printf(" \\ \n");printf(" g \n");CreateBiTree(&T); //初始化树getchar();while(flag){ printf("请选择: \n");printf("1.递归先序遍历\n");printf("2.递归中序遍历\n");printf("3.递归后序遍历\n");printf("4.退出程序\n");scanf(" %c",&j);switch(j){case '1':if(T){printf("先序遍历二叉树:");PreOrder(T);printf("\n");}else printf("二叉树为空!\n");break;case '2':if(T){printf("中序遍历二叉树:");InOrder(T);printf("\n");}else printf("二叉树为空!\n");break;case '3':if(T){printf("后序遍历二叉树:");PostOrder(T);printf("\n");}else printf("二叉树为空!\n");break;default:flag=0;printf("程序运行结束，按任意键退出!\n");}}getch();}void CreateBiTree(BiTree &T){char ch;scanf("%c",&ch); //读入一个字符 if(ch==' ') T=NULL;else {(*T)=(BiTNode *)malloc(sizeof(BiTNode)); //生成一个新结点T->data=ch;CreateBiTree(&((*T)->lchild)); //生成左子树CreateBiTree(&((*T)->rchild)); //生成右子树}}void PreOrder(BiTree T){if(T){printf("%c",T->data); //访问结点PreOrder(T->lchild); //遍历左子树PreOrder(T->rchild); //遍历右子树}}void InOrder(BiTree T){if(T){InOrder(T->lchild); //遍历左子树 printf("%c",T->data); //访问结点InOrder(T->rchild); //遍历右子树}}void PostOrder(BiTree T){if(T){PostOrder(T->lchild); //遍历左子树PostOrder(T->rchild); //访问结点printf("%c",T->data); //遍历右子树}}
[解决办法]
看我这段。
[解决办法]
是这一段，呵呵，刚才发错了：
#include <iostream>#include <queue>using namespace std;#define TREELEN 6struct NODE{ NODE *pLeft; NODE *pRight; char chValue;};void PostOrder(NODE *head){ if(head) { PostOrder(head->pLeft); PostOrder(head->pRight); cout << head->chValue << "\t"; } }void LevelOrder(NODE *head){ if(head) { queue<NODE *> qu; NODE *p; qu.push(head); while(!qu.empty()) { p = qu.front(); qu.pop(); cout << p->chValue << "\t"; if(p->pLeft != NULL) qu.push(p->pLeft); if(p->pRight != NULL) qu.push(p->pRight); } }} void ReBuild(char *pPreOrder, char *pInOrder, int nTreeLen, NODE **pRoot){ if(pPreOrder == NULL || pInOrder == NULL) return; NODE *pTemp = new NODE; pTemp->chValue = *pPreOrder; pTemp->pLeft = NULL; pTemp->pRight = NULL; if(*pRoot == NULL) *pRoot = pTemp; if(nTreeLen == 1) return; char *pOrgInOrder = pInOrder; char *pLeftEnd = pInOrder; int nTempLen = 0; while(*pPreOrder != *pLeftEnd) { if(pPreOrder == NULL || pLeftEnd == NULL) return; nTempLen++; if(nTempLen > nTreeLen) break; pLeftEnd++; } int nLeftLen = 0; nLeftLen = (int)(pLeftEnd - pOrgInOrder); int nRightLen = 0; nRightLen = nTreeLen - nLeftLen - 1; if(nLeftLen > 0) ReBuild(pPreOrder + 1, pInOrder, nLeftLen, &((*pRoot)->pLeft)); if(nRightLen > 0) { ReBuild(pPreOrder + nLeftLen + 1, pInOrder + nLeftLen + 1, nRightLen, &((*pRoot)->pRight)); }}int main(){ char szPreOrder[TREELEN] = {'a', 'b', 'd', 'c', 'e', 'f'}; char szInOrder[TREELEN] = {'d', 'b', 'a', 'e', 'c', 'f'}; NODE *pRoot = NULL; ReBuild(szPreOrder, szInOrder, TREELEN, &pRoot); PostOrder(pRoot); cout << endl; PreOrder(pRoot); cout << endl; LevelOrder(pRoot); cout << endl; system("pause"); return 0;}