二叉树的建立与遍历（二）（c++实现）

【目标】

建立如下所示的一棵二叉树，，并且输出其对应的前序遍历、中序遍历、后序遍历。

【代码实现】<class T> class Binarytree;template<class T>class TreeNode{friend class Binarytree<T>;private:T data;TreeNode<T> *rchild; //右指针指向右子树TreeNode<T> *lchild; //左指针指向左子树};template<class T>class Binarytree{public:Binarytree(){root=0;};void Creattree2();void Creattree2(TreeNode<T> *&currentnode);//使用指针引用建立二叉树void Preorder();void Preorder(TreeNode<T> *currentnode); //前序遍历void Inorder();void Inorder(TreeNode<T> *currentnode); //中序遍历void Postorder();void Postorder(TreeNode<T> *currentnode); //后序遍历private:TreeNode<T> *root;};//————–先序递归创建二叉树——–template<class T>void Binarytree<T>::Creattree2(){ Creattree2(root);}template<class T>void Binarytree<T>::Creattree2(TreeNode<T> *&currentnode){ //按先序输入二叉树中结点的值（一个字符），空格字符代表空树， char ch; if((ch=getchar())==’#’) { currentnode=0; } else {currentnode=new TreeNode<T>();//产生新的子树 currentnode->data=ch; Creattree2(currentnode->lchild);//递归创建左子树 Creattree2(currentnode->rchild);//递归创建右子树 } }//——递归实现二叉树的前序遍历——template<class T>void Binarytree<T>::Preorder() {cout<<“前序遍历（根->左->右）为：”;Preorder(root); }template<class T>void Binarytree<T>::Preorder(TreeNode<T> *currentnode){ if(currentnode) {cout<<currentnode->data<<” “;Preorder(currentnode->lchild);Preorder(currentnode->rchild); }}//——递归实现二叉树的中序遍历——template<class T>void Binarytree<T>::Inorder() {cout<<“中序遍历（左->根->右）为：”;Inorder(root); }template<class T>void Binarytree<T>::Inorder(TreeNode<T> *currentnode){ if(currentnode) {Inorder(currentnode->lchild);cout<<currentnode->data<<” “;Inorder(currentnode->rchild); }}//——递归实现二叉树的后序遍历——template<class T>void Binarytree<T>::Postorder() {cout<<“后序遍历（左->右->根）为：”;Postorder(root); }template<class T>void Binarytree<T>::Postorder(TreeNode<T> *currentnode){ if(currentnode) {Postorder(currentnode->lchild);Postorder(currentnode->rchild);cout<<currentnode->data<<” “; }}#endif;int main(){ Binarytree<char> Tree1; Tree1.Creattree2(); Tree1.Preorder(); cout<<endl; Tree1.Inorder(); cout<<endl; Tree1.Postorder(); cout<<endl; system(“pause”); return 0;}【结果图】

饶人不是痴汉，痴汉不会饶人。

相关文章：

你感兴趣的文章：

标签云：