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

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

///


#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
分享
相关文章
【深度优先搜索】【树】【状态压缩】2791. 树中可以形成回文的路径数
【深度优先搜索】【树】【状态压缩】2791. 树中可以形成回文的路径数
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
49 0
【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目
【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(上)
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
135 0
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力(下
【算法入门&二叉树】从先中后序的遍历到用中后序列构造二叉树|如何抵挡递归法该死的魅力
102 0
日拱算法: 删除链表的倒数第 N 个结点
平常基本上没有用过链表数据结构,链表的优势在于插入的时间复杂度良好 O(1)。 闲言少叙,冲就完事儿!
js 通过左右前序和中序, 或者后序和中序来还原二叉树
js 通过左右前序和中序, 或者后序和中序来还原二叉树
js 通过左右前序和中序, 或者后序和中序来还原二叉树
二叉查找树的建立,删除,非递归和递归查找给定元素,非递归和递归查找最大元素结点和最小元素结点
二叉查找树的建立,删除,非递归和递归查找给定元素,非递归和递归查找最大元素结点和最小元素结点
【CCCC】L2-006 树的遍历 (25分),根据后序与中序遍历建立二叉树
【CCCC】L2-006 树的遍历 (25分),根据后序与中序遍历建立二叉树
161 0