`
香煎马鲛鱼
  • 浏览: 109551 次
  • 性别: Icon_minigender_2
社区版块
存档分类
最新评论

二叉树最简单实现(c++)

    博客分类:
  • C++
阅读更多

二叉树的实现

这是我复习的第三部分,二叉树的实现,这次需要的代码比较少,所以把主函数贴出来了,注释也很清晰,所以大家直接看代码吧:

//树

#ifndef BINNODE_H

#define BINNODE_H

template<class Elem>

class BinNode{

public:

virtual Elemval() = 0;

virtual void setVal(const Elem&) = 0;

virtual void setValBinNode<Elem>* b) = 0;

virtual BinNodeleft() const = 0;

virtual void setLeft(BinNode*) = 0;

virtual BinNoderight() const = 0;

virtual void setRight(BinNode*) = 0;

virtual bool isLeaf() = 0;

};

#endif

 

//建树操作

#ifndef BINNODEPTR_H

#define BINNODEPTR_H

#include "BinNode.h"

template <class Elem>

class BinNodePtr:public BinNode<Elem>{

private:

Elem it;

BinNodePtr* lc;

BinNodePtr* rc;

public:

BinNodePtr(){lc = rc = NULL;}

BinNodePtr(Elem e,BinNodePtrl = NULL,BinNodePtrr = NULL){

it = e; lc = l; rc = r;

}

~BinNodePtr(){}

Elemval(){

return it;

}

void setVal(const Eleme){

it = e;

}

void setValBinNode<Elem>* b){

 

}

inline BinNode<Elem>* left()const{return lc;}

void setLeft(BinNode<Elem>* b){lc = (BinNodePtr*)b;}

    inline BinNode<Elem>* right()const{return rc;}

void setRight(BinNode<Elem>* b){rc = (BinNodePtr*)b;}

bool isLeaf(){

return (lc==NULL)&&(rc==NULL);

}

};

#endif BINNODEPTR_H

 

 

//树,这里实现了树的几种方法

//

//(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根 - 左 - 右。

//

//(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左 - 根 - 右。

//

//(3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左 - 右 - 根。

#include<iostream>

using namespace std;

#include"BinNode.h"

#include"BinNodePtr.h"

template <class Elem>

//建树

//          a

//         / \

//        b   c

//       / \   \

//      d   e   f

//建立此二叉树的方法为:(abd  e  c f  )

BinNode<Elem>* CreateBinTree(){

BinNode<Elem>* t;

char ch;

if ((ch = getchar()) == ' ')

{

//如果是空格表示空,后面没有节点了;

return NULL;

}

else

{

//输入值

t = new BinNodePtr<Elem>(ch);

//左孩子

t->setLeft(CreateBinTree<Elem>());

//右孩子

t->setRight(CreateBinTree<Elem>());

}

return t;

}

template <class Elem>

//复制该树

BinNode<Elem>* CopyBinTree(BinNode<Elem>* p){

BinNode<Elem>* t;

t= new BinNodePtr();

t->setVal(p->val());

if (t->val()==NULL)return NULL;

else

{

t->setLeft(CopyBinTree<Elem>(p->left()));

t->setRight(CopyBinTree<Elem>(p->right()));

}

return t;

}

template <class Elem>

//输出单个节点

void visit(BinNode<Elem>* subroot){

cout<<subroot->val();

}

template <class Elem>

//前序

void preorder(BinNode<Elem>* subroot){

if(subroot == NULLreturn;

visit(subroot);//根

preorder(subroot->left());//左

preorder(subroot->right());//右

}

template <class Elem>

//中序

void inorder(BinNode<Elem>* subroot){

if(subroot == NULLreturn;

inorder(subroot->left());//左

visit(subroot);//根

inorder(subroot->right());//右

 

}

//后序遍历

template <class Elem>

void backorder(BinNode<Elem>* subroot){

if (subroot == NULLreturn;

backorder(subroot->left());//左

backorder(subroot->right());//右

visit(subroot);//根

 

}

template <class Elem>

//左右孩子互换

//我们仍然举一个例子

//          a

//         / \

//        b   c

//       / \   \

//      d   e   f

void swithOrder(BinNode<Elem>* subroot){

//如果要置换的树是空的,结束

if(subroot==NULLreturn;

visit(subroot);

//声明一个空间,用来临时存放节点

BinNode<Elem>* t;

char ch=' ';

t = new BinNodePtr<Elem>(ch);

//t临时存放右边节点

//          a

//         / \

//        b   c

//       / \   \

//      d   e   f

//t = b{d e}

t=subroot->left();

//用右边的节点覆盖左边节点

//          a

//         / \

//        c   c

//         \   \

//          f   f

//t = b{d e}

subroot->setLeft(subroot->right());

//把t付给右边节点

//          a

//        /   \

//       c     b

//        \    /\

//         f  d  e 

subroot->setRight(t);

//递归,最终结果为

//          a

//        /   \

//       c     b

//      /      /\

//     f      e  d 

swithOrder(subroot->left());

swithOrder(subroot->right());

}

int main(){

cout << "请输入:abd(空格)(空格)e(空格)(空格)c(空格)f(空格)(空格)(回车)" << endl;

BinNode<char>* tree;

tree = CreateBinTree<char>();

inorder<char>(tree);

cout<<endl;

swithOrder<char>(tree);

    cout<<endl;

inorder<char>(tree);

cout << endl;

backorder<char>(tree);

    cout<<endl;

system("pause");

}

 

0
0
分享到:
评论

相关推荐

    C++排序二叉树模板

    在这个“C++排序二叉树模板”中,我们将会探讨二叉树的基本概念、常用操作以及如何在C++中实现这些操作。 首先,我们要了解二叉排序树(Binary Search Tree,BST)。这是一种特殊的二叉树,其中每个节点的值都大于...

    二叉树 中序遍历c++实现

    本文将详细讲解如何用C++实现二叉树的中序遍历。 首先,我们需要定义一个二叉树节点的结构体。这个结构体通常包含三个成员:一个整型的数据域(用于存储节点值),一个指针指向左子节点,以及一个指针指向右子节点...

    平衡二叉树的详细实现,C++语言

    C++作为一种强大的编程语言,常被用于实现各种数据结构,包括平衡二叉树。 平衡二叉树主要有AVL树和红黑树等类型。AVL树是最早被提出的自平衡二叉搜索树,由G. M. Adelson-Velsky 和 E. M. Landis 在1962年提出,...

    二叉树的实现 c++

    在C++中实现二叉树,我们需要理解二叉树的基本概念和操作,包括如何创建节点、如何进行遍历以及如何进行插入和删除操作。 首先,让我们了解二叉树的基本定义。二叉树是由节点(或称为顶点)组成的有限集合,每个...

    二叉树的C++ 实现

    本文将深入探讨如何在C++中实现二叉树,并提供实用的代码示例。 二叉树由节点构成,每个节点包含两个子节点,分别称为左子节点和右子节点。在C++中,我们可以通过定义一个结构体或类来表示二叉树节点: ```cpp ...

    二叉树遍历C++源代码

    从给定的C++源代码来看,这段代码主要实现了二叉树的基本构建和深度优先遍历中的前序遍历(Preorder Traversal)。下面将详细解析这段代码的关键知识点。 ### 1. 数据结构定义 首先,代码定义了一个`NODE`结构体...

    数据结构课程设计,树与二叉树的转换,C++

    本课程设计探讨的是如何将一般树转换为二叉树,并在C++中实现这一过程。 首先,我们要明确,任何树都可以通过某种方式转换成二叉树,但这种转换并不一定是一一对应的。也就是说,同一棵树可以有多种不同的二叉树...

    基于二叉树的猜动物程序c++

    可以学习的二叉树 最简单的人工智能 c++描写

    查找二叉树中最大结点的C++源代码

    在这个例子中,我们创建了一个简单的二叉树,然后调用`findMax`函数找到最大节点并打印其值。最后,我们使用`deleteTree`函数释放所有分配的内存以防止内存泄漏。 在VC++环境中,你可以编译并运行这个程序,查看...

    平衡排序二叉树的C++算法实现

    本文将详细讲解平衡排序二叉树的C++实现,特别是如何处理插入和删除操作时的平衡化问题。 首先,平衡排序二叉树的核心在于其平衡特性,即树中任意节点的左右子树高度差不超过1。这保证了在最坏情况下,树的查找、...

    简单介绍所有的数据结构,包括数组、队列、二叉树等C、C++

    C++标准库提供了`&lt;queue&gt;`头文件来实现队列,但也可以用数组或链表手动实现。队列在处理并发任务、缓冲区管理和事件调度等场景中非常有用。 **三、二叉树** 二叉树是每个节点最多有两个子节点的树形数据结构。每个...

    树和二叉树的实验报告

    4. **求二叉树的高度**:高度是指从根节点到最远叶子节点的最长路径上的边数。 - 递归计算方法:高度 = max(左子树高度, 右子树高度) + 1。 5. **求二叉树的叶节点个数**: - 叶节点是没有子节点的节点。 - 递归...

    二叉树的层次遍历-C++实现

    本文将详细讨论如何用C++语言实现二叉树的层次遍历。 首先,我们定义了一个`Tree`结构体,包含一个数据成员`data`以及指向左右子节点的指针`lchild`和`rchild`。这里使用了`typedef`关键字,使得我们可以用`Tree`来...

    二叉树实现-二叉树操作

    在C++中实现二叉树,我们需要理解其基本操作,并能有效地进行创建、遍历、查找、插入和删除等操作。 1. **二叉树的定义**: 二叉树由节点组成,每个节点包含一个值、指向左子节点的指针(如果存在)和指向右子节点...

    二叉树各种遍历算法

    对于给定的压缩包文件"二叉树各种遍历算法",其中应该包含了上述各种遍历方法的代码示例,可能包括C++、Java、Python或其他编程语言。通过学习这些代码,你可以深入理解每种遍历方法的实现细节,并且可以运用到实际...

    二叉树的定义与简单应用

    在这个"二叉树的定义与简单应用"的主题中,我们将深入探讨二叉树的定义、遍历方法以及相关的计算问题。 首先,我们来看二叉树的定义。一个二叉树是由若干个节点组成,每个节点包含一个值、一个指向左子树的指针和一...

    子树深度,完全二叉树的计算

    这种结构使得二叉树的插入、删除和遍历操作变得简单。在处理完全二叉树的问题时,通常会利用这种存储结构进行操作。 此外,提到的其他文件如“24点.cpp”、“算术表达式求值.cpp”、“稀疏多项式的乘法实现.cpp”、...

    二叉树C++源代码,模板实现,可用于各种类型

    本项目提供了一套完整的C++源代码,旨在实现一个通用的二叉树模板,使得它能适用于处理各种类型的数据。 首先,`BinaryTree.h` 文件通常包含了二叉树节点的定义以及相关的模板类声明。在这个模板类中,我们可以预见...

    二叉树的生成以及非递归遍历C++实现

    ### 二叉树的生成及非递归遍历C++实现 #### 一、二叉树的基本概念 在深入探讨二叉树的生成与非递归遍历之前,我们先来了解一下二叉树的基本概念。 - **二叉树定义**:二叉树是一种树形结构,其中每个节点最多有两...

Global site tag (gtag.js) - Google Analytics