`

二叉树相关

 
阅读更多

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

 

《编程之美》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语言的实现

    二叉树相关操作代码

    二叉树代码 相关操作删除 插入 查找 数据结构中的二叉排序树

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

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

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

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

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

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

    考研常考的二叉树相关算法总结(详细全面,PDF版)

    主要针对考研常考的二叉树相关算法,包括但不限于对普通二叉树的构造、查找、插入元素、(先序、中序、后序、层序)遍历,并含递归和非递归方式等的算法、求二叉树的深度、删除二叉树中以某个结点为根结点的子树、...

    数据结构二叉树相关代码

    数据结构二叉树word,主要包一些二叉树的相关操作的源代码

    二叉树相关操作java实现

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

    二叉树相关操作

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

    二叉树及18个相关算法

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

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

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

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

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

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

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

    二叉树相关算法.rar

    二叉树面试相关算法:重要:8道 二叉比较简单,记住不要用递归,也不会有面试官让你用递归写,记住里面的非递归的写法

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

    二叉树

    MFC实现(数据结构)二叉树的应用

    本次设计,主要设计出二叉链表结构的相关函数库。其中包括二叉树的各种基本函数以及常用函数(实现二叉树的建立以及建立二叉树后的中序、前序、后序的递归和非递归函数,层次遍历的非递归函数)。 通过MFC实现可视化...

    二叉树学习啊

    二叉树 相关

    数据结构C++版-二叉树实验-使用类模板的方式实现

    一、实验目的:1、实现二叉树的存储结构(二叉链表或三叉链表等存储结构任选)2、熟悉二叉树基本术语的含义3、掌握使用栈和队列及递归思想完成二叉树相关操作的编程实现二、实验内容: 主要完成以下功能:1....

Global site tag (gtag.js) - Google Analytics