c++先序二叉树的构建详解

二叉树首先要解决构建问题,才能考虑后续的遍历,这里贴出通过先序构建二叉树,同时包含四种二叉树的遍历方法(先序,中序,后序,逐层)

第一、定义BinaryTreeNode 类

#include <iostream>

#include <string>

#include <queue>

using namespace std;

template<typename T >class BinaryTree;

template <typename T> class BinaryTreeNode {

public:

  friend class BinaryTree<T>;

  BinaryTreeNode() {

    data = NULL;

    lChild = rChild = NULL;

  }

  BinaryTreeNode(T newdata) {

    this->data = newdata;

    lChild = rChild = NULL;

  }

  T getData() {

    return data;

  }

  BinaryTreeNode<T> * getLeftNode() {

    return lChild;

  }

  BinaryTreeNode<T> * getRightNode() {

    return rChild;

  }

  T data;

  BinaryTreeNode<T>* lChild;

  BinaryTreeNode<T>* rChild;

private:

};

View Code

第二、定义BinaryTree 类

template <typename T> class BinaryTree {

public:

  BinaryTreeNode<T> *root;

  char* p;

  BinaryTree() { root = NULL; }

  BinaryTree(T data) {

    root = new BinaryTreeNode<T>(data);

    root->lChild = NULL;

    root->rChild = NULL;

  }

  ~BinaryTree() {

    delete root;

  }

  //构建二叉树并返回

  BinaryTreeNode<T>* CreateTree() {

    BinaryTreeNode<int>* bt = NULL;

    char t;

    cin >> t;

    if (t == '#')

    {

      return NULL;

    }

    else {

      int num = t - '0';

      bt = new BinaryTreeNode<T>(num);

      bt->lChild = CreateTree();

      bt->rChild = CreateTree();

    }

    return bt;

  }

  //先序构建二叉树

  BinaryTreeNode<T>* PreCreateTree() {

    BinaryTreeNode<int>* bt = NULL;

    if (this->root == NULL)

    {

      cout << "请输入根节点(#代表空树):";

    }

    else {

      cout << "请输入节点(#代表空树):";

    }

    char t;

    cin >> t;

    if (t == '#')

    {

      return NULL;

    }

    else {

      int num = t - '0';

      bt = new BinaryTreeNode<T>(num);

      if (this->root == NULL)

      {

        this->root = bt;

      }

      cout << bt->data << "的左孩子";

      bt->lChild = PreCreateTree();

      cout << bt->data << "的右边孩子";

      bt->rChild = PreCreateTree();

    }

    return bt;

  }  

  void preOderTraversal(BinaryTreeNode<T> *bt); //先序遍历

  void inOrderTraversal(BinaryTreeNode<T> *bt); //中序遍历

  void postOrderTraversal(BinaryTreeNode<T> *bt);//后序遍历

  void levelTraversal(BinaryTreeNode<T> *bt);  //逐层遍历

private:

};

template <typename T>

void BinaryTree<T>::preOderTraversal(BinaryTreeNode<T> *bt) {

  if (bt)

  {

    cout << bt->data;

    BinaryTree<T>::preOderTraversal(bt->getLeftNode());

    BinaryTree<T>::preOderTraversal(bt->getRightNode());

  }

}

template <typename T>

void BinaryTree<T>::inOrderTraversal(BinaryTreeNode<T> *bt) {

  if (bt)

  {

    BinaryTree<T>::inOrderTraversal(bt->getLeftNode());

    cout << bt->data;

    BinaryTree<T>::inOrderTraversal(bt->getRightNode());

  }

}

template <typename T>

void BinaryTree<T>::postOrderTraversal(BinaryTreeNode<T> *bt) {

  if (bt)

  {

    BinaryTree<T>::postOrderTraversal(bt->getLeftNode());

    BinaryTree<T>::postOrderTraversal(bt->getRightNode());

    cout << bt->data;

  }

}

template <typename T>

void BinaryTree<T>::levelTraversal(BinaryTreeNode<T> *bt) {

  queue<BinaryTreeNode<T>*> que;

  que.push(bt);

  while (!que.empty())

  {

    BinaryTreeNode<T>* proot = que.front();

    que.pop();

    cout << proot->data;

    if (proot->lChild != NULL)

    {

      que.push(proot->lChild);//左孩子入队

    }

    if (proot->rChild != NULL)

    {

      que.push(proot->rChild);//右孩子入队

    }

  }

}

View Code

第三、主程序运行

#include "pch.h"

#include <iostream>

#include "BinaryTree.h"

int main()

{

  //场景测试2

  BinaryTree<int> btree;

  btree.PreCreateTree();//先序构建二叉树

  cout << "先序遍历:";

  btree.preOderTraversal(btree.root); cout << endl;//先序遍历  

  cout << "中序遍历:";

  btree.inOrderTraversal(btree.root); cout << endl;//中序遍历

  cout << "后序遍历:";

  btree.postOrderTraversal(btree.root); cout << endl;//后序遍历

  cout << "逐层序遍历:";

  btree.levelTraversal(btree.root);

}

View Code

最终测试运行截图

(0)

相关推荐

  • C++实现二叉树基本操作详解

    树是一种重要的非线性数据结构,二叉树是树型结构的一种重要类型.本学年论文介绍了二叉树的定义,二叉树的存储结构,二叉树的相关术语,以此引入二叉树这一概念,为展开二叉树的基本操作做好理论铺垫.二叉树的基本操作主要包含以下几个模块:二叉树的遍历方法,计算二叉树的结点个数,计算二叉树的叶子结点个数,二叉树深度的求解等内容. 前序遍历(递归&非递归) 访问根节点 前序访问左子树 前序访问右子树 //前序非递归 void PrevOrder() { stack<Node*> s; Node *cu

  • C++ 数据结构完全二叉树的判断

    C++ 数据结构完全二叉树的判断 完全二叉树(Complete Binary Tree):若设二叉树的深度为h,除第h层外,其他各层(1~h-1)的节点数都达到最大个数,第h层所有的节点都连续集中在最左边,这就是完全二叉树.完全二叉树由满二叉树而引起来的.对于深度为K的,有n个节点的二叉树,当且仅当每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树. 注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树. 完全二叉树的特点:完全二叉树的效率极高,堆是一种完全二

  • C++ 遍历二叉树实例详解

    C++ 遍历二叉树实例详解 2叉数又叫红黑树,关于2叉数的遍历问题,有很多,一般有三种常用遍历方法: (1)前序遍历(2)中序遍历(3)后续遍历 以下是经典示例: #include "stdafx.h" #include<stdio.h> #include<malloc.h> #include <math.h > #define MaxSize 20 typedef struct BiTNode { int data; struct BiTNode

  • C++ 二叉树的镜像实例详解

    二叉树的镜像:将一个二叉树的左右子树,调换位置.即下图的形式: 递归的思想是: 从根节点的左右子树进行交换,然后以根节点的左子树为根节点,而后以根节点的右结点为根节点,进行左右子树交换.遇到空节点或叶节点直接返回.下面求二叉树镜像的函数代码实现: template<class T> void MirroTree(TreeNode<T> * root) { if (root == NULL) return; if (root->_left == NULL &&

  • C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)

    C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree

  • C++二叉树实现词频分析功能

    通过二叉树存单词,并且对总共的单词数量进行计数,二叉树自适应的将出现频率高的单词往上移动以减少二叉树的搜索时间. 代码如下 /***********************genSplay.h***********************/ #ifndef _GENSPLAY_H_ #define _GENSPLAY_H_ #include <iostream> using namespace std; //树节点 template<class T> class SplayingN

  • c++先序二叉树的构建详解

    二叉树首先要解决构建问题,才能考虑后续的遍历,这里贴出通过先序构建二叉树,同时包含四种二叉树的遍历方法(先序,中序,后序,逐层) 第一.定义BinaryTreeNode 类 #include <iostream> #include <string> #include <queue> using namespace std; template<typename T >class BinaryTree; template <typename T> c

  • MySQL8新特性之降序索引底层实现详解

    什么是降序索引 大家可能对索引比较熟悉,而对降序索引比较陌生,事实上降序索引是索引的子集. 我们通常使用下面的语句来创建一个索引: create index idx_t1_bcd on t1(b,c,d); 上面sql的意思是在t1表中,针对b,c,d三个字段创建一个联合索引. 但是大家不知道的是,上面这个sql实际上和下面的这个sql是等价的: create index idx_t1_bcd on t1(b asc,c asc,d asc); asc表示的是升序,使用这种语法创建出来的索引叫做

  • C语言二叉树的概念结构详解

    目录 1.树的概念及结构(了解) 1.1树的概念: 1.2树的表示法: 2.二叉树的概念及结构 2.1二叉树的概念 2.2特殊的二叉树 2.2二叉树的性质 2.3二叉树的顺序存储 2.4二叉树的链式存储 3.二叉树链式结构的实现 3.1二叉树的前中后序遍历 3.2求二叉树的节点个数 3.3求二叉树的叶子节点个数 3.4销毁二叉树 1.树的概念及结构(了解) 1.1树的概念: 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树

  • 基于canvas粒子系统的构建详解

    前面的话 本文将从最基本的imageData对象的理论知识说开去,详细介绍canvas粒子系统的构建 imageData 关于图像数据imageData共有3个方法,包括getImageData().putImageData().createImageData() [getImageData()] 2D上下文可以通过getImageData()取得原始图像数据.这个方法接收4个参数:画面区域的x和y坐标以及该区域的像素宽度和高度 例如,要取得左上角坐标为(10,5).大小为50*50像素的区域的

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • 二叉树的非递归后序遍历算法实例详解

    前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中.方法有很多,这里只举一种,先定义栈结点的数据结构 复制代码 代码如下: typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,往左下方走,一直走到头,将路径上

  • JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

    本文实例讲述了JavaScript数据结构与算法之二叉树遍历算法.分享给大家供大家参考,具体如下: javascript数据结构与算法--二叉树遍历(先序) 先序遍历先访问根节点, 然后以同样方式访问左子树和右子树 代码如下: /* *二叉树中,相对较小的值保存在左节点上,较大的值保存在右节点中 * * * */ /*用来生成一个节点*/ function Node(data, left, right) { this.data = data;//节点存储的数据 this.left = left;

  • java二叉树面试题详解

    目录 二叉树的深度 二叉搜索树的第k大节点 从上到下打印二叉树 二叉树的镜像 对称的二叉树 树的子结构 重建二叉树 二叉树的下一个节点 二叉搜索树的后序遍历路径 二叉树中和为某一值的路径 二叉搜索树与双向链表 总结 二叉树的深度 题目:输入一颗二叉树的根节点,求该树的的深度.输入一颗二叉树的根节点,求该树的深度.从根节点到叶节点依次经过的节点(含根.叶节点)形成的一条路径,最长路径的长度为树的深度. 如果一棵树只有一个节点,那么它的深度是1.如果根节点只有左子树,那深度是其左子树的深度+1,同样

  • PHP实现的线索二叉树及二叉树遍历方法详解

    本文实例讲述了PHP实现的线索二叉树及二叉树遍历方法.分享给大家供大家参考,具体如下: <?php require 'biTree.php'; $str = 'ko#be8#tr####acy#####'; $tree = new BiTree($str); $tree->createThreadTree(); echo $tree->threadList() . "\n";从第一个结点开始遍历线索二叉树 echo $tree->threadListReserv

  • PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】

    本文实例讲述了PHP实现绘制二叉树图形显示功能.分享给大家供大家参考,具体如下: 前言: 最近老师布置了一个作业:理解并实现平衡二叉树和红黑树,本来老师是说用C#写的,但是我学的C#基本都还给老师了,怎么办?那就用现在最熟悉的语言PHP来写吧! 有一个问题来了,书上在讲解树的时候基本上会给出形象的树形图.但是当我们自己试着实现某种树,在调试.输出的时候确只能以字符的形式顺序地输出.这给调试等方面带来了很大的不便.然后在各种百度之后,我发现利用PHP实现二叉树的图形显示的资源几乎是零!好吧,那我就

随机推荐