`

二叉树相关

 
阅读更多

本节主要是为了写二叉树类型题目练手的代码,重点培养运用“指针”。

 

《编程之美》3.9重建二叉树 : 已知前序和中序,重建二叉树

#include <iostream>
using namespace std;

#define TREELEN 6
struct NODE{
	NODE* pLeft;
	NODE* pRight;
	char chValue;
};

void ReBuild(char* pPreOrder, char* pInOrder, int nTreeLen, NODE** pRoot){
	if(nTreeLen<1){
		return;
	}
	
	*pRoot=new NODE;
	(*pRoot)->pLeft=NULL;
	(*pRoot)->pRight=NULL;
	(*pRoot)->chValue=*pPreOrder;
	
	int lNum=0;	//左子树节点个数 
	int rNum=0;	//有子树节点个数 
	for(int i=0;i<nTreeLen;i++){
		if(*pPreOrder==*(pInOrder+i)){
			lNum=i;
			break;
		}
	}
	rNum=nTreeLen-1-lNum;
	
	if(lNum>=1){
		ReBuild(pPreOrder+1, pInOrder, lNum, &((*pRoot)->pLeft));
	}
	if(rNum>=1){
		ReBuild(pPreOrder+1+lNum, pInOrder+1+lNum, rNum, &((*pRoot)->pRight));
	}
}

void printTree(NODE* pRoot){
	if(pRoot==NULL)
		return;
	
	cout<<pRoot->chValue<<", ";
	if(pRoot->pLeft!=NULL){
		cout<<"l="<<pRoot->pLeft->chValue<<", ";
	}else{
		cout<<"l=NULL, ";
	}
	if(pRoot->pRight!=NULL){
		cout<<"r="<<pRoot->pRight->chValue<<endl;
	}else{
		cout<<"r=NULL"<<endl;
	}
		
	printTree(pRoot->pLeft);
	printTree(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);
	
	printTree(pRoot);
}

 

 

 

分享到:
评论

相关推荐

    与二叉树有关的算法 c

    本篇将详细探讨在C语言中实现与二叉树相关的算法,包括求解二叉树节点总数、叶子总数、高度以及宽度,以及交换二叉树节点的左右子树。 首先,二叉树的节点由其数据、左子节点和右子节点构成。在C语言中,可以使用...

    二叉树相关操作代码

    根据给定文件的信息,我们可以详细地探讨一下二叉树数据结构以及如何通过...以上就是对给定文件中所涉及的二叉树相关操作的详细解析。通过对这些操作的理解和实现,可以帮助我们更好地掌握二叉树这一重要的数据结构。

    二叉树相关算法.rar

    在面试中,二叉树相关的问题是常见的考察点,尤其是非递归的算法实现,因为它们能体现候选人的逻辑思维能力和空间复杂度控制。下面我们将详细探讨八种可能的二叉树算法,以及如何非递归地解决它们。 1. **遍历**:...

    二叉树相关算法的实验验证+判别给定二叉树是否为完全二叉树。

    1、 定义链接存储的二叉树类。 2、 实验验证如下算法的正确性、各种功能及指标: 1) 创建一棵二叉树,并对其初始化; 2)先根、中根、后根遍历二叉树; 3) 在二叉树中搜索给定结点的父结点; 4) 搜索二叉树中符合...

    二叉树相关算法源代码大全

    二叉树相关算法源代码大全,包括二叉树的递归创建、先序中序后序遍历、二叉树结点数求解、二叉树叶结点路径求解、二叉树深度等常见的二叉树算法。 附带一个根据二叉树的先序遍历序列和中序遍历序列输出后序遍历序列...

    数据结构——二叉树有关操作程序

    一)建立二叉树+判空+遍历 (1)以二叉链表作为存储结构,从键盘以先序次序输入各个结点(空格字符表示空树)建立一棵二叉树; (2)对(1)中生成的二叉树进行判空; (3)对(1)中生成的二叉树进行遍历(分别实现...

    数据结构-二叉树相关功能及算法

    以上是关于“数据结构-二叉树相关功能及算法”的主要知识点,理解并掌握这些内容对于提升编程能力和解决实际问题有着至关重要的作用。通过实践和学习,你可以更加熟练地运用二叉树解决各种数据处理和计算问题。

    数据结构:二叉树相关代码

    这个压缩包“数据结构:二叉树相关代码”很可能包含了各种二叉树操作的实现,如插入、删除、遍历等,以及可能的自定义二叉树类型,比如二叉搜索树、平衡二叉树(AVL树或红黑树)等。 首先,二叉树是一种非线性数据...

    与二叉树相关的程序集锦

    在本程序集中,我们深入探讨了与二叉树相关的多种概念和操作,包括计算二叉树的节点数、叶子数、深度,以及执行三种遍历方法——前序遍历、中序遍历和后序遍历,同时也包含了层次遍历的实现。下面将详细介绍这些知识...

    链表存储结构的表达式二叉树相关代码

    在这个“链表存储结构的表达式二叉树相关代码”主题中,我们将深入探讨二叉树的遍历方法及其与链表的关系。 首先,链表是一种线性数据结构,其中每个元素(节点)包含数据和指向下一个节点的引用。链表不需在内存中...

    数据结构二叉树相关代码

    总结来说,这段代码实现了一个基于链表的数据结构,包括二叉树节点的存储结构、栈和队列的链式存储结构,以及相关操作的函数。这些结构和函数提供了对二叉树和线性数据结构的基本操作,是数据结构和算法学习的基础。...

    二叉树相关操作java实现

    1:构造一个二叉树 2:二叉树前序遍历(递归) 3:二叉树中序遍历(递归) 4:二叉树后续遍历(递归) 5:二叉树前序遍历(非递归) 6:二叉树中序遍历(非递归) 7:二叉树后序遍历(非递归)

    二叉树相关操作

    二叉树基本操作:定义、建立、输入、输出等操作以及各种遍历,交换using namespace std; //二叉树定义 typedef char ElementType; typedef struct BiTreeNode { ElementType data; struct BiTreeNode* lchild; ...

    画二叉树小工具dtree源码

    这个名为dtree的小工具,旨在帮助程序员更直观地理解和调试二叉树相关的算法。 【描述】提到的"画二叉树小工具源码"来源于博主karizhang在CSDN上的博客文章。CSDN(China Software Developer Network)是中国最大的...

    二叉树模板代码 二叉树习题

    本主题将深入探讨二叉树的基本概念、常见操作以及模板代码实现,帮助你理解和解决二叉树相关的习题。 一、二叉树定义与基本概念 二叉树是由n(n&gt;=0)个有限节点组成的数据结构,每个节点最多有两个子节点,分别称为...

    二叉树

    二叉树是一种重要的数据结构,它在计算机科学中扮演着至...通过深入理解和熟练运用这些概念,可以有效地解决与二叉树相关的编程问题,提高程序的效率。无论是理论学习还是实际开发,二叉树都是计算机科学中的重要基石。

    二叉树及18个相关算法

    给出了较为完整的二叉树相关算法,包含构建二叉树,非递归的先序、中序、后序和层次遍历算法,求树的深度,以及寻找指定节点、设定指定节点值等18个算法,有一个简单的命令行交互界面。 建议windows用户用编程工具...

    二叉树相关算法的具体实现

    本文件包含前序和层序创建二叉树,前序、中序、后序遍历二叉树的递归和非递归版本,以及层序遍历。

    数据结构实验——二叉树相关操作

    本人本科期间数据结构二叉树的实验 1、建立二叉树的存储结构 2、先序、中序、后序遍历二叉树(要求任选某一种用非递归算法完成) 3、查询二叉树中某个结点 4、统计二叉树中叶子结点的个数 5、求二叉树的深度 6、要求...

    C语言二叉树相关的代码.zip

    本文将深入探讨C语言实现二叉树的相关知识点,包括二叉树的基本概念、常用操作以及如何在C语言中编码实现。 首先,我们要理解什么是二叉树。二叉树是每个节点最多有两个子节点的树形数据结构,通常分为左子节点和右...

Global site tag (gtag.js) - Google Analytics