如何在二叉树中找出和为某一值的所有路径

代码如下所示,不足之处,还望指正!


代码如下:

// BinaryTree.cpp : 定义控制台应用程序的入口点。
//C++实现链式二叉树,在二叉树中找出和为某一值的所有路径
#include "stdafx.h"
#include<iostream>
#include<string>
#include <stack>
using namespace std;
static int sum(0);
static int count(0);
template<class T>
struct BiNode
{
 T data;
 struct BiNode<T> *rchild,*lchild;
};
template<class T>
class BiTree
{
public:
 BiTree(){
  cout<<"请输入根节点:"<<endl;
  Create(root);
  if (NULL != root)
  {
   cout<<"root="<<root->data<<endl;
  }
  else
  {
   cout << "The BinaryTree is empty." << endl;
  }
 }
 ~BiTree(){Release(root);}
 int Depth(){return Depth(root);}
 int FindPath(T i)
 {
  stack<BiNode<T>*> sta;
  return FindPath(i, root, sta);
 };
private:
 BiNode<T> *root;
 void Create(BiNode<T>* &bt);
 void Release(BiNode<T> *bt);
 int Depth(BiNode<T>* bt);
 int FindPath(T i, BiNode<T>* bt, stack<BiNode<T>*> &sta);
};
//析构函数
template <class T>
void BiTree<T>::Release(BiNode<T> *bt)
{

if(bt==NULL)
 {
  Release(bt->lchild );
  Release(bt->rchild );
  delete bt;
 }
}
//建立二叉树
template <class T>
void BiTree<T>::Create(BiNode<T>* &bt)
{
 T ch;
    cin>>ch;
    if(ch== 0)bt=NULL;
    else
    {
     bt=new BiNode<T>;
     bt->data =ch;
     cout<<"调用左孩子"<<endl;
     Create(bt->lchild );
     cout<<"调用右孩子"<<endl;
     Create(bt->rchild );
    }
}
//求树的深度
template <class T>
int BiTree<T>::Depth(BiNode<T>* bt)
{
 if (NULL == bt)
 {
  return 0;
 }
 int d1 = Depth(bt->lchild);
 int d2 = Depth(bt->rchild);
 return (d1 > d2 ? d1 : d2)+ 1;
}
template <class T>
int BiTree<T>::FindPath(T i, BiNode<T>* bt, stack<BiNode<T>*> &sta)
{
 if (NULL != bt)
 {
  sta.push(bt);
 }
 sum += bt->data;
 if (sum == i && bt->lchild == NULL && bt->rchild == NULL)
 {
  stack<BiNode<T>*> sta2(sta);
  BiNode<T>* p;
  cout << "One of the path is: " ;
  while (!sta2.empty())
  {
   p = sta2.top();
   cout << p->data << " ";
   sta2.pop();
  }
  cout << endl;
  count ++;
 }
 if (NULL != bt->lchild)
 {
  FindPath(i, bt->lchild, sta);
 }
 if (NULL != bt->rchild)
 {
  FindPath(i,bt->rchild, sta);
 }
 sum -= bt->data;
 sta.pop(); 
 return count;
}
void main()
{
    BiTree<int> a;
   cout << "There are " << a.FindPath(9) << " path all." << endl;
}

输入一棵二叉树,从树的根节点开始往下访问,一直到叶节点所经过的所有节点形成一条路径。输出和与某个数相等的所有路径。
例如: 二叉树
         3
      2     6
   5    4
则和为9的,路径有两条,一条为3,6  另一条为3, 2, 4。

时间: 2013-05-28

深入理解二叉树的非递归遍历

二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的.对于二叉树,有前序.中序以及后序三种遍历方法.因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁.而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现.在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点.一.前序遍历前序遍历按照"根结点-左孩子-右孩子"的顺序进行访问.1.递归实现 复制代码 代码如下: void preO

python二叉树遍历的实现方法

复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class TreeNode(object):    def __init__(self,data=0,left=0,right=0):        self.data = data        self.left = left        self.right = right class BTree(object):    def __init__(self,root=0):     

先序遍历二叉树的递归实现与非递归实现深入解析

1.先序遍历二叉树  递归实现思想:若二叉树为空,返回.否则 1)遍历根节点:2)先序遍历左子树:3)先序遍历右子树: 代码: 复制代码 代码如下: template<typename elemType> void PreOrder(nodeType<elemType> *root)  {      if(root==NULL)          return ;      visit(root->data); // visit the data    PreOrder(ro

平衡二叉树的实现实例

复制代码 代码如下: /*首先平衡二叉树是一个二叉排序树:其基本思想是:在构建二叉排序树的过程中,当每插入一个节点时,先检查是否因为插入而破坏了树的平衡性,若是,找出最小不平衡树,进行适应的旋转,使之成为新的平衡二叉树.*/#include<cstdio>#include<cstdlib>#define LH 1#define EH 0#define RH -1 using namespace std; typedef struct BTNode{ int data; int BF

深入遍历二叉树的各种操作详解(非递归遍历)

先使用先序的方法建立一棵二叉树,然后分别使用递归与非递归的方法实现前序.中序.后序遍历二叉树,并使用了两种方法来进行层次遍历二叉树,一种方法就是使用STL中的queue,另外一种方法就是定义了一个数组队列,分别使用了front和rear两个数组的下标来表示入队与出队,还有两个操作就是求二叉树的深度.结点数... 复制代码 代码如下: #include<iostream>#include<queue>#include<stack>using namespace std;/

PHP Class&amp;Object -- 解析PHP实现二叉树

二叉树及其变体是数据结构家族里的重要组成部分.最为链表的一种变体,二叉树最适合处理需要一特定次序快速组织和检索的数据. 复制代码 代码如下: <?php// Define a class to implement a binary treeclass Binary_Tree_Node {    // Define the variable to hold our data:    public $data;    // And a variable to hold the left and ri

二叉树先序遍历的非递归算法具体实现

在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构 总结先根遍历得到的非递归算法思想如下: 1)入栈,主要是先头结点入栈,然后visit此结点 2)while,循环遍历当前结点,直至左孩子没有结点 3)if结点的右孩子为真,转入1)继续遍历,否则退出当前结点转入父母结点遍历转入1) 先看符合此思想的算法: 复制代码 代码如下: int PreOrderTraverseNonRecursiveEx(const BiTree &T, int

深入二叉树两个结点的最低共同父结点的详解

题目:二叉树的结点定义如下: 复制代码 代码如下: struct TreeNode   {              int m_nvalue;             TreeNode* m_pLeft;             TreeNode* m_pRight;}; 输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点.分析:求数中两个结点的最低共同结点是面试中经常出现的一个问题.这个问题至少有两个变种.第一变种是二叉树是一种特殊的二叉树:查找二叉树.也就是树是排序过的,位于左子

PHP Class&amp;Object -- PHP 自排序二叉树的深入解析

在节点之间再应用一些排序逻辑,二叉树就能提供出色的组织方式.对于每个节点,都让满足所有特定条件的元素都位于左节点及其子节点.在插入新元素时,我们需要从树的第一个节 点(根节点)开始,判断它属于哪一侧的节点,然后沿着这一侧找到恰当的位置,类似地,在读取数据时,只需要使用按序遍历方法来遍历二叉树. 复制代码 代码如下: <?phpob_start();// Here we need to include the binary tree classClass Binary_Tree_Node() { 

二叉树先根(先序)遍历的改进

二叉树的特点:每个结点的度最大不能超过2,并且左右子树不能颠倒 二叉树的存储结构:下面采用链式存储进行阐述,堆排序算法(快速排序改进)采用的顺序存储结构的二叉树,先看如下结构体的存储方式 顺序存储: 复制代码 代码如下: /*二叉树的顺序存储*/#define  MAX_TREE_SIZE 100typedef  TElemType  SqBiTree[MAX_TREE_SIZE]; 链式存储: 复制代码 代码如下: /*二叉树的链式存储*/typedef struct BiTNode{ TEl

二叉树遍历 非递归 C++实现代码

二叉树的非递归遍历 二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的.对于二叉树,有前序.中序以及后序三种遍历方法.因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁.而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现.在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点. 一.前序遍历 前序遍历按照"根结点-左孩子-右孩子"的顺序进行访问. 1.递归实现 复制代码 代码

C++二叉树结构的建立与基本操作

准备数据定义二叉树结构操作中需要用到的变量及数据等. 复制代码 代码如下: #define MAXLEN 20    //最大长度typedef char DATA;    //定义元素类型struct  CBTType                   //定义二叉树结点类型 { DATA data;           //元素数据  CBTType * left;    //左子树结点指针  CBTType * right;   //右子树结点指针 }; 定义二叉树结构数据元素的类型DA

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

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

c语言版本二叉树基本操作示例(先序 递归 非递归)

复制代码 代码如下: 请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):ABD==E==CF==G== 先序递归遍历:A B D E C F G中序递归遍历:D B E A F C G后序递归遍历:D E B F G C A层序递归遍历:ABCDEFG先序非递归遍历:A B D E C F G中序非递归遍历:D B E A F C G后序非递归遍历:D E B F G C A深度:请按任意键继续. . . 复制代码 代码如下: #include<stdio.h>#include&

探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

如有不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data; 

python二叉树的实现实例

树的定义树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样.树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示.树在计算机领域中也得到广泛应用,如在编译源程序时,可用树表示源程序的语法结构.又如在数据库系统中,树型结构也是信息的重要组织形式之一.一切具有层次关系的问题都可用树来描述.树结构的特点是:它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前驱.树的递归定义如下:(1

二叉树前序遍历的非递归算法

二叉树的前序遍历是先根节点,然后如果有左子树则再先序遍历左子树,然后如果有右子树则再先序遍历其又子树.递归算法如下 复制代码 代码如下: void   preorder(Betree *t){   if(t==null) return;visit(t);//访问该节点preorder(t->lchild);preorder(t->rchild); } 当然递归算法是隐式使用了栈.我们仔细分析这个过程,先是取出了根节点进行了访问,然后我们把根节点退栈,退栈后必然有节点进栈,怎么办呢?根节点只能直

平衡二叉树AVL操作模板

复制代码 代码如下: /*** 目的:实现AVL* 利用数组对左右儿子简化代码,但是对脑力难度反而增大不少,只适合acm模板* 其实avl在acm中基本不用,基本被treap取代* avl一般只要求理解思路,不要求写出代码,因为真心很烦*/ #include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <

ThinkPHP模板之变量输出、自定义函数与判断语句用法

本文实例讲述了ThinkPHP模板之变量输出.自定义函数与判断语句用法.主要包括变量输出.自定义函数与判断语句三种用法.分享给大家供大家参考.具体分析如下: 模板操作变量输出: 快捷输出变量 复制代码 代码如下: {:function(-)} //执行方法并输出返回值 {~function} //执行方法不输出 {@var} //输出Session变量 {#var} //输出Cookie变量 {&var} //输出配置参数  {%var} //输出语言变量 {.var} //输出GET变量 {^

ThinkPHP模板输出display用法分析

本文实例分析了ThinkPHP模板输出display用法.分享给大家供大家参考.具体分析如下: 模板变量赋值后就需要调用模板文件来输出相关的变量,模板调用通过display方法来实现,我们在操作方法的最后使用: 复制代码 代码如下: $this->display(); 就可以输出模板,根据前面的模板定义规则,因为系统会按照默认规则自动定位模板文件,所以通常display方法无需带任何参数即可输出对应的模板,这是模板输出的最简单的用法. 事情总有特例,或者根本不需要按模块进行分目录存放,不过dis

JavaScript的Polymer框架中dom-repeat与VM的相关操作

各种框架都有把一个列表数据绑定到 DOM 上的功能,比如 Angular 会用 ng-repeat 来绑定.那么 Polymer 呢?其实这个级别的功能属于框架的扩展功能了,Angular 的 ng-repeat 也只是个 Directive 而已.Polymer 的 dom-repeat 也是这个级别的东西. 在 Polymer 中,一切都是 Directive 的概念.dom-module 用于定义模块,它本身也是一个 Directive.dom-repeat 也是,但它不是一个标签,而是一

SpringBoot操作Redis三种方案全解析

使用 Java 操作 Redis 的方案很多,Jedis 是目前较为流行的一种方案,除了 Jedis ,还有很多其他解决方案,如下: 除了这些方案之外,还有一个使用也相当多的方案,就是 Spring Data Redis. 在传统的 SSM 中,需要开发者自己来配置 Spring Data Redis ,这个配置比较繁琐,主要配置 3 个东西:连接池.连接器信息以及 key 和 value 的序列化方案. 在 Spring Boot 中,默认集成的 Redis 就是 Spring Data Re

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

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

为什么MySQL数据库索引选择使用B+树?

在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出B树以及为什么MySQL数据库索引选择使用B+树! 学过数据结构的一般对最基础的树都有所认识,因此我们就从与我们主题更为相近的二叉查找树开始. 一.二叉查找树 (1)二叉树简介: 二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质: 1.任意节点左子树不为空,则左子树的值均小于根节点的值: 2.任意节点右子

thinkphp3.x中display方法及show方法的用法实例

本文实例讲述了thinkphp3.x中display方法及show方法的用法.分享给大家供大家参考,具体如下: 通过前面的文章在了解了控制器和模型操作后,我们开始熟悉视图部分,ThinkPHP中的视图主要就是指模板文件和模板引擎,本篇首先了解下模板文件以及是如何进行渲染输出的. 一.模板定义 为了对模板文件更加有效的管理,ThinkPHP对模板文件进行目录划分,默认的模板文件定义规则是: 模板目录/[分组名/][模板主题/]模块名/操作名+模板后缀 模板目录默认是项目下面的Tpl, 当定义分组的

详解SpringBoot集成Redis来实现缓存技术方案

概述 在我们的日常项目开发过程中缓存是无处不在的,因为它可以极大的提高系统的访问速度,关于缓存的框架也种类繁多,今天主要介绍的是使用现在非常流行的NoSQL数据库(Redis)来实现我们的缓存需求. Redis简介 Redis 是一个开源(BSD许可)的,内存中的数据结构存储系统,它可以用作数据库.缓存和消息中间件,Redis 的优势包括它的速度.支持丰富的数据类型.操作原子性,以及它的通用性. 案例整合 本案例是在之前一篇SpringBoot + Mybatis + RESTful的基础上来集

java后台利用Apache poi 生成excel文档提供前台下载示例

之前在项目中会用到在Java在后台把数据填入Word文档的模板来提供前台下载,为了自己能随时查看当时的实现方案及方便他人学习我写了这篇博客,访问量已经是我写的博客里第一了.于是乎我在学会用Java在后台利用Apache poi 生成excel文档提供前台下载之后就想着来写一篇姊妹篇啦. 在生成Excel文档的时候我采用了和生成Word时的不同方法,Apache poi.它是用Java编写的免费开源的跨平台的 Java API,提供API给Java程式对Microsoft Office格式档案读和