4.6 树

使用指针和结构体还可以构成另一种嵌入式操作系统常用的数据结构——树。例如，树的定义如下：

typedef struct node *tree_pointer;
struct node{
 char ch;
 tree_pointer left_child,right_child;
};

根节点赋初值语句：

tree_pointer root=NULL;

生成树的函数如下：

tree_pointer create(tree_pointer ptr)
{
     char ch;
    scanf("%c",&ch);
    if(ch==' ')
        ptr=NULL;
    else
    {
        ptr=(tree_pointer)malloc(sizeof(node));
        ptr->ch=ch;
        ptr->left_child=create(ptr->left_child);
        ptr->right_child=create(ptr->right_child);
    }
    return ptr;
}

二叉树是一种特殊的树，每个节点都只有左、右两个分支，连接左、右两个儿子节点。

（1）前序遍历二叉树：一种按照从左儿子节点、该节点到右儿子节点顺序的树节点的访问方式。

void preorder(tree_pointer ptr)
{
 if(ptr){
  printf("%c",ptr->ch);
  preorder(ptr->left_child);
  preorder(ptr->right_child);
 }
}

（2）中序遍历二叉树：一种先查该节点、再查左儿子节点、最后查右儿子节点的访问方式。

void inorder(tree_pointer ptr)
{
 if(ptr){
  inorder(ptr->left_child);
  printf("%c",ptr->ch);
  inorder(ptr->right_child);
 }
}

（3）后序遍历二叉树：一种先查右儿子节点、再查该节点、最后查左儿子节点的访问方式。

void postorder(tree_pointer ptr)
{
 if(ptr){
  postorder(ptr->left_child);
  postorder(ptr->right_child);
  printf("%c",ptr->ch);
 }
}

使用上面的函数构建的一个主程序的例子如下：

void main()
{
 printf("构建一个二叉树：\n");
 root=create(root);
 printf("前序遍历二叉树：\n");
 preorder(root);
 printf("\n");
 printf("中序遍历二叉树：\n");
 inorder(root);
 printf("\n");
 printf("后序遍历二叉树：\n");
 postorder(root);
 printf("\n");
}