2.3二叉树的存储方式
2.3.1 二叉树的顺序存储
因为无法保存当前二叉树是一个满二叉树或者完全二叉树，所以，顺序存储时，需要将不存在的结点预留位置，这样做就会浪费空间，所以一般不使用顺序存储
2.3.2 二叉树的链式存储
二叉树使用链式存储时，每一个结点需要定义一个结构体，里面至少有三个成员，分别是一个数据域和两个指针域组成，数据域保存数据，指针域分别保存左右子树的地址。
typedef int DataType; typedef struct node //定义二叉树的结点结构体 { DataType data; struct node *left; //指向左孩子的指针 struct node *right; //指向右孩子的指针 }bitree_t;
2.4 二叉树的遍历
2.4.1 二叉树的遍历：
先序遍历:先访问树根，再访问左子树，最后访问右子树 （根左右）
中序遍历：先访问左子树，再访问树根，最后访问右子树（左根右）
后序遍历:先访问左子树，再访问右子树，最后访问树根（左右根）
反推：中序必须有，先序或者后序有一个就可以
2.4.2 代码
#ifndef _TREE_H_ #define _TREE_H_ #include <stdio.h> #include <stdlib.h> typedef int DataType; typedef struct node //定义二叉树的结点结构体 { DataType data; struct node *left; //指向左孩子的指针 struct node *right; //指向右孩子的指针 }bitree_t; //创建一棵二叉树 bitree_t *CreateTree(DataType *a,int length); //先序遍历 void PreOrder(bitree_t *root); //中序遍历 void MidOrder(bitree_t *root); //后序遍历 void PostOrder(bitree_t *root); #endif
#include "tree.h" //创建一棵二叉树 bitree_t *CreateTree(DataType *a,int length) { bitree_t *array[11] ={0}; int i; for(i = 0; i < length;i++) { array[i] = (bitree_t *)malloc(sizeof(bitree_t)); if(NULL == array[i]) { return NULL; } array[i]->data = a[i]; array[i]->left = NULL; array[i]->right = NULL; } for(i = 0 ; i < length /2;i++) { array[i]->left = array[2*i + 1]; array[i]->right = array[2*i + 2]; } return array[0]; } //先序遍历 void PreOrder(bitree_t *root) { if(NULL == root) { return; } printf("%d ",root->data); PreOrder(root->left); PreOrder(root->right); } //中序遍历 void MidOrder(bitree_t *root) { if(NULL == root) { return; } MidOrder(root->left); printf("%d ",root->data); MidOrder(root->right); } //后序遍历 void PostOrder(bitree_t *root) { if(NULL == root) { return; } PostOrder(root->left); PostOrder(root->right); printf("%d ",root->data); }
#include "tree.h" int main(int argc, char const *argv[]) { DataType array[10] ={1,2,3,4,5,6,7,8,9,10}; bitree_t *root1 = CreateTree(array,sizeof(array)/sizeof(array[0])); PreOrder(root1); putchar(10); MidOrder(root1); putchar(10); PostOrder(root1); putchar(10); return 0; }
2.5 二叉搜索树
定义：二叉查找树，又被称为二叉搜索树，其特点，左孩子比父节点小，右孩子比父节点大。
//二叉搜索树 bitree_t* CreateBSTree(bitree_t *root,DataType num) { if(NULL == root) { root = (bitree_t *)malloc(sizeof(bitree_t) * 1); if(NULL == root) { return NULL; } root->data = num; root->left = NULL; root->right = NULL; } else { if(root->data > num) { root->left = CreateBSTree(root->left,num); } else { root->right = CreateBSTree(root->right,num); } } return root; }
