数据结构--第六天

--树

-树的基本概念

树结构通常用来储存逻辑关系为“一对多”的数据，例如：

上图的这些元素具有的就是 "一对多" 的逻辑关系，例如元素A同时和B、C、D有关系，元素D同时和A、H、I、J有关系等。观察这些元素之间的逻辑关系会发现，它们整体上像一棵倒着的树，这也是将存储这些元素的结构起名为“树”的原因

tips：树型结构可以保证数据的插入、删除、修改的速度

-树的定义

1. 树是由节点和边构成

2. 树中除根节点，每一个节点都只有一个父节点，但是可以有多个子节点

3. 根节点没有父节点

-树中的专业术语

节点：树结构存储的各个元素称为节点，例如：父节点，子节点，叶子节点

节点的度：一个节点拥有子树的个数，就称为该节点的度

叶子节点：没有子节点的节点，称为叶子节点

边：一个节点到另一个节点的距离

树的深度：树中结点的层数，根节点默认为第一层

有序树：如果一棵树中各个节点左子树和右子树的位置不能交换，那么这棵树就称为有序树

无序树：如果一棵树中各个节点左子树和右子树的位置可以交换，那么这棵树就称为无序树

空树：指没有任何节点的树，连根节点都没有

-树的分类

一般树：任意节点的子节点的个数不受限制，则称为一般树

二叉树：任意一个节点的子节点个数最多是2个

森林：由多个树共同组成一片森林

-二叉树的特性

1.二叉树和链表一样，也是动态数据结构

其结构体格式:

struct Node{

datatype_t data;

struct Node* left;

struct Node* right;

}

2.二叉树具有唯一的根节点

3.二叉树具有天然的递归结构（每个节点的左、右子树也是二叉树）

满二叉树

1>叶子节点出现在二叉树的最底层，除叶子节点之外的其他节点都有俩个子节点

2>一个层数为k的满二叉树的总节点数为：2^k-1

3>第i层上节点数为：2^(i-1)

4>一个层数为k的满二叉树的叶子节点个数（也就是最后一层）为：2^(k-1)

完全二叉树

概念：按照树的结构从上到下，从左到右依次将元素排列成树的形状

性质：

1>根节点没有父节点

2>除根节点之外的任意节点（i）的父节点的索引为：（i-1）/2

3>任意节点的左子节点的的索引为：2*i+1

4>任意节点的右子节点的的索引为：2*i+2

-二叉树的遍历

二叉树的遍历是指从根结点触发，按照某种次序访问二叉树中所有节点，使得每个节点被访问且仅被访问一次

四种常用遍历思想为：

前序遍历：根节点-->左子树-->右子树

中序遍历：左子树-->根节点-->右子树

后序遍历：左子树-->右子树-->根节点

层次遍历：只需按层次遍历即可

-树示例代码

main.c

#include "tree.h"void menu(){printf("--------------------------------\n");printf("1.create tree\n");printf("2.preorder tree\n");printf("3.midorder tree\n");printf("4.suffixorder tree\n");printf("show complete binary tree array\n");printf("0.exit\n");printf("--------------------------------\n");
}int main(){int select;node_t* root=NULL;do{menu();printf("请选择：");scanf("%d",&select);switch(select){case 1:while(getchar()!='\n');create_tree2(&root);break;case 2:printf("-------------------pre traversal----------------------\n");pre_traversal(root);putchar('\n');break;case 3:printf("-------------------middle traversal----------------------\n");middle_traversal(root);putchar('\n');break;case 4:printf("-------------------suf traversal----------------------\n");suf_traversal(root);putchar('\n');break;case 5:printf("-------------------level traversal----------------------\n");level_traversal(root);putchar('\n');break;case 0:printf("退出成功！\n");free(root);root=NULL;exit(EXIT_FAILURE);}}while(1);return 0;
}

tree.c

#include "tree.h"//创建树的方法
void create_tree2(node_t** p_root){//创建一个节点char c;scanf("%c",&c);if(c=='#'){return; }node_t* p_node=(node_t*)malloc(sizeof(node_t));if(NULL==p_node){printf("malloc failure\n");return;}p_node->data=c;create_tree2(&(p_node->left));create_tree2(&(p_node->right));*p_root=p_node;
}node_t* create_tree(){//创造节点printf("input character:");char c;scanf("%c",&c);if(c=='#'){return NULL;}node_t* p_node=(node_t*)malloc(sizeof(node_t));if(NULL==p_node){printf("malloc failure.\n");return NULL;}p_node->data=c;//创建左子树p_node->left=create_tree();//创建右子树p_node->right=create_tree();return p_node;
}
//前序遍历
void pre_traversal(node_t* root){//递归终止条件if(NULL==root){return;}//递归操作printf("%-3c",root->data);pre_traversal(root->left);pre_traversal(root->right);
}
void middle_traversal(node_t* root){                          //递归终止条件if(NULL==root){                                    return;                                    }//递归操作middle_traversal(root->left);printf("%-3c",root->data);middle_traversal(root->right);                        
}
void suf_traversal(node_t* root){//递归终止条件if(NULL==root){return;}//递归操作suf_traversal(root->left);suf_traversal(root->right);printf("%-3c",root->data);
}void level_traversal(node_t* root){if(NULL==root){return;}//创建队列linkednode_t* queue=NULL;linkedlist_init(&queue);//1.将头节点入队linkedlist_insert_tail(queue,root);while(!linkedlist_is_empty(queue)){//2.出队node_t* node=linkedlist_remove_head(queue);printf("%-3c",node->data);//3.分别判断左右子树是否为空if(node->left!=NULL){linkedlist_insert_tail(queue,node->left);}if(node->right!=NULL){linkedlist_insert_tail(queue,node->right);}}
}

tree.h

#ifndef _HEAD_COMPLETE_BT_H__
#define _HEAD_COMPLETE_BT_H__#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>
#include "linkedlist.h"extern void create_tree2(node_t**);
extern void pre_traversal(node_t*);
extern void middle_traversal(node_t*);
extern void suf_traversal(node_t*);
extern void level_traversal(node_t*);
extern node_t* create_tree();#endif

linkedlist.c

#include "linkedlist.h"void linkedlist_init(linkednode_t** p_head){                                         linkednode_t* p_node = (linkednode_t*)malloc(sizeof(linkednode_t));        if(p_node==NULL){                                        printf("malloc failure:%s\n",strerror(errno));   return;                                    }                                                        memset(p_node,0,sizeof(linkednode_t));                                                              p_node->next = NULL; *p_head = p_node;	
}// 添加的方法
bool linkedlist_insert_tail(linkednode_t* p_head,node_t* data){//将data添加到链表的尾部// 1、封装成节点linkednode_t* p_node = (linkednode_t*)malloc(sizeof(linkednode_t));if(p_node==NULL){printf("malloc failure:%s\n",strerror(errno));return false;}memset(p_node,0,sizeof(linkednode_t));p_node->data = data;p_node->next = NULL;// 1、找到链表的尾部linkednode_t* tail = p_head;while(tail->next!=NULL){tail= tail->next;}// 2、进行挂接tail->next=p_node;return true;
}bool linkedlist_is_empty(linkednode_t* head){return head == NULL || head->next==NULL;
}node_t* linkedlist_remove_head(linkednode_t* head){if(linkedlist_is_empty(head)){return NULL;}else{linkednode_t* delnode = head->next;head->next = head->next->next;return delnode->data;	}
}