头歌两种遍历方法建立一棵树(前序和中序)

简介: 头歌两种遍历方法建立一棵树(前序和中序)

///


#include <stdio.h>


#include <stdlib.h>


#include <string.h>


#include "ConstructTree.h"


/




/*


InPreToTree(): 由前序遍历序列和中序遍历序列构造二叉树


前序序列为pa[p1:p2]


中序序列为ia[i1:i2]


返回所构造的二叉树的根指针


*/


TNode* InPreToTree(char *pa, char *ia, int p1, int p2, int i1, int i2)


{


   /*请在BEGIN和END之间实现你的代码*/


   /*****BEGIN*****/


  if(p1>p2){


      return NULL;


  }


  TNode* root=new TNode;


  root->data=pa[p1];//将前序数组中第一个元素赋给data,前序数组第一个值都是根节点。


  root->left=NULL;


  root->right=NULL;


  int i=0;


  while(ia[i]!=pa[p1]){


      i++;


  }//查找根节点在中序数组中的位置。


//递归,每次缩小范围,将树一次一次细分。


  int llen=i-i1;//存储左子树长度


   root->left=InPreToTree(pa,ia,p1+1,p1+llen,i1,i-1);//每个根节点左右子树依次递推下去,双亲和子树的递推方法都是一样的。


   int rlen=i2-i;//存储右子树长度,两个分开存储会更好


   root->right=InPreToTree(pa,ia,p2-rlen+1,p2,i+1,i2);


   return root;


   /******END******/


   /*请不要修改[BEGIN,END]区域外的代码*/


}


void PrintPostTravel(TNode* t)


{


   if(t==NULL) return;


   if(t->left) PrintPostTravel(t->left);


   if(t->right) PrintPostTravel(t->right);


   printf("%c", t->data);


}


void DeleteTree(TNode* t)


{


   if(t==NULL) return;


   if(t->left) DeleteTree(t->left);


   if(t->right) DeleteTree(t->right);


   delete t;


}


目录
打赏
0
0
0
0
0
分享
相关文章
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
49 0
给出一个数据序列,建立二叉排序树,并实现插入功能 对二叉排序树进行中序遍历,可以得到有序的数据序列
该文章通过C++代码示例讲解了如何根据输入数据序列构建二叉排序树,并实现插入功能,随后通过中序遍历输出有序的数据序列,展示了对二叉排序树进行操作和遍历的完整过程。
【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目
【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目
代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树
代码随想录算法训练营第十八天 | 力扣 513. 找树左下角的值、112. 路径总和、113. 路径总和 II、106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树
66 0
【线索二叉树】C++代码及线索化过程详解
【线索二叉树】C++代码及线索化过程详解
262 0
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(下
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
102 0
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(上)
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
135 0
二叉树的递归遍历与迭代遍历(图示)
本文将讲述二叉树递归与迭代的相关知识。
145 0
前端知识案例-二叉树的遍历(前序 中序 后序)
前端知识案例-二叉树的遍历(前序 中序 后序)
87 0
前端知识案例-二叉树的遍历(前序 中序 后序)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等