第1關(guān)?先序遍歷創(chuàng)建二叉鏈表存儲的二叉樹及遍歷操作

void CreateBiTree(BiTree &T)
{  //按先序次序輸入二叉樹中結(jié)點的值
   // 構(gòu)造二叉鏈表表示的二叉樹T。變量Nil表示空(子)樹。
  /********** Begin **********/ 
  
   // if (!T) return ;
   TElemType data;
   input(data);
   if(data == Nil) {
      return ;
   }
   T = (BiTree)malloc(sizeof(BiTNode));
   if(!T) return;
   T->data = data;
   CreateBiTree(T->lchild);
   CreateBiTree(T->rchild);
    
  /********** End **********/
}
 int  BiTreeEmpty(BiTree T)
 { // 初始條件：二叉樹T存在。操作結(jié)果：若T為空二叉樹，則返回TRUE，否則FALSE
    /********** Begin **********/ 
   if(!T){
      // if(T->data == Nil) return TRUE;
      // else return FALSE;
      return TRUE;
   }
   else return FALSE;
   /********** End **********/
}
void ProOrderTraverse(BiTree T,void(*Visit)(TElemType))
{ // 采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應用函數(shù)。
   // 先序遍歷二叉樹T的遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit
    /********** Begin **********/ 
   if (!T) {
      return ;
    }
    Visit(T->data);
    ProOrderTraverse(T->lchild,Visit);
    ProOrderTraverse(T->rchild,Visit);
    /********** End **********/
 }
void InOrderTraverse(BiTree T,void(*Visit)(TElemType))
{ // 采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應用函數(shù)。
   // 中序遍歷二叉樹T的遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit
    /********** Begin **********/ 
    if(!T){
      return;
    }
   InOrderTraverse(T->lchild,Visit);
   Visit(T->data);
   InOrderTraverse(T->rchild,Visit);
    
   /********** End **********/
 }
void PostOrderTraverse(BiTree T,void(*Visit)(TElemType))
{ // 初始條件：二叉樹T存在，Visit是對結(jié)點操作的應用函數(shù)
   // 操作結(jié)果：后序遞歸遍歷T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次
    /********** Begin **********/ 
    if(!T){
       return ; 
    }
    PostOrderTraverse(T->lchild,Visit);
    PostOrderTraverse(T->rchild,Visit);
    Visit(T->data);
     /********** End **********/
}
void DestoryBiTree(BiTree &T)
{  // 初始條件：二叉樹T存在。操作結(jié)果：銷毀二叉樹T
    /********** Begin  **********/
   if(!T){
      return ;
   }
   DestoryBiTree(T->lchild);
   DestoryBiTree(T->rchild);
   free(T);
    /********** End **********/
}

?第2關(guān)?計算二叉樹的高度、總節(jié)點個數(shù)和葉子節(jié)點個數(shù)

int BiTreeDepth(BiTree T)
{	 // 初始條件：二叉樹T存在。操作結(jié)果：返回T的深度
    /********** Begin **********/ 
	if(!T) return 0;
    int lchild = BiTreeDepth(T->lchild);
    int rchild = BiTreeDepth(T->rchild);
    return 1+( 1+lchild>1+rchild?lchild:rchild);
    // return 1+lchild+rchild;
     /********** End **********/
}


int NodeCount(BiTree T)
{
	//初始條件：二叉樹T存在。操作結(jié)果：返回T的結(jié)點數(shù)
    /********** Begin **********/
	if(!T) return 0;
    int lchild = NodeCount(T->lchild);
    int rchild = NodeCount(T->rchild);
    return 1+lchild+rchild;
    // return 1 + lchild + rchild;
    /********** End **********/
}


int LeafNodeCount(BiTree T)
{
	//初始條件：二叉樹T存在。操作結(jié)果：返回T的葉子結(jié)點數(shù)
    /********** Begin **********/
	if(!T) return 0;
    if(!T->lchild && !T->rchild) return 1;
    return LeafNodeCount(T->lchild) + LeafNodeCount(T->rchild);
	/********** End **********/
}

?第3關(guān)?層次遍歷二叉樹

void LevelOrderTraverse(BiTree T,void(*Visit)(TElemType))
 { // 初始條件：二叉樹T存在，Visit是對結(jié)點操作的應用函數(shù)
   // 操作結(jié)果：層序遞歸遍歷T(利用隊列)，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次
    /********** Begin **********/ 
    if(!T) return ;
    BiTree p;
    LinkQueue q;
    InitQueue(q);  // 創(chuàng)建隊列
    // 入隊操作
    EnQueue(q,T);
    while(!QueueEmpty(q)){
      DeQueue(q,p);

      Visit(p->data);
      if(p->lchild){
        EnQueue(q,p->lchild);
      }
      if(p->rchild){
        EnQueue(q,p->rchild);
      }
    }
    DestroyQueue(q);
    /********** End **********/
}

?第4關(guān)?遞歸實現(xiàn)二叉樹左右子樹交換

void exchange ( BiTree T )
{
  // 實現(xiàn)二叉樹左右子樹的交換（遞歸法）
  /********** Begin *********/
  
  if(!T) return ;
  BiTree temp;

  exchange(T->lchild);
  exchange(T->rchild);
  
  temp = T->rchild;
  T->rchild = T->lchild;
  T->lchild = temp;
  
	/********** End **********/
}

?第5關(guān)?非遞歸實現(xiàn)二叉樹左右子樹交換

void exchange(BiTree T)
{
  // 實現(xiàn)二叉樹左右子樹的交換（棧實現(xiàn)）
  /********** Begin *********/
  SqStack s;
  BiTree p,temp;
  InitStack(s);
  if(!T) return;
  Push(s,T);
  while(!StackEmpty(s)){
    Pop(s,p);
    if(p->rchild){
      Push(s,p->rchild);
    }
    if(p->lchild){
      Push(s,p->lchild);
    }
    temp = p->lchild;
    p->lchild = p->rchild;
    p->rchild = temp;
  }
  /********** End **********/
}

?第6關(guān)?非遞歸實現(xiàn)二叉樹的中序遍歷文章來源地址http://www.zghlxwxcb.cn/news/detail-774786.html

void InOrderTraverse2(BiTree T,void(*Visit)(TElemType))
{  // 采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應用函數(shù)。
   // 中序遍歷二叉樹T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit
  /********** Begin *********/
  
  if(!T) return ;
  
  SqStack s;
  InitStack(s);
  BiTree p = T;
  while(!StackEmpty(s)||p){
      while(p){
          Push(s,p);
          p = p->lchild;
      }
      Pop(s,p);
      Visit(p->data);
        p = p->rchild;
    }
    DestroyStack(s);

  /********** End **********/
 }

到了這里，關(guān)于頭歌 二叉樹的二叉鏈表存儲及基本操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！