c语言 数据结构 --二叉树


一、二叉树的定义

二叉树:每个节点只由两个节点组成;
二叉树:是一种特殊的树;
二叉树:是链表的一种扩展结构;


struct tree{
数据类型 data; //树中的数据
struct tree *leftTree; //树的左节点
struct tree *rightTree; //树的右节点
}T,*TAdd;


二、二叉树遍历

二叉树的遍历是采用递归的方式获取所有节点的信息,依次展示出来
2.1 先序遍历: 先访问中节点 再访问 左节点 再访问 右节点
void v(TAdd t){
show(t->data);//访问数据
v(t->leftTree);//访问左节点
v(t->rightTree);//访问右节点
}

2.2 中序遍历 先访问左节点 再访问中节点 再访问右节点
void v(TAdd t){
v(t->leftTree);
show(t->data);
v(t->rightTree);
}

2.3 后序遍历 先访问左节点 再访问右节点 再访问中节点
void v(TAdd t){
v(t->leftTree);
v(t->rightTree);
show(t->data);
}


三、二叉树创建

void createTree(TAdd t)
{
char c;
scanf(“%c”,&c);
if(c !=’ ‘)
{
t = (TAdd)malloc(sizeof(T));
createTree(t->leftTree);
createTree(t->rightTree);
}else
{
t =NULL;
}
}


四、二叉树的举例说明

#include "stdio.h"
#include "stdlib.h"
typedef struct Tree{
    char data;
    struct Tree *leftTree;
    struct Tree *rightTree;
}T,*TAdd;

void createTree(TAdd t,char *info){
   char c;
   printf("%s\n",info);
   scanf("%c",&c);
   if(c !='@' && c!=10){ // !=10 过滤macos 下的回车键
      if(t==NULL)
      t = (TAdd) malloc(sizeof(T));
      t->leftTree =(TAdd)malloc(sizeof(T));//生成左树空间 
      t->rightTree=(TAdd)malloc(sizeof(T));//生成右树空间  
    
      t->data =c;
      createTree(t->leftTree,"左节点");
      createTree(t->rightTree,"右节点");
    }else
   {
      t =NULL;
   }
}


void show(char c,int i){
   printf("%c\n  层数: %d \n",c,i);
}

void v(TAdd t,int i){
     if(t){
        show(t->data,i);
        v(t->leftTree,i+1);
        v(t->rightTree,i+1);
     }
}


int main(){
  T t;
  int i=0;
  createTree(&t,"主节点");
  v(&t,i);
  return 1;
}