在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
树是由一个或多个结点组成的有限集合，其中：
⒈必有一个特定的称为根(ROOT)的结点；
⒉剩下的结点被分成n>=0个互不相交的集合T1、T2、......Tn，而且，这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。
树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树
1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度。树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
2.树的深度——组成该树各结点的最大层次。
3.还有树的节点，根节点，左子树，右子树。
数的组成：由数据存储 左子树 右子树组成。
typedef struct Tree
{
data_t data;
struct Tree* ltree;
struct Tree* rtree;
}Tree;
对数的操作有对树的遍历，如对树进行先序遍历，中序遍历，后序遍历。
#ifndef _TREE_H_ #define _TREE_H_
typedef int data_t; //树的封装 typedef struct Tree { data_t data; //存储的数据 struct Tree* ltree; //左子树 struct Tree* rtree; //右子树 }Tree;
typedef enum TREE_OP { TREE_ERR=-1, TREE_OK }TREE_OP_ENUM;
//创建树节点 Tree* CreateTreeNode(data_t tdata); //创建一颗树 Tree* CreateTree(data_t *data,int size); //销毁一颗树 void DestroyTree(Tree* ptree); //先序遍历二叉树 void PreOrder(Tree* ptree); //中序遍历二叉树 void InOrder(Tree* ptree); void PostOrder(Tree* ptree);
#endif /* _TREE_H_ */ |
#include<stdio.h> #include<stdlib.h> #include<string.h> #include"tree.h"
Tree* CreateTreeNode(data_t tdata) { Tree* pNode =(Tree*)malloc(sizeof(Tree)); if ( NULL != pNode ) { memset(pNode,0,sizeof(Tree)); } pNode->data = tdata; return pNode; }
Tree* CreateTree(data_t *data,int size) { if (( NULL == data )||(size <=0)) { printf("parameter err\n"); return NULL; } Tree* proot=CreateTreeNode(data[0]); int i=1; for ( ; i <size; i++ ) { Tree* pNode=CreateTreeNode(data[i]); Tree* prootTmp=proot; while ( 1 ) { if ( pNode->data > prootTmp->data) { if ( NULL == prootTmp->rtree) { prootTmp->rtree = pNode; break; } else { prootTmp= prootTmp->rtree; } } else { if ( NULL == prootTmp->ltree) { prootTmp->ltree=pNode; break; } else { prootTmp=prootTmp->ltree; } } } } return proot; }
void DestroyTree(Tree* ptree) { if ( NULL == ptree ) { return; } DestroyTree(ptree->ltree); DestroyTree(ptree->rtree); free(ptree); ptree=NULL; }
void PreOrder(Tree* ptree) { if ( NULL == ptree ) { return; } printf("%d ",ptree->data); PreOrder(ptree->ltree); PreOrder(ptree->rtree); }
void InOrder(Tree* ptree) { if ( NULL == ptree ) { return; }
InOrder(ptree->ltree); printf("%d ",ptree->data); InOrder(ptree->rtree); } void PostOrder(Tree* ptree) { if ( NULL == ptree ) { return; }
PostOrder(ptree->ltree); PostOrder(ptree->rtree); printf("%d ",ptree->data); } |
#include<stdio.h> #include"tree.h"
int main() { data_t arr[5]={120,2,100,88,93}; Tree* ptree=CreateTree(arr, 5); PreOrder(ptree); printf("\n"); InOrder(ptree); printf("\n"); PostOrder(ptree); printf("\n"); DestroyTree(ptree); ptree = NULL; return 0; } |