【数据结构】二叉树----前序、中序、后序遍历非递归和递归的实现

文章目录

- 1、概念
- 2、特殊的二叉树
- - - 2.1 完全二叉树
    - 2.2 满二叉树
- 3、二叉树的性质
- 4、二叉树的存储方式
- - - 4.1 顺序存储
    - 4.2 链式存储
- 5、二叉树实现
- - - 5.1 顺序存储实现
    - 5.2 链式存储实现
    - - 5.2.1 二叉树的创建
        
        5.2.2 前序遍历
        
        5.2.3 中序遍历
        
        5.2.4 后序遍历
        
        5.2.5 层序遍历

1、概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

二叉树的特点：

每个结点最多有两棵子树。
二叉树的子树有左右之分。

2、特殊的二叉树

2.1 完全二叉树

有n个结点，当且仅当每一个结点都和深度为k的满二叉树中编号从1到n的节点一一对应，即就是完全二叉树。

【数据结构】二叉树----前序、中序、后序遍历非递归和递归的实现

2.2 满二叉树

二叉树每层的节点数达到最大值，即就是满二叉树。

【数据结构】二叉树----前序、中序、后序遍历非递归和递归的实现

3、二叉树的性质

若根节点的层数为0，则一颗非空二叉树的第i层上最多有 2 ^ i 个结点
若根节点的二叉树深度为0，则深度为 h 的二叉树对的结点数是 2 ^ (h + 1) - 1
n0 = n2 + 1
具有 n 个结点的完全二叉树深度 h = log(n+1)
具有n个结点的完全二叉树，从上到下，从左到右给二叉树编号。i = 0 为根节点编号，i 是双亲结点编号，2 * i + 1是左孩子编号，2 * i + 2 是右孩子编号。

4、二叉树的存储方式

4.1 顺序存储

顺序结构存储就是使用数组来存储。而现实中使用中只有堆才会使用数组来存储。

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

【数据结构】二叉树----前序、中序、后序遍历非递归和递归的实现

4.2 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

通常的法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

5、二叉树实现

5.1 顺序存储实现

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。堆总是一棵完全二叉树。

#pragma once 
#include <malloc.h>
#include <string.h>
#include <iostream>
#include <assert.h>

typedef int hpint;

// 比较：按照大于还是小于
typedef int(*PCOM)(int left, int right);

struct heap 
{
  hpint* arr;
  int capacity;
  int size;
  PCOM compare;
};

int Less(int left, int right)
{
  return left < right;
}
int Great(int left, int right)
{
  return left > right;
}
void Swap(int *left, int * right)
{
  int temp = *left;
  *left = *right;
  *right = temp;
}
// 向上调整
void AdjustUp(heap* hp, int child)
{
  int parent = (child - 1) >> 1;
  while (child)
  {
    if (hp->compare(hp->arr[child], hp->arr[parent]))
    {
      Swap(&hp->arr[child], &hp->arr[parent]);

      child = parent;
      parent = (child - 1) >> 1;
    }
    else
    {
      return;
    }
  }
}

// 检查是否需要扩容
void check(heap* hp)
{
  assert(hp);
  if(hp->size >= hp->capacity)
  {
    hpint* temp = (hpint*)malloc(sizeof(hpint)*hp->size*2);
    int size = hp->size * 2;
    if(temp != nullptr)
    {
      return;
    }
    memcpy(temp, hp->arr, hp->size);
    free(hp->arr);
    hp->arr = temp;
    hp->capacity = size;
  }
}
// 向下调整
void AdjustDown(heap* hp, int parent)
{
  assert(hp);
  int child = parent*2 + 1;
  while(child < hp->size)
  {
    if(child + 1 < hp->size && hp->compare(hp->arr[child + 1], hp->arr[child]))
      child += 1;

    if(hp->compare(hp->arr[child], hp->arr[parent]))
    {
      Swap(&hp->arr[child], &hp->arr[parent]);
      parent = child;
      child = parent* 2 + 1;
    }
    else 
      return;
  }
}

//创建堆
void Creatheap(heap* hp, hpint arr[], int size, PCOM Compare)
{
  assert(hp);
  hp->arr = (hpint*)malloc(sizeof(hpint)*size);
  if(hp->arr == nullptr)
  {
    return;
  }
  memcpy(hp->arr, arr, sizeof(hpint)*size);
  hp->capacity = size;
  hp->size = size;
  hp->compare = Compare;

  // 对堆进行调整,从最后一个叶子节点开始调整
  for(int i = (size - 2) >> 1; i >= 0; --i)
  {
    AdjustUp(hp,i);
  }
}

//堆的插入
void heapPush(heap* hp, hpint data)
{
  assert(hp);
  check(hp);
  hp->arr[hp->size++] = data;
  AdjustUp(hp, hp->size - 1);
}

//堆的删除
void heapPop(heap* hp)
{
  assert(hp);
  if(hp->size == 0)
    return;
  Swap(&hp->arr[0], &hp->arr[hp->size - 1]);
  hp->size--;
  AdjustDown(hp, 0);
}

//获取堆顶元素
hpint heapTop(heap* hp)
{
  assert(hp);
  return hp->arr[0];
}

//有效元素个数
int heapSize(heap* hp)
{
  assert(hp);
  return hp->size;
}

//判断堆是否为空
int heapEmpty(heap* hp)
{
  return hp->size == 0;
}

//堆的销毁
void heapDestroy(heap* hp)
{
  assert(hp);
  if(hp->arr)
  {
    free(hp->arr);
    hp->arr = NULL;
    hp->capacity = hp->size = 0;
  }
}

5.2 链式存储实现

5.2.1 二叉树的创建

typedef char btint;

struct BTreeNode
{
  struct BTreeNode* left;
  struct BTreeNode* right;
  btint val;
};

BTreeNode* create_btree1()    
{
  btint ch;
  std::cin >> ch;
  BTreeNode* newNode;
  if(ch == '#')
  {
    return NULL;
  }
  else 
  {
    newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
    if(NULL == newNode)
    {
      perror("malloc");
      exit(-1);
    }
    newNode->val = ch;
    newNode->left = create_btree1();
    newNode->right = create_btree1();
  }
  return newNode;
}

void create_btree(BTreeNode **t)  
{
  btint ch;
  std::cin >> ch;
  if(ch == '#')
  {
    return;
  }
  else 
  {
    (*t) = (BTreeNode*)malloc(sizeof(BTreeNode));
    if(NULL == *t)
    {
      perror("malloc");
      exit(-1);
    }
    (*t)->val = ch;
    create_btree(&(*t)->left);
    create_btree(&(*t)->right);
  }
}

5.2.2 前序遍历

递归

void pre_order(BTreeNode* t)    
{
  if(t)
  {
    printf("%d ", t->val);
    pre_order(t->left);
    pre_order(t->right);
  }
}

非递归

void unpre_order(BTreeNode* t)  
{
  if(!t)
    return;

  std::stack<BTreeNode*> stk;
  stk.push(t);
  BTreeNode* temp;
  while(!stk.empty())
  {
    temp = stk.top();
    stk.pop();
    printf("%d ", temp->val);

    if(temp->right)
    {
      stk.push(temp->right);
    }
    if(temp->left)
    {
      stk.push(temp->left);
    }
  }
}

5.2.3 中序遍历

递归

void mid_order(BTreeNode* t)    
{
  if(t)
  {
    mid_order(t->left);
    printf("%d ", t->val);
    mid_order(t->right);
  }
}

非递归

void unmid_order(BTreeNode* t)    
{
  if(!t)
    return;
  std::stack<BTreeNode*> stk;
  BTreeNode* p = t;
  while(!stk.empty() || p != nullptr)
  {
    while(p != nullptr)
    {
      stk.push(p);
      p = p->left;
    }
    if(!stk.empty()) 
    {
      p = stk.top();
      printf("%d ", p->val);
      stk.pop();
      p = p->right;
    }
  }
}

5.2.4 后序遍历

递归

void post_order(BTreeNode* t)   
{
  if(t)
  {
    post_order(t->left);
    post_order(t->right);
    printf("%d ", t->val);
  }
}

非递归

void unpost_order(BTreeNode* t)   
{
  std::stack<BTreeNode*> stk1; 
  std::stack<BTreeNode*> stk2;
  stk1.push(t);
  BTreeNode* temp;
  while(!stk1.empty())
  {
    temp = stk1.top();
    stk1.pop();
    stk2.push(temp);
    if(temp->left)
    {
      stk1.push(temp->left);
    }
    if(temp->right)
    {
      stk1.push(temp->right);
    } 
  }

  while(!stk2.empty())
  {
    temp = stk2.top();
    stk2.pop();
    printf("%d ", temp->val);
  }
}

5.2.5 层序遍历

void level_order(BTreeNode* t)  
{
  if(!t)
    return;
  std::queue<BTreeNode*> q;
  q.push(t);
  while(!q.empty())
  {
    BTreeNode* temp = q.front();
    q.pop();
    // std::cout << temp->val << " ";
    printf("%d ", temp->val);

    if(temp->left)
    {
      q.push(temp->left);
    }
    if(temp->right)
    {
      q.push(temp->right);
    }
  }
}

【数据结构】二叉树----前序、中序、后序遍历非递归和递归的实现

文章目录

1、概念

2、特殊的二叉树

2.1 完全二叉树

2.2 满二叉树

3、二叉树的性质

4、二叉树的存储方式

4.1 顺序存储

4.2 链式存储

5、二叉树实现

5.1 顺序存储实现

5.2 链式存储实现

继续阅读

树的基本概念(定义、基本术语、性质)

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器