C 二叉树

刺骨的言语ヽ痛彻心扉 2022-05-19 09:27 115阅读 0赞

\#include<malloc.h>  
\#include<stdio.h>  
\#include<process.h>

int da = 0;

typedef struct BiTNode\{  
 char data;  
   
 struct BiTNode \*lchild, \*rchild;  
\}BiTNode, \*BiTree;

int CreateBiTree(BiTree &T)\{  
   
 //按先序次序输入二叉树中结点的值（一个字符） ，空格字符表示空树  
 //构造二叉链表表示的二叉树T。  
   
 char ch;  
   
 scanf("%c", &ch);  
   
 if(ch == ' ')\{  
  T = NULL;  
 \}  
    else\{  
     T = (BiTNode \*)malloc(sizeof(BiTNode));  
       
     if(!T)\{  
      exit(-1);  
     \}  
       
     T->data = ch;  
       
     CreateBiTree(T->lchild);  
       
     CreateBiTree(T->rchild);  
    \}  
     
    return 1;  
\}

void Preorder(BiTree T)\{  
   
 //先序遍历  
 //移动 printf("%c\\n", T->data);可得到中序遍历和后序遍历  
   
 if(T)\{  
  printf("%c\\n", T->data);  
    
  Preorder(T->lchild);  
    
  Preorder(T->rchild);  
 \}  
\}

void Preorder3(BiTree T)\{  
   
 if(T)\{  
    
  Preorder(T->lchild);  
    
  Preorder(T->rchild);  
    
  printf("%c\\n", T->data);  
 \}  
\}

void Preorder2(BiTree T)\{  
   
 if(T)\{  
    
  Preorder(T->lchild);  
    
  printf("%c\\n", T->data);  
    
  Preorder(T->rchild);  
 \}  
\}

int Height(BiTree T)\{  
   
 //求二叉树的深度  
   
 int m ,n;  
   
 if(T == NULL)\{  
  return 0;  
 \}  
 else\{  
  m = Height(T->lchild);  
    
  n = Height(T->rchild);  
    
  if(m >= n)\{  
   return m+1;  
  \}  
  else\{  
   return n+1;  
  \}  
 \}  
 return 1;  
\}

int Leaf(BiTree T)\{  
   
 //求叶子的个数  
   
 int m, n;  
   
 if(T == NULL)\{  
  return 0;  
 \}  
 else  
 if(T->lchild == NULL && T->rchild == NULL)\{  
    
  return 1;  
 \}  
 else\{  
  m = Leaf(T->lchild);  
    
  n = Leaf(T->rchild);  
    
  return m+n;  
 \}  
\}

int Sum(BiTree T)\{  
   
 if(T == NULL)\{  
  return 0;  
 \}  
 else  
 if(T->rchild == NULL && T->lchild == NULL)\{  
    
     return T->data - '0';  
 \}  
 else\{  
  return Sum(T->lchild) + Sum(T->rchild);  
 \}  
\}

int Sum1(BiTree T)\{  
   
 if(T)\{  
  da = da + T->data - '0';  
    
  Sum1(T->lchild);  
    
  Sum1(T->rchild);  
 \}  
   
 return da;  
\}

int main()\{  
   
 BiTree T;  
   
 CreateBiTree(T);  
   
 printf("先序遍历:\\n");  
   
 Preorder(T);  
   
 printf("\\n");  
   
 printf("先序遍历:\\n");  
   
 Preorder2(T);  
   
 printf("\\n");  
   
 printf("先序遍历:\\n");  
   
 Preorder3(T);  
   
 printf("\\n");  
   
 printf("深度:%d\\n", Height(T));  
   
 printf("叶子数:%d\\n", Leaf(T));  
   
 printf("数据域的合:%d\\n", Sum(T));  
   
 return 0;  
\}