服务器之家

服务器之家 > 正文

C语言数据结构二叉树简单应用

时间:2021-05-12 16:05     来源/作者:super_yc

 C语言数据结构二叉树简单应用

在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree),接下来我就在这里给大家介绍一下二叉树在算法中的简单使用:

我们要完成总共有

(1)二叉树的创建

(2)二叉树的先中后序递归遍历

(3)统计叶子结点的总数

(4)求树的高度

(5)反转二叉树

(6)输出每个叶子结点到根节点的路径

(7)输出根结点到每个叶子结点的路径。

定义二叉树结点类型的结构体

?
1
2
3
4
5
6
typedef struct node{
  char data;
  struct node *Lchild;
  struct node *Rchild;
}BiTNode,*BiTree;
int cnt=0;//统计叶子节点个数

二叉树的创建

?
1
2
3
4
5
6
7
8
9
10
11
12
BiTNode *Create(){ //二叉树的先序建立 
  char ch;
  BiTNode *s;
  ch=getchar();
  if(ch=='#')erchashu 
    return NULL;
  s=(BiTNode *)malloc(sizeof(BiTNode));
  s->data=ch;
  s->Lchild=Create();
  s->Rchild=Create();
  return s;
}

二叉树的先序、中序、后序递归遍历

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void PreOrder(BiTree root){   //前序遍历 
  if(root){
    printf("%c ",root->data);
    PreOrder(root->Lchild);
    PreOrder(root->Rchild);
  }
}
 
void InOrder(BiTree root){   //中序遍历 
  if(root){
    InOrder(root->Lchild);
    printf("%c ",root->data);
    InOrder(root->Rchild);
  }
}
 
void PostOrder(BiTree root){    //后序遍历 
  if(root){
    PostOrder(root->Lchild);
    PostOrder(root->Rchild);
    printf("%c ",root->data);
  }
}

统计叶子结点个数:

?
1
2
3
4
5
6
7
8
void LeafCountNode(BiTree root){  //统计叶子结点个数 
  if(root){
    if(!root->Lchild && !root->Rchild)
      cnt++;
    LeafCountNode(root->Lchild);
    LeafCountNode(root->Rchild);
  }

输出各个叶子结点值:

?
1
2
3
4
5
6
7
8
void IInOrder(BiTree root){ //输出各个叶子结点值 
  if(root){
    IInOrder(root->Lchild);
    if(!root->Lchild && !root->Rchild) 
      printf("%c ",root->data);
    IInOrder(root->Rchild);
  }
}

求树的高度:

?
1
2
3
4
5
6
7
8
9
10
11
12
int PostTreeDepth(BiTree root){       //求树的高度 
  int h1,h2,h;
  if(root==NULL){
    return 0;
  }
  else{
    h1=PostTreeDepth(root->Lchild);
    h2=PostTreeDepth(root->Rchild);
    h=(h1>h2?h1:h2)+1;
    return h;
  }
}

反转二叉树:

?
1
2
3
4
5
6
7
8
9
10
11
12
void MirrorTree(BiTree root){        //二叉树镜像树 
  BiTree t;
  if(root==NULL)
    return;
  else{
    t=root->Lchild;
    root->Lchild=root->Rchild;
    root->Rchild=t;
    MirrorTree(root->Lchild);
    MirrorTree(root->Rchild);
  }
}

输出每个叶子结点到根节点的路径:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
void OutPutPath(BiTree root,char path[],int len){      //输出每个叶子结点到根节点的路径 
  if(root){
    if(!root->Lchild && !root->Rchild){
      printf("%c ",root->data);
      for(int i=len-1;i>=0;i--)
        printf("%c ",path[i]);
      printf("\n");  
    }
    path[len]=root->data;
    OutPutPath(root->Lchild,path,len+1);
    OutPutPath(root->Rchild,path,len+1);
  }
}

输出根到每个叶子结点的路径:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void PrintPath(BiTree root,char path[],int l){     //输出根到每个叶子结点的路径
  int len=l-1;
  if(root){
    if(root->Lchild==NULL && root->Rchild==NULL){
      path[len]=root->data;
      for(int i=9;i>=len;i--)
        printf("%c ",path[i]);
      printf("\n");
    }
    path[len]=root->data;
    PrintPath(root->Lchild,path,len);
    PrintPath(root->Rchild,path,len);
  

测试代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main(void){
  int h,len;
  char path[20];
  BiTree root;
  root=Create();
// PreOrder(root);
// printf("\n");
// InOrder(root);
// printf("\n");
// PostOrder(root);
// printf("\n");
// LeafCountNode(root);
// printf("叶子结点个数为:%d\n",cnt);
// IInOrder(root); 
  h=PostTreeDepth(root);
  printf("树的高度为:High=%d\n",h);
// PrintTree(root,0);
// MirrorTree(root); 
// PrintTree(root,0);
// OutPutPath(root,path,0);
// PrintPath(root,path,10); 
  return 0;
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

原文链接:http://blog.csdn.net/super_yc/article/details/71440938

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部