数据结构和算法-二叉树

一、概念

二叉树:每个结点最多有两个子树的树结构
如图:

截屏2020-05-07下午2.30.01.png

满二叉树:除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树

截屏2020-05-07下午3.43.10.png

完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树
截屏2020-05-07下午3.45.09.png

二、相关术语

  • 树的结点:包含一个数据元素及若干指向子树的分支
  • 孩子结点:结点的子树的根称为该结点的孩子
  • 双亲结点:B 结点是A 结点的孩子,则A结点是B 结点的双亲
  • 兄弟结点:同一双亲的孩子结点
  • 堂兄结点:同一层上结点
  • 叶子结点:也叫终端结点,是度为 0 的结点
  • 结点层:根结点的层定义为1;根的孩子为第二层结点,依此类推
  • 树的深度:树中最大的结点层
  • 结点的度:结点子树的个数
  • 树的度: 树中最大的结点度

三、二叉树性质

  1. 性质1: 在二叉树的第n层上最多有2⁽ⁿ ⁻ ¹⁾个结点(n>=1)
  2. 性质2: 深度为n的二叉树最多有2ⁿ - 1 个结点(n>=1)
  3. 性质3: 对于任何一颗二叉树T,如果其终端结点数为n₀,度为2的结点数为n₂,则n₀ = n₂ + 1;
  4. 性质4: 具有n个结点的完全二叉树深度为(log₂n)+1
  5. 性质5:对具有n个结点的完全二叉树,如果按照从上至下和从左至右的顺序对二叉树的所有结点从1开始编号,则对于任意的序号为i的结点有:
    A. 如果i>1,那么序号为i的结点的双亲结点序号为i/2;
    B. 如果i=1,那么序号为i的结点为根节点,无双亲结点;
    C. 如果2i<=n,那么序号为i的结点的左孩子结点序号为2i;
    D. 如果2i>n,那么序号为i的结点无左孩子;
    E. 如果2
    i+1<=n,那么序号为i的结点右孩子序号为2i+1;
    F. 如果2
    i+1>n,那么序号为i的结点无右孩子。

四、二叉树的代码实现

1、顺序存储

typedef CElemType OrderBiTree[MAX_TREE_SIZE];
CElemType Nil = 0;

typedef struct {
  int level; //结点层
  int order; //本层的序号(按照满二叉树给定序号规则)
} NodePosition;

//构造空二叉树
Status initBiTree(OrderBiTree T){
  for (int i = 0; i<MAX_TREE_SIZE; i++) {
      T[i] = Nil;
  }
  return OK;
}
//由于清空二叉树与初始化二叉树是一致的
#define clearBiTree initBiTree

按层序次序依次给二叉树结点赋值

Status creatBiTree(OrderBiTree T){
  int maxNode = 10;
  for (int i = 0; i<MAX_TREE_SIZE; i++) {
      if (i<maxNode) {
          T[i] = i+1;
          if (i!=0 && T[i]!=Nil && T[(i+1)/2-1] == Nil) {
              return ERROR;
          }
      }else{
          T[i] = Nil;
      }
  }
  
  return OK;
}

判断二叉树是否为空

Status biTreeIsEmpty(OrderBiTree T){
  if (T[0] == Nil) {
      return TRUE;
  }else{
      return FALSE;
  }
}

获取二叉树的深度

int getDepthFromBiTree(OrderBiTree T){
  int i;
  //获取二叉树T的最后一个结点的序列号
  for (i = MAX_TREE_SIZE-1; i>=0; i--) {
      if (T[i] != Nil) {
          break;
      }
  }
  //根据二叉树性质:深度为n的二叉树最多有2ⁿ - 1个结点
  int j = -1;
  do {
      j++;
  } while (pow(2, j)<=i);
  
  return j;
}

根据结点位置获取结点的值

CElemType getValueWithPosition(OrderBiTree T, NodePosition p){
  //p.level层第一个结点的序列号,根结点序列号从1开始
  int index = pow(2, p.level-1);
  
  //p.level层p.order位置结点的序列号
  index = index+p.order-1;
  return T[index-1];
}

给处于位置e的结点赋值

Status setValueToPosition(OrderBiTree T, NodePosition e, CElemType value){
  int i = pow(2, e.level-1) + e.order-2;
  if (value== Nil || T[(i+1)/2-1] == Nil) {
      return ERROR;
  }
  T[i] = value;
  return OK;
}

获取某结点的双亲结点

CElemType parentNode(OrderBiTree T, CElemType e){
  if (T[0] == Nil) {
      return Nil;
  }
  for (int i=0; i<MAX_TREE_SIZE; i++) {
      if (i != 0 &&T[i] == e) {
          return T[(i+1)/2-1];
      }
  }
  
  return Nil;
}

获取某结点的左子结点

CElemType leftChildNode(OrderBiTree T,CElemType e){
  if (T[0] == Nil) {
      return Nil;
  }
  for (int i=0; i<MAX_TREE_SIZE-1; i++) {
      if (T[i] == e) {
          return T[i*2+1];
      }
  }
  
  return Nil;
}

获取某结点的右子结点

CElemType rightChildNode(OrderBiTree T,CElemType e){
  if (T[0] == Nil) {
      return Nil;
  }
  for (int i=0; i<MAX_TREE_SIZE; i++) {
      if (T[i] == e) {
          return T[i*2+2];
      }
  }
  
  return Nil;
}

获取某结点的左兄弟

CElemType leftSibling(OrderBiTree T,CElemType e){
 if (T[0] == Nil) {
     return Nil;
 }
 for (int i=0; i<MAX_TREE_SIZE-1; i++) {
     //找到e数据的结点,且该结点是右结点
     if (T[i] == e&&i%2==0) {
         return T[i-1];
     }
 }
 
 return Nil;
}

获取某结点的右兄弟

CElemType rightSibling(OrderBiTree T,CElemType e){
  if (T[0] == Nil) {
      return Nil;
  }
  for (int i=0; i<MAX_TREE_SIZE-1; i++) {
      //找到e数据的结点,且该结点是左结点
      if (T[i] == e&&i%2==1) {
          return T[i+1];
      }
  }
  
  return Nil;
}

二叉树的遍历

Status visit(CElemType c){
  printf("%d ",c);
  return OK;
}

//层序遍历
void levelOrderTraverse(OrderBiTree T){
  int i = MAX_TREE_SIZE-1;
  //找到最后一个非空结点
  while (T[i] == Nil) {
      i--;
  }
  for (int j = 0; j<=i; j++) {
      if (T[j] != Nil) {
          visit(T[j]);
      }
  }
  printf("\n");
}

//前序遍历
void preTraverse(OrderBiTree T,int i){
  //打印结点
  visit(T[i]);
  //遍历左子树
  if (T[2*i+1]!=Nil) {
      preTraverse(T, 2*i+1);
  }
  //遍历右子树
  if (T[2*i+2]!=Nil) {
      preTraverse(T, 2*i+2);
  }
}

Status preOrderTraverse(OrderBiTree T){
  if (!biTreeIsEmpty(T)) {
      preTraverse(T, 0);
  }
  printf("\n");
  return OK;
}

//中序遍历
void inTraverse(OrderBiTree T, int i){
  if (T[2*i+1] != Nil){
      inTraverse(T, 2*i+1);
  }
  visit(T[i]);
  if (T[2*i+2] != Nil){
      inTraverse(T, 2*i+2);
  }
}

Status inOrderTraverse(OrderBiTree T){
  if (!biTreeIsEmpty(T)) {
      inTraverse(T, 0);
  }
  printf("\n");
  return OK;
}

// 后序遍历
void postTraverse(OrderBiTree T,int i){
  if(T[2*i+1]!=Nil){
      postTraverse(T,2*i+1);
  }
  if(T[2*i+2]!=Nil){
      postTraverse(T,2*i+2);
  }
  visit(T[i]);
}

Status postOrderTraverse(OrderBiTree T)
{
  if(!biTreeIsEmpty(T)) {
      postTraverse(T,0);
  }
  printf("\n");
  return OK;
}
2、链式存储
/* 存储空间初始分配量 */
#define MAXSIZE 100
/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Status;
typedef char CElemType;
CElemType Nil='#'; /* 字符型以空格符为空 */
typedef struct BiTNode  /* 结点结构 */
{
  CElemType data;        /* 结点数据 */
  struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*LinkBiTree;

//将字符串存入到数组T中
typedef char String[24]; /*  0号单元存放串的长度 */
Status strAssign(String s,char *chars)
{
  int i;
  if(strlen(chars)>MAXSIZE)
      return ERROR;
  else
  {
      s[0]=strlen(chars);
      for(i=1;i<=s[0];i++)
          s[i]=*(chars+i-1);
      return OK;
  }
}

二叉树的初始化

Status initBiTree(LinkBiTree *T){
  (*T) = NULL;
  return OK;
}

销毁二叉树

void destory(LinkBiTree *T){
  if (*T) {
      if ((*T)->lchild) {
          destory(&(*T)->lchild);
      }
      if ((*T)->rchild) {
          destory(&(*T)->rchild);
      }
      
      free(*T);
      (*T) = NULL;
  }
}
#define ClearBiTree DestroyBiTree

创建二叉树

static int indexs = 1;
static String str;
void createBiTree(LinkBiTree *T){
  CElemType data = str[indexs++];
  if (data == '#') {
      *T = NULL;
  }else{
      *T = (LinkBiTree)malloc(sizeof(BiTNode));
      if (!*T) {
          exit(0);
      }
      (*T)->data = data;//给结点赋值
      createBiTree(&(*T)->lchild);//创建左子树
      createBiTree(&(*T)->rchild);//创建右子树
  }
}

判断二叉树是否为空

Status biTreeIsEmpty(LinkBiTree T){
  if (T) {
      return TRUE;
  }else{
      return FALSE;
  }
}

获取二叉树的深度

int getDepthFromBiTree(LinkBiTree T){
  if (!T) {
      return 0;
  }
  int i,j;
  if (T->lchild) {
      i = getDepthFromBiTree(T->lchild);
  }else{
      i = 0;
  }
  if (T->rchild) {
      j = getDepthFromBiTree(T->rchild);
  }else{
      j = 0;
  }
  return i>j?(i+1):(j+1);
}

根据结点位置获取结点的值

CElemType getValue(LinkBiTree T){
  if (T) {
      return T->data;
  }
  return Nil;
}

给处于位置e的结点赋值

void setValue(LinkBiTree T, CElemType value){
  T->data = value;
}

二叉树的遍历

//前序遍历

void preOrderTraverse(LinkBiTree T){
  if (T) {
      printf("%c",T->data);
      preOrderTraverse(T->lchild);
      preOrderTraverse(T->rchild);
  }
}

//中序遍历
void inOrderTraverse(LinkBiTree T){
  if (T) {
      inOrderTraverse(T->lchild);
      printf("%c",T->data);
      inOrderTraverse(T->rchild);
  }
}

// 后序遍历
void postOrderTraverse(LinkBiTree T)
{
  if (T) {
      postOrderTraverse(T->lchild);
      postOrderTraverse(T->rchild);
      printf("%c",T->data);
  }
}

顺序二叉树
链式二叉树

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,992评论 6 493
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,212评论 3 388
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 159,535评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,197评论 1 287
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,310评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,383评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,409评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,191评论 0 269
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,621评论 1 306
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,910评论 2 328
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,084评论 1 342
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,763评论 4 337
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,403评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,083评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,318评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,946评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,967评论 2 351