数据结构和算法-二叉树

一、概念

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

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

顺序二叉树
 链式二叉树