精品99久久,91人妻免费观看视频,熟女9999

一、概念

二叉樹(shù)：每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)
如圖：

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

滿二叉樹(shù)：除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹(shù)

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

完全二叉樹(shù)：若設(shè)二叉樹(shù)的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布，這就是完全二叉樹(shù)

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

二、相關(guān)術(shù)語(yǔ)

樹(shù)的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹(shù)的分支
孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子
雙親結(jié)點(diǎn)：B 結(jié)點(diǎn)是A 結(jié)點(diǎn)的孩子，則A結(jié)點(diǎn)是B 結(jié)點(diǎn)的雙親
兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)
堂兄結(jié)點(diǎn)：同一層上結(jié)點(diǎn)
葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為 0 的結(jié)點(diǎn)
結(jié)點(diǎn)層：根結(jié)點(diǎn)的層定義為1；根的孩子為第二層結(jié)點(diǎn)，依此類推
樹(shù)的深度：樹(shù)中最大的結(jié)點(diǎn)層
結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹(shù)的個(gè)數(shù)
樹(shù)的度：樹(shù)中最大的結(jié)點(diǎn)度

三、二叉樹(shù)性質(zhì)

性質(zhì)1: 在二叉樹(shù)的第n層上最多有2?? ? 1?個(gè)結(jié)點(diǎn)(n>=1)
性質(zhì)2: 深度為n的二叉樹(shù)最多有2? - 1 個(gè)結(jié)點(diǎn)(n>=1)
性質(zhì)3: 對(duì)于任何一顆二叉樹(shù)T,如果其終端結(jié)點(diǎn)數(shù)為n?,度為2的結(jié)點(diǎn)數(shù)為n?,則n? = n? + 1;
性質(zhì)4: 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)深度為(log?n)+1
性質(zhì)5:對(duì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從上至下和從左至右的順序?qū)Χ鏄?shù)的所有結(jié)點(diǎn)從1開(kāi)始編號(hào)，則對(duì)于任意的序號(hào)為i的結(jié)點(diǎn)有:
A. 如果i>1，那么序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號(hào)為i/2;
B. 如果i=1，那么序號(hào)為i的結(jié)點(diǎn)為根節(jié)點(diǎn)，無(wú)雙親結(jié)點(diǎn);
C. 如果2i<=n，那么序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)序號(hào)為2i;
D. 如果2i>n，那么序號(hào)為i的結(jié)點(diǎn)無(wú)左孩子;
E. 如果2i+1<=n，那么序號(hào)為i的結(jié)點(diǎn)右孩子序號(hào)為2i+1;
F. 如果2i+1>n，那么序號(hào)為i的結(jié)點(diǎn)無(wú)右孩子。

四、二叉樹(shù)的代碼實(shí)現(xiàn)

1、順序存儲(chǔ)

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

typedef struct {
  int level; //結(jié)點(diǎn)層
  int order; //本層的序號(hào)(按照滿二叉樹(shù)給定序號(hào)規(guī)則)
} NodePosition;

//構(gòu)造空二叉樹(shù)
Status initBiTree(OrderBiTree T){
  for (int i = 0; i<MAX_TREE_SIZE; i++) {
      T[i] = Nil;
  }
  return OK;
}
//由于清空二叉樹(shù)與初始化二叉樹(shù)是一致的
#define clearBiTree initBiTree

按層序次序依次給二叉樹(shù)結(jié)點(diǎn)賦值

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;
}

判斷二叉樹(shù)是否為空

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

獲取二叉樹(shù)的深度

int getDepthFromBiTree(OrderBiTree T){
  int i;
  //獲取二叉樹(shù)T的最后一個(gè)結(jié)點(diǎn)的序列號(hào)
  for (i = MAX_TREE_SIZE-1; i>=0; i--) {
      if (T[i] != Nil) {
          break;
      }
  }
  //根據(jù)二叉樹(shù)性質(zhì)：深度為n的二叉樹(shù)最多有2? - 1個(gè)結(jié)點(diǎn)
  int j = -1;
  do {
      j++;
  } while (pow(2, j)<=i);
  
  return j;
}

根據(jù)結(jié)點(diǎn)位置獲取結(jié)點(diǎn)的值

CElemType getValueWithPosition(OrderBiTree T, NodePosition p){
  //p.level層第一個(gè)結(jié)點(diǎn)的序列號(hào)，根結(jié)點(diǎn)序列號(hào)從1開(kāi)始
  int index = pow(2, p.level-1);
  
  //p.level層p.order位置結(jié)點(diǎn)的序列號(hào)
  index = index+p.order-1;
  return T[index-1];
}

給處于位置e的結(jié)點(diǎn)賦值

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;
}

獲取某結(jié)點(diǎn)的雙親結(jié)點(diǎn)

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;
}

獲取某結(jié)點(diǎn)的左子結(jié)點(diǎn)

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;
}

獲取某結(jié)點(diǎn)的右子結(jié)點(diǎn)

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;
}

獲取某結(jié)點(diǎn)的左兄弟

CElemType leftSibling(OrderBiTree T,CElemType e){
 if (T[0] == Nil) {
     return Nil;
 }
 for (int i=0; i<MAX_TREE_SIZE-1; i++) {
     //找到e數(shù)據(jù)的結(jié)點(diǎn)，且該結(jié)點(diǎn)是右結(jié)點(diǎn)
     if (T[i] == e&&i%2==0) {
         return T[i-1];
     }
 }
 
 return Nil;
}

獲取某結(jié)點(diǎn)的右兄弟

CElemType rightSibling(OrderBiTree T,CElemType e){
  if (T[0] == Nil) {
      return Nil;
  }
  for (int i=0; i<MAX_TREE_SIZE-1; i++) {
      //找到e數(shù)據(jù)的結(jié)點(diǎn)，且該結(jié)點(diǎn)是左結(jié)點(diǎn)
      if (T[i] == e&&i%2==1) {
          return T[i+1];
      }
  }
  
  return Nil;
}

二叉樹(shù)的遍歷

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

//層序遍歷
void levelOrderTraverse(OrderBiTree T){
  int i = MAX_TREE_SIZE-1;
  //找到最后一個(gè)非空結(jié)點(diǎn)
  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){
  //打印結(jié)點(diǎn)
  visit(T[i]);
  //遍歷左子樹(shù)
  if (T[2*i+1]!=Nil) {
      preTraverse(T, 2*i+1);
  }
  //遍歷右子樹(shù)
  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、鏈?zhǔn)酱鎯?chǔ)

/* 存儲(chǔ)空間初始分配量 */
#define MAXSIZE 100
/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int Status;
typedef char CElemType;
CElemType Nil='#'; /* 字符型以空格符為空 */
typedef struct BiTNode  /* 結(jié)點(diǎn)結(jié)構(gòu) */
{
  CElemType data;        /* 結(jié)點(diǎn)數(shù)據(jù) */
  struct BiTNode *lchild,*rchild; /* 左右孩子指針 */
}BiTNode,*LinkBiTree;

//將字符串存入到數(shù)組T中
typedef char String[24]; /*  0號(hào)單元存放串的長(zhǎng)度 */
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;
  }
}

二叉樹(shù)的初始化

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

銷毀二叉樹(shù)

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

創(chuàng)建二叉樹(shù)

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;//給結(jié)點(diǎn)賦值
      createBiTree(&(*T)->lchild);//創(chuàng)建左子樹(shù)
      createBiTree(&(*T)->rchild);//創(chuàng)建右子樹(shù)
  }
}

判斷二叉樹(shù)是否為空

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

獲取二叉樹(shù)的深度

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);
}

根據(jù)結(jié)點(diǎn)位置獲取結(jié)點(diǎn)的值

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

給處于位置e的結(jié)點(diǎn)賦值

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

二叉樹(shù)的遍歷

//前序遍歷

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);
  }
}

順序二叉樹(shù)
鏈?zhǔn)蕉鏄?shù)

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)和算法-二叉樹(shù)

數(shù)據(jù)結(jié)構(gòu)和算法-二叉樹(shù)

一、概念

二、相關(guān)術(shù)語(yǔ)

三、二叉樹(shù)性質(zhì)

四、二叉樹(shù)的代碼實(shí)現(xiàn)

1、順序存儲(chǔ)

2、鏈?zhǔn)酱鎯?chǔ)

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)和算法-二叉樹(shù)

一、概念

二、相關(guān)術(shù)語(yǔ)

三、二叉樹(shù)性質(zhì)

四、二叉樹(shù)的代碼實(shí)現(xiàn)

1、順序存儲(chǔ)

2、鏈?zhǔn)酱鎯?chǔ)

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一、概念

二、相關(guān)術(shù)語(yǔ)

四、二叉樹(shù)的代碼實(shí)現(xiàn)

1、順序存儲(chǔ)

2、鏈?zhǔn)酱鎯?chǔ)