二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用作
二叉查找树
和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。
?
二叉树的遍历包括深度优先和宽度优先,深度优先又有前序,中序遍历和后序遍历三种。
对于深度优先遍历,递归遍历方法直观而简洁,如果要使用非递归方法,一般要借用栈结构;
宽度优先则常使用队列来实现。
?
?1?
int?main()
?2?{
?3?????TreeNode<
int>?n1(
10,NULL,NULL);
?4?????TreeNode<
int>?n2(
9,128); line-height:1.5!important”>?5?????TreeNode<
int>?n3(
6,&n1,&n2);
?6?????TreeNode<
int>?n4(
7,128); line-height:1.5!important”>?7?????TreeNode<
int>?n5(
8,128); line-height:1.5!important”>?8?????TreeNode<
int>?n6(
3,&n4,&n5);
?9?????TreeNode<
int>?n7(
1,&n3,&n6);?
10?
11?????n7.PreTraverse();?cout?<<?endl;?
12?????n7.InTraverse();??cout?<<?endl;?
13?????n7.PostTraverse();cout?<<?endl;??
14?
15?????system(
”
pause
“);
16?????
return?
0;
17?}