一、定义
二叉树在图论中是这样定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。
二、基本概念
二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——如图(a)；
(3)只有左子树——如图(c)；
(4)只有右子树——如图(d)；
(5)完全二叉树——如图(e)。
三、类型
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。[2]
四、相关术语
树的结点：包含一个数据元素及若干指向子树的分支；
孩子结点：结点的子树的根称为该结点的孩子；
双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；
兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；
祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙
结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；
树的深度：树中最大的结点层
结点的度：结点子树的个数
树的度： 树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点；
分枝结点：度不为0的结点；
有序树：子树有序的树，如：家族树；
五、代码实现
1 1 // main.c 2 2 3 3 // C语言-二叉树 4 4 5 5 // 6 6 7 7 // Created by rimi on 2017/5/24. 8 8 9 9 // Copyright © 2017年 rimi. All rights reserved. 10 11 15 #include <stdio.h> 12 16 13 17 #include <stdlib.h> 14 23 struct TreeNode { 15 24 16 25 char data; 17 26 18 27 struct TreeNode * left; 19 28 20 29 struct TreeNode * right; 21 30 22 31 }; 23 35 // 创建树 24 36 25 37 struct TreeNode * createTree(); 26 38 27 39 // 先序遍历 28 40 29 41 void preTraverse(struct TreeNode * root); 30 42 31 43 // 中序遍历 32 44 33 45 void centerTraverse(struct TreeNode * root); 34 46 35 47 // 后序遍历 36 48 37 49 void backTraverse(struct TreeNode * root); 38 53 int main(int argc, const char * argv[]) { 39 54 40 55 // preTraverse(createTree()); 41 56 42 57 centerTraverse(createTree()); 43 58 44 59 // backTraverse(createTree()); 45 60 46 61 return 0; 47 62 48 63 } 49 64 50 65 // 创建树 51 66 52 67 struct TreeNode * createTree(){ 53 71 struct TreeNode * pa = (struct TreeNode *)malloc(sizeof(struct TreeNode)); 54 72 55 73 struct TreeNode * pb = (struct TreeNode *)malloc(sizeof(struct TreeNode)); 56 74 57 75 struct TreeNode * pc = (struct TreeNode *)malloc(sizeof(struct TreeNode)); 58 76 59 77 struct TreeNode * pd = (struct TreeNode *)malloc(sizeof(struct TreeNode)); 60 78 61 79 struct TreeNode * pe = (struct TreeNode *)malloc(sizeof(struct TreeNode)); 62 80 63 81 struct TreeNode * pf = (struct TreeNode *)malloc(sizeof(struct TreeNode)); 64 82 65 83 struct TreeNode * pg = (struct TreeNode *)malloc(sizeof(struct TreeNode)); 66 84 67 85 pa->data = 'A'; 68 86 69 87 pb->data = 'B'; 70 88 71 89 pc->data = 'C'; 72 90 73 91 pd->data = 'D'; 74 92 75 93 pe->data = 'E'; 76 94 77 95 pf->data = 'F'; 78 96 79 97 pg->data = 'G'; 80 98 81 99 82 100 83 101 pa->left = pb; 84 103 pa->right = pc; 85 86 107 pb->left = pd; 87 109 pb->right = NULL; 88 89 90 113 pc->left = pe; 91 115 pc->right = pf; 92 93 119 pd->left = NULL; 94 120 95 121 pd->right = pg; 96 97 125 pe->left = NULL; 98 126 99 127 pe->right = NULL; 100 101 131 pf->left = NULL; 102 132 103 133 pf->right = NULL; 104 105 137 pg->left = NULL; 106 138 107 139 pg->right = NULL; 108 143 return pa; 109 144 110 145 } 111 146 112 147 // 先序遍历 113 148 114 149 void preTraverse(struct TreeNode * root){ 115 150 116 151 if (root != NULL) { 117 152 118 153 printf("%c ", root->data); 119 154 120 155 preTraverse(root->left); 121 156 122 157 preTraverse(root->right); 123 158 124 159 } 125 160 126 161 } 127 162 128 163 // 中序遍历 129 164 130 165 void centerTraverse(struct TreeNode * root){ 131 166 132 167 if(root !=NULL) { 133 168 134 169 centerTraverse(root ->left); 135 173 printf("%c ",root ->data); 136 174 137 177 centerTraverse(root->right); 138 178 139 183 } 140 184 141 185 } 142 187 // 后序遍历 143 188 144 189 void backTraverse(struct TreeNode * root){ 145 190 146 191 if(root !=NULL){ 147 192 148 193 backTraverse(root ->left); 149 194 150 195 backTraverse(root ->right); 151 196 152 197 printf("%c ",root ->data); 153 198 154 199 } 155 203 }