首页 > 代码库 > 二叉树建立和遍历

二叉树建立和遍历

二叉树创建遍历规则:

1.先序:根-左-右

2.中序:左-根-右

3.后序:左-右-根


二叉树定义和辅助函数如下:

struct node {  
    int data;  
    struct node* left;  
    struct node* right;  
};  
  
void visit(int data)  
{  
    printf("%d ", data);  
}  

int indata()
{
    int data;
    scanf("%d",&data);
    return data;
}




先序创建二叉树:

struct node* CreateBiTree()//先序建立一个二叉树  
{   
    char x; //x为根节点  
    struct node* t;   
    x=indata();  
    if (x==' ') /* 判断当前子树是否创建完成*/   
        return NULL;   
    else   
    {   
        t=(struct node*)malloc(sizeof(struct node));   
        t->data=http://www.mamicode.com/x;   >先序遍历二叉树:

void preOrder(struct node* root)  
{  
    if (root == NULL)  
        return;  
    visit(root->data);  
    preOrder(root->left);  
    preOrder(root->right);  
}  



中序创建二叉树:

struct node* CreateBiTree()//先序建立一个二叉树  
{   
    char x; //x为根节点  
    struct node* t;   
    x=indata();  
    if (x==' ') /* 判断当前子树是否创建完成*/   
        return NULL;   
    else   
    {  
        t=(struct node*)malloc(sizeof(struct node)); 
        t->left=CreateBiTree();  
        t->data=http://www.mamicode.com/x;     >中序遍历二叉树:

void inOrder(struct node* root)  
{  
    if (root == NULL)  
        return;  
    inOrder(root->left);  
    visit(root->data);  
    inOrder(root->right);  
}  




后序创建二叉树

struct node* CreateBiTree()//先序建立一个二叉树  
{   
    char x; //x为根节点  
    struct node* t;   
    x=indata();  
    if (x==' ') /* 判断当前子树是否创建完成*/   
        return NULL;   
    else   
    {  
        t=(struct node*)malloc(sizeof(struct node)); 
        t->left=CreateBiTree();    
        t->right=CreateBiTree();   
    	t->data=http://www.mamicode.com/x;   >后序遍历二叉树

void inOrder(struct node* root)  
{  
    if (root == NULL)  
        return;  
    inOrder(root->left);   
    inOrder(root->right);  
    visit(root->data); 
}  



转载请注明作者:小刘