二叉树的基本操作

    xiaoxiao2021-12-15  28

    #include<stdio.h> #include<stdlib.h> #include<string.h> #include<conio.h> typedef struct Node { char data;     struct Node *Lchild;     struct Node *Rchild;        }BiTNode,*BiTree;    /*************************************/  void createBiTree(BiTree *root)                  //扩展先序遍历序列创建二叉树  { char ch; ch    = getchar(); if(ch == '^')  *root=NULL; else { *root=(BiTree)malloc(sizeof(BiTNode)); (*root)->data=ch; createBiTree(&((*root)->Lchild)); createBiTree(&((*root)->Rchild)); }   } void printTree(BiTree root,int h)               //按树状输出二叉树  { int i; if(root==NULL) return ; printTree(root->Rchild,h+1); for(i=0;i<h;i++) printf(" "); printf("%c\n",root->data); printTree(root->Lchild,h+1);     } /*************************************/ /************************************/ void Preorder(BiTree root){              //先序遍历算法      if(root){          printf(",",root->data);         Preorder(root->Lchild);         Preorder(root->Rchild);     } } /***********************************/ void Inorder(BiTree root){              //中序遍历算法      if(root==NULL) return;         Inorder(root->Lchild);         printf(",",root->data);         Inorder(root->Rchild); } /***********************************/ void NRInorder(BiTree root)              //非递归中序遍历  {           BiTree s;             //s-指向当前节点 BiTree stack[100];               //定义栈 int    top=-1;                 //初始化栈顶指针 if(root==NULL) return; stack[++top]=root;                  //根指针入栈 s=root->Lchild;                     //s指向左子树 while(s!=NULL||top!=-1)             //当存在节点(涉及到根下右子树)或者栈不为空,进行遍历 { while(s!=NULL)                  //如果存在节点,寻找最左子树并入栈 { if(top>=99) { printf("栈为满\n"); return; } stack[++top]=s;            //当前节点入栈 s=s->Lchild;               //左子树进行遍历 } if(top==-1) { printf("栈为空\n"); return; } s=stack[top--];      //弹出栈顶元素到s中   printf("%c ",s->data);      //输出当前节点元素值 s=s->Rchild;      //遍历右子树 } } /*************************************/  void Postorder(BiTree root){              //后序遍历算法      if(root){          Postorder(root->Lchild);         Postorder(root->Rchild);         printf(",",root->data);     } } /***********************************/       //树的高度  int PostTreeDepth(BiTree root) { int hl,hr,h; if(root==NULL) return 0; else { hl=PostTreeDepth(root->Lchild); hr=PostTreeDepth(root->Rchild); h =(hl>hr? hl:hr)+1; return h; } }  /**********************************/  int PostTreeLeaf(BiTree root)              //后序遍历求节点数  { int count,count1,count2; if(root == NULL)     return 0; if(root->Lchild == NULL && root->Rchild == NULL)    return 1; count1=PostTreeLeaf(root->Lchild); count2=PostTreeLeaf(root->Rchild); count =count1+count2; return count; } /***********************************/ int PostTreeOneAspectLeaf(BiTree root,int aspect)      //求树每层有多少个叶子  { int count,count1,count2; if(root==NULL||aspect==0) return 0; if(aspect==1&&root->Lchild==NULL&&root->Rchild==NULL) return 1; count1=PostTreeOneAspectLeaf(root->Lchild,aspect-1); count2=PostTreeOneAspectLeaf(root->Rchild,aspect-1); count=count1+count2;     return count;     } BiTree SDParents(BiTree root,BiTree current) { BiTree p; if(root==NULL) return NULL; if(root->Lchild==current||root->Rchild==current)     return root; p=SDParents(root->Lchild,current);     if(p!=NULL) return p;     else return(SDParents(root->Rchild,current)); } int main() { BiTree root=NULL; int h;            //树的高度; int count;        //树的叶子节点的个数  int aspect=1;       //树的层数   char ch; printf("请按扩展的先序遍历序列输入树的节点数据:\n"); createBiTree(&root); printf("按树状结果输出:\n"); printTree(root,1);  printf("\n先序遍历输出:\n"); Preorder(root); printf("\n中序遍历输出:\n"); Inorder(root); printf("\n非递归中序遍历输出:\n"); NRInorder(root); printf("\n后序遍历输出:\n"); Postorder(root); h=PostTreeDepth(root); printf("\n树的高度为:\n"); printf("%d",h);  count=PostTreeLeaf(root); printf("\n树的叶子节点个数为:\n"); printf("%d\n",count);  printf("第%d层有%d个叶子结点",aspect,count); printf("\n结点B的双亲为:\n"); root=SDParents(root,root->Lchild); printf("%c",root->data); }
    转载请注明原文地址: https://ju.6miu.com/read-1000204.html

    最新回复(0)