2叉树（Binary Tree）：是每个结点最多有左右两棵子2叉树相连接的树结构。
性质：
- 高度（height）1：根节点在第0层，树中节点层数的最大值，即外部结点层数的最大值。
- 一棵有N个内部节点的2叉树有N+1个外部节点。
图1
关于2叉树的高度，维基百科2中说的深度，根节点的深度为1。深度为k的2叉树，最多有2k-1个结点。具体以自己参考书为准。
下面来看看用的比较多的2叉搜索树（图1）
2叉搜索树（Binary Search Tree）3:也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的2叉树：
- 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点（no duplicate nodes）。
树的遍历（见图1）：
- 前序（preorder）：我们访问该结点，然后访问该结点的左子树和右子树。10、6、4、3、5、8、7、9、12、11、13
//递归前序遍历，中序和后序只需将PRINT（）函数放到中间和后面即可 PRE-TRAVERSE(p_node) IF p_node!=NIL THEN PRINT(p_node) PRE-TRAVERSE(p_node_L_child) PRE-TRAVERSE(p_node_R_child)
- 中序（inorder）：我们访问该结点的左子树，然后访问该结点，最后访问右子树。3、4、5、6、7、8、9、10、11、12、13（结果为递增哦）
//非递归中序,前序和后序将压入tmp_node的顺序换下即可NONREC-INTRAVERSE(p_node) STACK-PUSH(p_node) WHILE STACK!=NIL p_node <- STACK-POP() IF p_node是树不是数据项 将p_node结点数据项赋值给tmp_node STACK-PUSH(p_node_R_child) STACK-PUSH(tmp_node) STACK-PUSH(p_node_L_child) ELSE PRINT(p_node)
- 后序（postorder）：我们访问该结点的左子树和右子树，然后访问该节点。3、5、4、7、9、8、6、11、13、12、10
- 层序（level-order）:从上到下，从左到右的遍历树的结点。10、6、12、4、8、11、13、3、5、7、9
//层次遍历LEVEL-TRAVERSE(p_node) QUEUE-IN(p_node) WHILE QUEUE != NIL p_node <- QUEUE-OUT() PRINT(p_node) QUEUE-IN(p_node_L_child) QUEUE-IN(p_node_R_child)
CODE：
1 #include2 #include 3 #define N 15 4 int const *p; /*指向数组s[]的指针*/ 5 /************************************************* 6 **树的定义、初始化、插入节点 7 **前序递归遍历树(中序、后序) 8 **叶子数、深度、每层结点数 9 **version:1.0 10 *************************************************/ 11 /*树的结点*/ 12 typedef struct node 13 { 14 int item; 15 struct node *l,*r; 16 }tree_node; 17 typedef struct 18 { 19 tree_node tn[N]; 20 int cur; 21 }m_arr_tree; 22 /*初始化树*/ 23 void treeInit(m_arr_tree **mat) 24 { 25 *mat=(m_arr_tree *)calloc(1,sizeof(m_arr_tree)); 26 (*mat)->cur=0; 27 } 28 /*储存树*/ 29 tree_node * treePush(m_arr_tree *mat,int item) 30 { 31 mat->tn[mat->cur].item=item; 32 return mat->tn+mat->cur++; /*返回该节点的地址，并使数组下标加1*/ 33 } 34 /*前序插入树的节点*/ 35 tree_node *treePreInsert(m_arr_tree *mat) 36 { 37 tree_node *node=NULL; 38 if(*p==0) 39 ++p; 40 else 41 { 42 node=treePush(mat,*p++); 43 node->l=treePreInsert(mat); 44 node->r=treePreInsert(mat); 45 } 46 return node; 47 } 48 /*打印树*/ 49 void printNode(int c,int width) 50 { 51 while(width-->0) 52 printf("#"); 53 printf("%d\n",c); 54 55 } 56 /*递归前序遍历，中序和后序只需将打印函数放到中间和后面*/ 57 void preTraverse(tree_node *node,int width) 58 { 59 if(node==NULL) 60 { 61 printNode(0,width); /* 打印叶子节点是左右孩子都是0 */ 62 return; 63 } 64 printNode(node->item,width); 65 preTraverse(node->l,width+1); 66 preTraverse(node->r,width+1); 67 } 68 /*树的叶子个数*/ 69 int treeLeaves(tree_node * node) 70 { 71 if(node==NULL) 72 return 0; 73 if(node->l==NULL && node->r==NULL) 74 return 1; 75 int l_count=treeLeaves(node->l); 76 int r_count=treeLeaves(node->r); 77 return l_count+r_count; 78 } 79 /*树的深度*/ 80 int treeDepth(tree_node * node) 81 { 82 if(node==NULL) 83 return 0; 84 int l_depth=treeDepth(node->l); 85 int r_depth=treeDepth(node->r); 86 if(l_depth>r_depth) 87 return l_depth+1; 88 else 89 return r_depth+1; 90 91 } 92 /*树的每层结点个数*/ 93 void treeLevelNode(tree_node *node,int lev,int lev_num[]) 94 { 95 if(node==NULL) 96 return; 97 lev_num[lev]++; 98 treeLevelNode(node->l,lev+1,lev_num); 99 treeLevelNode(node->r,lev+1,lev_num);100 }101 /*************************************************102 **队列的定义、初始化、入队列、出队列、判断为空103 **层次遍历104 **version:1.0105 *************************************************/106 /*定义队列*/107 typedef struct 108 {109 tree_node * que[N]; /*存放树结点的指针*/110 int front,tail;111 }m_queue;112 /*初始化队列*/113 void queueInit(m_queue **mq)114 {115 *mq=(m_queue *)malloc(sizeof(m_queue));116 (*mq)->front=0;(*mq)->tail=0;117 }118 /*入队列*/119 void queueIn(m_queue *mq,tree_node *node)120 {121 mq->tail=(mq->tail+1)%N;122 mq->que[mq->tail]=node;123 }124 /*出队列*/125 tree_node* queueOut(m_queue *mq)126 {127 mq->front=(mq->front+1)%N;128 return mq->que[mq->front];129 }130 /*队列是否为空*/131 int queueEmpty(m_queue *mq)132 {133 if(mq->front == mq->tail)134 return 1;135 return 0;136 }137 /*利用队列层次遍历*/138 void levelTraverse(tree_node *node)139 {140 m_queue * mq; /*声明队列*/141 queueInit(&mq);queueIn(mq,node); /*初始化和向队列放入根结点*/142 int node_count=0,node_level_num=2; /*深度为k，满足2^k-1个结点时，换行*/143 while(!queueEmpty(mq))144 {145 node=queueOut(mq);146 printf("%d ",node->item); ++node_count;147 if(node_count >= node_level_num-1)148 {149 putchar('\n');150 node_level_num<<=1;151 }152 if(node->l)queueIn(mq,node->l); /*压入弹出结点的左右孩子*/153 if(node->r)queueIn(mq,node->r);154 }155 putchar('\n');156 free(mq);157 }158 159 /*************************************************160 **栈的定义、初始化、压栈、弹栈、判断为空161 **非递归中序遍历（前序、后序）162 **version:1.0163 *************************************************/164 /*定义栈*/165 typedef struct166 {167 tree_node * sta[N];168 int cur;169 }m_stack;170 /*初始化*/171 void stackInit(m_stack **ms)172 {173 *ms=(m_stack *)malloc(sizeof(m_stack));174 (*ms)->cur=0;175 }176 /*压栈*/177 void stackPush(m_stack * ms,tree_node * node)178 {179 ms->sta[ms->cur++]=node;180 }181 /*弹出栈*/182 tree_node *stackPop(m_stack *ms)183 {184 return ms->sta[--ms->cur];185 }186 /*判断为空*/187 int stackEmpty(m_stack *ms)188 {189 if(ms->cur==0)190 return 1;191 return 0;192 }193 /*非递归中序遍历栈，弹出元素为数据项，访问它；为一棵树，按希望的顺序压栈*/194 void nonRecInTraverse(tree_node *node)195 {196 m_arr_tree *tmp_mat; /*存放弹出的数据项*/197 treeInit(&tmp_mat);198 199 m_stack *ms; /*按希望的顺序保存数据项的栈*/200 stackInit(&ms);201 stackPush(ms,node);202 while(!stackEmpty(ms))203 {204 node=stackPop(ms); 205 if(node->l || node->r) /*是树继续压栈，否则打印该数据项*/206 {207 tree_node *new_node=treePush(tmp_mat,node->item); 208 if(node->r)stackPush(ms,node->r);209 stackPush(ms,new_node);210 if(node->l)stackPush(ms,node->l);211 }212 else213 printf("%d ",node->item);214 }215 putchar('\n');216 free(tmp_mat);217 free(ms);218 }219 220 int main()221 {222 /*0代表外部结点*/223 int s[]={ 10,6,4,3,0,0,5,0,0,8,7,0,0,9,0,0,12,11,0,0,13,0,0};224 p=s; /*将全局指针指向数组s，方便前序初始化树*/225 m_arr_tree *head;226 treeInit(&head);227 treePreInsert(head);228 // preTraverse(head->tn,0); /*递归前序遍历*/229 // levelTraverse(head->tn); /*层次遍历*/230 // nonRecInTraverse(head->tn); /*非递归中序遍历*/231 // printf("\nnumber of leaves:%d\n",treeLeaves(head->tn)); /*叶子结点数*/232 int d=treeDepth(head->tn); /*树的深度*/233 printf("\n depth of tree : %d\n",d);234 int lev_num[N]={ 0}; /*每层的节点数*/235 treeLevelNode(head->tn,0,lev_num);236 while(--d>=0) /*打印每层节点数*/237 printf(" The %d level number of node :%d\n",d,lev_num[d]);238 free(head);239 return 0;240 }
参考资料：
- Robert Sedgewick，《算法：C语言实现》，中文版
- http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91
- http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9
- http://www.zdyi.com/blog/binary-tree/792
转载请注明：作者：Timothy_T地址：http://www.cnblogs.com/jhooon