C语言二叉树常见操作详解【前序语言二叉树常见操作详解【前序,中序中序,后序后序,层次遍历及非递层次遍历及非递
归查找归查找,统计个数统计个数,比较比较,求深度】求深度】
本文实例讲述了C语言二叉树常见操作。分享给大家供大家参考，具体如下：
一、基本概念一、基本概念
每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。
性质：
1、非空二叉树的第n层上至多有2^(n-1)个元素。
2、深度为h的二叉树至多有2^h-1个结点。
满二叉树：所有终端都在同一层次，且非终端结点的度数为2。
在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。
完全二叉树：除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐，即集中在左面的位置上，不能有空
位置。
对于完全二叉树，设一个结点为i则其父节点为i/2，2i为左子节点，2i+1为右子节点。
二、存储结构二、存储结构
顺序存储：顺序存储：
将数据结构存在一块固定的数组中。
#define LENGTH 100
typedef char datatype;
typedef struct node{
datatype data;
int lchild,rchild;
int parent;
}Node;
Node tree[LENGTH];
int length;
int root;
虽然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。
链式存储：链式存储：
typedef char datatype;
typedef struct BinNode{
datatype data;
struct BinNode* lchild;
struct BinNode* rchild;
}BinNode;
typedef BinNode* bintree; //bintree本身是个指向结点的指针
三、二叉树的遍历三、二叉树的遍历
遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
例如：求下面树的三种遍历
资源评论
