二叉树的输入输出操作

一、二叉树的抽象数据类型:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 ADT BinaryTree{ 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R:    若D=Φ,则R=Φ,称BinaryTree为空二叉树;    若D≠Φ,则R={H},H是如下二元关系;      (1)在D中存在惟一的称为根的数据元素root,它在关系H下无前驱;      (2)若D-{root}≠Φ,则存在D-{root}={D1,Dr},且D1∩Dr =Φ;      (3)若D1≠Φ,则D1中存在惟一的元素x1,<root,x1>∈H,且存在D1上的关系H1 ⊆H;若Dr≠Φ,则Dr中存在惟一的元素xr,<root,xr>∈H,且存在Dr上的关系Hr ⊆H;H={<root,x1>,<root,xr>,H1,Hr};      (4)(D1,{H1})是一棵符合本定义的二叉树,称为根的左子树;(Dr,{Hr})是一棵符合本定义的二叉树,称为根的右子树。 基本操作:    InitBiTree( &T )      操作结果:构造空二叉树T。    DestroyBiTree( &T )      初始条件:二叉树T已存在。      操作结果:销毁二叉树T。    CreateBiTree( &T, definition )      初始条件:definition给出二叉树T的定义。      操作结果:按definiton构造二叉树T。    ClearBiTree( &T )      初始条件:二叉树T存在。      操作结果:将二叉树T清为空树。    BiTreeEmpty( T )      初始条件:二叉树T存在。      操作结果:若T为空二叉树,则返回TRUE,否则返回FALSE。    BiTreeDepth( T )      初始条件:二叉树T存在。      操作结果:返回T的深度。    Root( T )      初始条件:二叉树T存在。      操作结果:返回T的根。    Value( T, e )      初始条件:二叉树T存在,e是T中某个结点。      操作结果:返回e的值。    Assign( T, &e, value )      初始条件:二叉树T存在,e是T中某个结点。      操作结果:结点e赋值为value。    Parent( T, e )      初始条件:二叉树T存在,e是T中某个结点。      操作结果:若e是T的非根结点,则返回它的双亲,否则返回“空”。    LeftChild( T, e )      初始条件:二叉树T存在,e是T中某个结点。      操作结果:返回e的左孩子。若e无左孩子,则返回“空”。    RightChild( T, e )      初始条件:二叉树T存在,e是T中某个结点。      操作结果:返回e的右孩子。若e无右孩子,则返回“空”。    LeftSibling( T, e )      初始条件:二叉树T存在,e是T中某个结点。      操作结果:返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回“空”。    RightSibling( T, e )      初始条件:二叉树T存在,e是T中某个结点。      操作结果:返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回“空”。    InsertChild( T, p, LR, c )      初始条件:二叉树T存在,p指向T中某个结点,LR为0或1,非空二叉树c与T不相交且右子树为空。      操作结果:根据LR为0或1,插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树。    DeleteChild( T, p, LR )      初始条件:二叉树T存在,p指向T中某个结点,LR为0或1。      操作结果:根据LR为0或1,删除T中p所指结点的左或右子树。    PreOrderTraverse( T, visit() )      初始条件:二叉树T存在,Visit是对结点操作的应用函数。      操作结果:先序遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败,则操作失败。    InOrderTraverse( T, visit() )      初始条件:二叉树T存在,Visit是对结点操作的应用函数。      操作结果:中序遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败,则操作失败。    PostOrderTraverse( T, visit() )      初始条件:二叉树T存在,Visit是对结点操作的应用函数。      操作结果:后序遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败,则操作失败。    LevelOrderTraverse( T, visit() )      初始条件:二叉树T存在,Visit是对结点操作的应用函数。      操作结果:层次遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败,则操作失败。 }ADT BinaryTree

 

 

二、基本操作的实现:

二叉树的结点结构体:

 

1 2 3 4 typedef  struct {      TElemType data;      struct  BiTNode *lchild,*rchild; }BiTNode,*BiTree;

 

 

1.二叉树的创建:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 /*******************************************/ /*          按照前序遍历建立二叉树         */ /*******************************************/   Status CreateBiTree(BiTree &T) {      //按先序次序输入二叉树中结点的值(一个字符),      //空格字符表示空树,构造二叉链表表示的二叉树T。      char  ch;      ch = getchar (); //scanf("%c",&ch);      if (ch == ' ' )          T = NULL;      else      {          if (!(T = (BiTNode*) malloc ( sizeof (BiTNode))))              exit (OVERFLOW);          T->data = ch;                //生成根结点          CreateBiTree(T->lchild);     //构造左子树          CreateBiTree(T->rchild);     //构造右子树      }      return  OK; }

 

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 /************************************************************/ /*                  按层次顺序建立一棵二叉树 :队列         */ /************************************************************/   Status LevelCreateBiTree(BiTree &T) {      BiTree p,s; //p指向父亲结点,s指向孩子结点      Queue BiNodeQueue;      char  ch;      ch= getchar ();      if (ch== ' ' )      {          return  NULL;      }      T=(BiTNode*) malloc ( sizeof (BiTNode)); //生成根结点      T->data=ch;      EnQueue(BiNodeQueue,T); //用队列实现层次遍历      while (!BiNodeQueue.Empty())      {          DeQueue(BiNodeQueue,p);          ch= getchar (); //为了简化操作,分别对左右子结点进行赋值。          if (ch!= ' ' ) //子树不空则进队列进行扩充。下同          {              s=(BiTNode*) malloc ( sizeof (BiTNode));              s->data=ch;              p->lchild=s;              EnQueue(BiNodeQueue,s);          }          else          {              p->lchild=NULL;          }          ch= getchar ();          if (ch!= ' ' )          {              s=(BiTNode*) malloc ( sizeof (BiTNode));              s->data=ch;              p->rchild=s;              EnQueue(BiNodeQueue,s);          }          else          {              p->rchild=NULL;          }      }      return  OK; }

 

 

2.二叉树的前序遍历:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 /*******************************************/ /*          按照前序递归遍历二叉树         */ /*******************************************/   Status PreOrderTraverse(BiTree T) {      if (T)      {          printf ( "%d" ,T->data);           PreOrderTraverse(T->lchild);           PreOrderTraverse(T->rchild);      }      return  OK; }

 

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 /*******************************************/ /*          按照前序非递归遍历二叉树:栈   */ /*******************************************/   Status PreOrderTraverse(BiTree T) {      stack S;      InitStack(S);      BiTree p=T;  //p指向当前访问的结点            while (p||!StackEmpty(S))      {          if (p)          {              printf ( "%c" ,p->data);              Push(S,p);              p=p->lchild;          }          else          {              Pop(S,p);              p=p->rchild;          }      }      return  OK; }

 

 

3.二叉树的中序遍历:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 /*******************************************/ /*          按照中序递归遍历二叉树         */ /*******************************************/   Status InOrderTraverse(BiTree T) {      if (T)      {          InOrderTraverse(T->lchild);          printf ( "%d" ,T->data);          InOrderTraverse(T->rchild);      }      return  OK; }

 

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 /*******************************************/ /*          按照中序非递归遍历二叉树       */ /*******************************************/   Status InOrderTraverse(BiTree T)      stack S;      BiTree p;      InitStack(S);  Push(S, T);       while  (!StackEmpty(S))      {          while  (GetTop(S, p) && p)              Push(S, p->lchild);   // 向左走到尽头          Pop(S, p);                // 空指针退栈(叶子的左孩子)          if  (!StackEmpty(S))          {   // 访问结点,向右一步              Pop(S, p);               printf ( "%d" ,p->data);   //当前根结点              Push(S, p->rchild);          }      }      return  OK; }

 

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 /*******************************************/ /*          按照中序非递归遍历二叉树       */ /*******************************************/   Status InOrderTraverse(BiTree T)      stack S;      InitStack(S);      BiTree p=T;       while  (p || !StackEmpty(S))      {          if  (p)          {              Push(S, p);               p = p->lchild;          // 非空指针进栈,继续左进          else          // 上层指针退栈,访问其所指结点,再向右进              Pop(S, p);               printf ( "%d" ,p->data);              p = p->rchild;          }      }      return  OK; }

 

 

4.二叉树的后序遍历:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 /*******************************************/ /*          按照后序递归遍历二叉树         */ /*******************************************/   Status PostOrderTraverse(BiTree T) {      if (T)      {          PostOrderTraverse(T->lchild);          PostOrderTraverse(T->rchild);          printf ( "%d" ,T->data);      }      return  OK; }

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 /*******************************************/ /*        按照后序非递归遍历二叉树         */ /*******************************************/   Status PostOrderTraverse(BiTree T) {      stack S;      InitStack(S);      BiTree p=T,pre=NULL;      while  ( p || !StackEmpty(S))      {          if  (p)          {              Push(S,p);              p = p->left;          }          else          {              Pop(S,p);              if  (p->right!=NULL && pre!=p->right)              { //pre指向上次访问的右结点,避免再次访问                  p=p->right;              }              else              {                  printf ( "%d" ,p->data);                  pre=p;                  p=NULL;              }          }      } }

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 /*******************************************/ /*        按照后序非递归遍历二叉树         */ /*******************************************/   Status PostOrderTraverse(BiTree T) {      BiTree p = T,last = NULL;      stack S;      InitStack(S);      Push(S,p);      while (!StackEmpty(S))      {          Pop(S,p);          if (last == p->left || last == p->right) //左右子树已经访问完了,该访问根节点了          {              printf ( "%d" ,p->data);              last = p;          }          else  if (p->left || p->right) //左右子树未访问,当前节点入栈,左右节点入栈          {              Push(S,p);              if (p->right)                  Push(S,p->right);              if (p->left)                  Push(S,p->left);          }          else  //当前节点为叶节点,访问          {              printf ( "%d" ,p->data);              last = p;          }      } }

 

 

5.二叉树的层次遍历:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 /*******************************************/ /*           按照层次遍历二叉树            */ /*******************************************/ void  LevelOrderTraverse(BiTree T) {      Queue BiNodeQueue;      BiTree p=T;      EnQueue(BiNodeQueue,p);      while (!BiNodeQueue.Empty())      {          DeQueue(BiNodeQueue,p);          if (p)          {              printf ( "%c" ,p->data);              EnQueue(BiNodeQueue,p->lchild);              EnQueue(BiNodeQueue,p->rchild);          }      } }

 

6.交换左右子树:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 /*******************************************/ /*      递归法将二叉树的左右子树互换       */ /*******************************************/ void  Exchange(BiTree T) {      BiTree temp;      if (T)      {          Exchange1(T->lchild);          Exchange1(T->rchild);          temp=T->lchild;          T->lchild=T->rchild;          T->rchild=temp;      } }

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 /*******************************************/ /*      非递归法将二叉树的左右子树互换     */ /*******************************************/ void  Exchange(BiTree T) {      stack S;      InitStack(S);      BiTree p=T,temp;      while (p||!StackEmpty(S))      {          if (p)          {              Push(S,p);              temp=p->lchild;              p->lchild=p->rchild;              p->rchild=temp;              p=p->lchild;          }          else          {              Pop(S,p);              p->rchild;          }      } }

 

7.统计二叉树中叶子结点的数目:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 /*******************************************/ /*        递归法求叶子结点个数             */ /*******************************************/ int  LeavesNum(BiTree T) {      if (T)      {          if (T->lchild==NULL&&T->rchild==NULL)          {              return  1;          }          return  LeavesNum(T->lchild)+LeavesNum(T->rchild);      }      return  0; }

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 /*******************************************/ /*        非递归法求叶子结点个数           */ /*******************************************/ int  LeavesNum(BiTree T) {      int  count=0;      stack S;      InitStack(S);      BiTree p=T;      while (p||!StackEmpty(S))      {          if (p)          {              Push(S,p);              if (p->lchild==NULL&&p->rchild==NULL)              {                  count++;              }              p=p->lchild;          }          else          {              Pop(S,p);              p=p->rchild;          }      }      return  count; }

 

 

8.求二叉树的深度:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 /**********************************************/ /*                  求一棵树的高度            */ /**********************************************/   int  Depth(BiTree T) {      int   lh = rh =0 ;      BiTree p=T;      if (p==NULL)      {          return  0 ;      }      else      {          lh = Depth( p->lchild ) ;          rh = Depth( p->rchild ) ;          return  ( lh > rh ? lh : rh ) + 1 ;      } }

9.判断两棵树是否等价:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 /*******************************************************/ /*                  判断两棵是否等价                   */ /*******************************************************/   int  Is_equal( BiTree T1 , BiTree T2 ) {      int  t=0;      if (NULL == T1 && NULL == T2)      {          t=1;      }      else      {          if (NULL !=T1 &&NULL != T2 )          {              if (T1->data == T2->data)              {                  if (Is_equal(T1->lchild,T2->lchild))                  {                      t=Is_equal(T1->rchild,T2->rchild);                  }              }          }      }      return  t; }

10.查找某个信息是否在这棵树中:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 /****************************************************/ /*            查找某个信息是否在这棵树中            */ /****************************************************/   BiTree Locate(BiTree T, char  x) {      BiTree p=T;      if (P==NULL)          return  NULL;      else      {          if ( P -> data == x )              return  P;          else          {              p = Locate(P->lchild,x);              if (p)                  return  p;              else                  return  Locate(P->rchild,x);          }      } }

11.结点个数:

1 2 3 4 5 6 7 8 9 10 11 /****************************************************/ /*                  树的结点个数                    */ /****************************************************/   int   Num_Of_Node(BiTree t) {      if (t==NULL)          return  0 ;      else          return  Num_Of_Node(t->lchild)+Num_Of_Node(t->rchild)+1; }

12.

    原文作者:Miles-
    原文地址: https://blog.csdn.net/wl_ss/article/details/77687218
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞