数据结构与算法3--树常见操作

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。以下是笔者根据树的特性和平时使用情况完成的一些基本功能，后续将根据使用情况再增加相关功能。

1、功能

00-打印数组

01-新建树方法1

02-广度输出树

03-先序遍历树

04-中序遍历树

05-后续遍历树

06-树高度计算方法

2、代码

/*该文件夹包含tree的增删查改，以及常见tree算法的实现*/#include 
   
    #include 
    
     #include 
     
      using namespace std;/*	example 1     10  6     144   8  12 16pre = {10,6,4,8,14,12,16}mid = {4,8,6,12,16,14,10}example 2	 1  2     34      5   6  7        8pre = {1,2,4,7,3,5,6,8}mid = {4,7,2,1,5,3,8,6} */typedef struct Node{	int val;	Node *left;	Node *right;}TreeNode;/*Menu00-打印数组01-新建树方法102-广度输出树03-先序遍历树04-中序遍历树05-后续遍历树06-树高度计算方法*/void PrintArray(const vector
      
        &arr);//00TreeNode* CreateTree1(vector
       
         pre, vector
        
          mid);//01-1由前序遍历和中序遍历构建二叉树void PrintTreeBFS(TreeNode *pRoot);//02void PrintPreOrder(TreeNode *pRoot);//03void PrintInOrder(TreeNode *pRoot);//04void PrintLastOrder(TreeNode *pRoot);//05int GetHight(TreeNode *pRoot);//06-树高度计算方法//00-打印数组void PrintArray(const vector
         
           &arr){ cout<<'['; for(int i=0;i

pre, vector

mid){ if(pre.size()==0 || mid.size()==0) return NULL; vector

lpre,lmid,rpre,rmid;//save leftsubtre pre、leftsubtree mid、rightsubstree pre、rightsubtree mid int i=0; for(i=0;i

val = pre[0]; root->left = CreateTree1(lpre,lmid); root->right = CreateTree1(rpre,rmid); return root;}void TestCreateTree1(){ int pre[] = {1,2,4,7,3,5,6,8}; int mid[] = {4,7,2,1,5,3,8,6}; vector