二叉樹（tree）

目錄

一、二叉樹的周遊

二、二叉樹程式

1.建立結構體

2.插入結點

 2.找到某個結點，并傳回結點中的資料

3.左偏 周遊輸出

4.平衡二叉樹

5.周遊

1）先序周遊

2）中序周遊

3）後序周遊

4）按層周遊

6.删除結點

一、二叉樹的周遊

1.先序周遊        （根結點---左結點---右結點）

        A-B-D-E-G-C-F-F-I

2.中序周遊        （左節點---根結點---右節點）

        D-B-G-E-A-C-H-F-I

3.後續周遊        （左結點---右節點---根結點）

        D-G-E-B-H-I-F-C-A

二、二叉樹程式

1.建立結構體

struct score_st
{
	int id;
	char name[NAMESIZE];
	int math;
};
struct node_st
{
	struct score_st data;
	struct node_st *l,*r;
};
           

2.插入結點

int insert(struct node_st **root, struct score_st *data)
{
	struct node_st *node;

	if(*root == NULL)     //當root指向的指針為空
	{
		node = malloc(sizeof(*node));    //建立一個結點
		if(node == NULL)
			return -1;
		node->data = *data;            //将要插入的資料指派給node
		node->l = node->r = NULL;       //結點的做指針和右指針設為NULL
		*root = node;                  //将結點的位址儲存到root指向的指針中
		return 0;
	}

	if(data->id <=  (*root)->data.id)    //當樹不為空時，比較id的值，id小的在樹的左側
		return insert(&(*root)->l,data);
	return insert(&(*root)->r,data);    //id大的在樹的右側
}
           

 2.找到某個結點，并傳回結點中的資料

struct score_st *find(struct node_st *root, int id)
{
	if(root == NULL)    
		return NULL;
	if(root->data.id == id)      //如果要找的id和結點中的id相等，傳回資料
		return &root->data;

	if(id < root->data.id)        //如果要找的id小于結點中的id，再遞歸調用找左結點
		return find(root->l,id);
	return find(root->r,id);        //如果要找的id大于結點中的id，再遞歸調用找右結點
}
           

3.左偏 周遊輸出

static void draw_(struct node_st *root,int level)
{
    int i;
    if(root == NULL)    //root為NULL直接結束函數
        return ;    
    draw_(root->r,level+1);    //遞歸調用draw，指向右子樹，level+1    
    for(i = 0 ; i < level; i++)    //輸出level個空格
        printf("    ");
    print_s(&root->data);
    draw_(root->l,level+1);    遞歸調用draw，指向左子樹，level+1

}
void draw(struct node_st *root)
{
    draw_(root,0);

}
           

4.平衡二叉樹

static int get_num(struct node_st *root)    //傳回樹的結點個數
{
	if(root == NULL)
		return 0;
	return get_num(root->l) + 1 + get_num(root->r);//遞歸調用傳回結點個數
}
static struct node_st *find_min(struct node_st *root)
{
	if(root->l == NULL)   //如果root的左結點為NULL，将root傳回
		return root;        
	return find_min(root->l);    //遞歸調用查找左結點，當左結點為NULL，将這個結點傳回
}

static void turn_left(struct node_st **root)
{
	struct node_st *cur = *root;    //定義一個指針，指向*root指向的位置
	*root = cur->r;    //*root指向cur的右結點
	cur->r = NULL;       //cur的右結點指派為NULL
	find_min(*root)->l = cur;    //找到最小的結點，将cur插入到最小結點的左結點

//	draw(tree);
}

static struct node_st *find_max(struct node_st *root)
{
	if(root->r == NULL)    //如果root的左結點為NULL，将root傳回
		return root;
	return find_max(root->r);    //遞歸調用查找右結點，當右結點為NULL，将這個結點傳回
}  

static void turn_right(struct node_st **root)
{
	struct node_st *cur = *root;    //定義一個指針，指向*root指向的位置

	*root = cur->l;    //*root指向cur的左結點
	cur->l = NULL;    //cur的左結點指派為NULL
	find_max(*root)->r = cur;    //找到最大的結點，将cur插入到最大結點的右結點

//	draw(tree);
}

void balance(struct node_st **root)
{
	int sub;
	if(*root == NULL)
		return ;
	while(1)
	{
		sub = get_num((*root)->l) - get_num((*root)->r);    //得到根結點左子樹和右子樹的結點內插補點
		if(sub >= -1 && sub <= 1)    //兩邊的結點數內插補點如果是-1 0 1時結束循環
			break;
		if(sub < -1)                //如果內插補點小于-1，向左旋
			turn_left(root);
		else                        //如果內插補點大于1，向右旋
			turn_right(root);
	}

	balance(&(*root)->l);        //遞歸調用，平衡左子樹
	balance(&(*root)->r);        //遞歸調用，平衡右子樹

}
           

5.周遊

1）先序周遊

void travel(struct node_st *root) 
{
    if(root == NULL)
        return ;
    print_s(&root->data);
    travel(root->l);
    travel(root->r);
    
}
           

2）中序周遊

void travel(struct node_st *root) 
{
    if(root == NULL)
        return ;
    travel(root->l);
    print_s(&root->data);
    travel(root->r);
    
}
           

3）後序周遊

void travel(struct node_st *root) 
{
    if(root == NULL)
        return ;
    travel(root->l);
    travel(root->r);
    print_s(&root->data);
}
           

4）按層周遊

void travel(struct node_st *root)
{   
    QUEUE *qu;    
    struct node_st *cur;
    qu = queue_create(sizeof(struct node_st *));    //建立隊列
    queue_en(qu, &root);        //根結點入隊
    while(1)
    {   
        if(queue_de(qu, &cur) != 0)    //如果删除回顯不成功，則結束循環
            break;
        print_s(&cur->data);        //輸出回顯指針指向的資料
        if(cur->l != NULL)            //指針左結點不為NULL，則入隊
            queue_en(qu,&cur->l);    
        if(cur->r != NULL)            //指針右結點不為NULL，則入隊
            queue_en(qu,&cur->r);
    }   
    queue_destroy(qu);
}
           

6.删除結點

void delete(struct node_st **root, int id)
{
	struct node_st **node = root;
	struct node_st *cur;

	while( (*node) != NULL &&  (*node)->data.id != id )//查找要删除的結點
	{
		if( id < (*node)->data.id )    //如果想要删除的id小于結點中的id，讓指針指向結點的左結點
			node = &(*node)->l;
		else
			node = &(*node)->r;     //如果想要删除的id小于結點中的id，讓指針指向結點的左結點
	}
	
	if(*node == NULL)    //沒找到直接傳回
		return ;
	
	cur = *node;    

	if(cur->l == NULL)    //如果找到的結點的左子樹為NULL，則直接将*node指向cur的右結點
		*node = cur->r;
	else
	{
		*node = cur->l;    //不為NULL,則直接将*node指向cur的左結點
		find_max(cur->l)->r = cur->r;    //将找到的結點的右子樹插入到*node的右子樹的最後面
	}
	free(cur);

}