二叉树的定义：二叉树是每个结点最多有两个子树的有序树。
下面的代码内容主要包括二叉树的建立，判断二叉树是否为空树，二叉树的先序遍历，中序遍历，后序遍历以及层次遍历，计算总结点个数，叶子节点个数，树的深度。
先序遍历（根左右）：先访问一个节点的根，再访问其左子树，接着右子树，通过递归的方法。
中序遍历（左根右），后序遍历（左右根）的原理与先序相同，只是访问顺序不同。
在数据结构中，想要确定唯一的一棵二叉树，需要一棵树的中序序列以及另外两个序列中的任意一个，所以想要只用一个序列建立出一棵二叉树，就必须要用特殊符号来表示空节点。在下面的代码中，我是通过先序序列建立二叉树，空节点用‘#’表示。
另外在提一句，递归是数据结构乃至编程中非常重要的一种操作方法，下面代码的基本上每一个操作都用上了递归，必须要熟悉掌握。
1 #include<iostream> 2 #include<algorithm> 3 #include<queue> 4 using namespace std; 5 //***************链式二叉树************** 6 7 //结构定义 8 typedef struct BiNode{ 9 char data; 10 struct BiNode *lchild,*rchild; 11 }BiNode, *BiTree; 12 13 //判断二叉树是否为空树 14 int EmptyBT(BiTree T) 15 { 16 if(T == NULL) 17 return 1; 18 return 0; 19 } 20 21 //先序建立二叉树 22 void CreateBT(BiTree &T) 23 { 24 char child; 25 cin>>child; 26 if(child == '#')//无节点 27 T = NULL; 28 else 29 { 30 T = new BiNode; 31 T->data = child; 32 CreateBT(T->lchild);//建立左子节点 33 CreateBT(T->rchild);//建立右子节点 34 } 35 } 36 37 //先序遍历（根左右） 38 void PreOrder(BiTree &T) 39 { 40 if(T == NULL) return; 41 cout<<T->data<<' '; 42 if(T->lchild != NULL) 43 PreOrder(T->lchild); 44 if(T->rchild != NULL) 45 PreOrder(T->rchild); 46 return; 47 } 48 49 //中序遍历（左根右） 50 void InOrder(BiTree &T) 51 { 52 if(T == NULL) return; 53 if(T->lchild != NULL) 54 InOrder(T->lchild); 55 cout<<T->data<<' '; 56 if(T->rchild != NULL) 57 InOrder(T->rchild); 58 return; 59 } 60 61 //后序遍历（左右根） 62 void PostOrder(BiTree &T) 63 { 64 if(T ==NULL) return; 65 if(T->lchild != NULL) 66 PostOrder(T->lchild); 67 if(T->rchild != NULL) 68 PostOrder(T->rchild); 69 cout<<T->data<<' '; 70 return; 71 } 72 73 //层次遍历二叉树 74 void LevelOrder(BiTree &T) 75 { 76 if(T == NULL) return; 77 queue<BiTree> q; 78 BiNode *p = new BiNode; 79 q.push(T); 80 while(!q.empty()) 81 { 82 p = q.front(); 83 q.pop(); 84 cout<<p->data<<' '; 85 if(p->lchild != NULL) 86 q.push(p->lchild); 87 if(p->rchild != NULL) 88 q.push(p->rchild); 89 } 90 } 91 92 //计算总节点个数 93 int NodeCount(BiTree T) 94 { 95 if(T == NULL) 96 return 0; 97 else 98 return NodeCount(T->lchild) + NodeCount(T->rchild) +1; 99 } 100 101 //计算叶子节点个数 102 int LeafCount(BiTree T) 103 { 104 if(T == NULL) 105 return 0; 106 if(T->lchild==NULL && T->rchild==NULL) 107 return 1; 108 return LeafCount(T->lchild) + LeafCount(T->rchild); 109 } 110 111 //计算二叉树的深度 112 int DepthBT(BiTree T) 113 { 114 if(T == NULL) 115 return 0; 116 if(T->lchild==NULL && T->rchild==NULL) 117 return 1; 118 return max(DepthBT(T->lchild)+1 , DepthBT(T->rchild)+1); 119 } 120 121 //查找二叉树元素 122 int FindBT(BiTree &T,char e) 123 { 124 if(T == NULL) 125 return 0; 126 else if(T->data == e) 127 return 1; 128 else if(FindBT(T->lchild,e) || FindBT(T->rchild,e)) 129 return 1; 130 else return 0; 131 } 132 133 //清除二叉树 134 void ClearBT(BiTree &T) 135 { 136 if(T == NULL) 137 return; 138 ClearBT(T->lchild); 139 ClearBT(T->rchild); 140 delete T; 141 } 142 143 int main() 144 { 145 BiTree T; 146 147 cout<<"请输入二叉树的先序序列，空用‘#’表示："; 148 CreateBT(T); 149 150 if(EmptyBT(T)) 151 cout<<"二叉树为空树"<<endl; 152 else 153 { 154 //cout<<"二叉树不为空"<<endl; 155 156 cout<<"先序序列为："; 157 PreOrder(T); 158 cout<<endl; 159 160 cout<<"中序序列为："; 161 InOrder(T); 162 cout<<endl; 163 164 cout<<"后序序列为："; 165 PostOrder(T); 166 cout<<endl; 167 168 cout<<"层次遍历序列为："; 169 LevelOrder(T); 170 cout<<endl; 171 172 cout<<"二叉树总节点个数为："<<NodeCount(T)<<endl; 173 cout<<"二叉树叶子节点个数为："<<LeafCount(T)<<endl; 174 cout<<"二叉树的深度为："<<DepthBT(T)<<endl; 175 176 char a; 177 cout<<"请输入要查找的元素："; 178 cin>>a; 179 if(FindBT(T,a)) 180 cout<<"存在元素"<<a<<endl; 181 else 182 cout<<"不存在元素"<<a<<endl; 183 } 184 ClearBT(T); 185 return 0; 186 }
毕竟这是为了完成数据结构实验所写的代码，所以写的比较简单，有很多细节情况没有考虑进去，以后有时间会写写更复杂的来练手。