上海建设网站公司哪家好,wordpress标签云404错误,公司宣传册设计与制作图片,衡水网站制作多少钱对于三种遍历方式来说#xff0c;均为先左后右#xff01;区别在于根结点的位置顺序
先序遍历#xff1a;根——左——右
中序遍历#xff1a;左——根——右
后序遍历#xff1a;左——右——根
#xff08;所谓先中后的顺序#xff0c;是指根结点D先于子树还是后于…对于三种遍历方式来说均为先左后右区别在于根结点的位置顺序
先序遍历根——左——右
中序遍历左——根——右
后序遍历左——右——根
所谓先中后的顺序是指根结点D先于子树还是后于子树出现 如上图
先序遍历的结果为A B C D E F G H
中序遍历的结果为B D C E A F H G
后序遍历的结果为D E C B H G F A 定义树的结点类型
typedef struct BinaryNode{char ch;struct BinaryNode* lchild;struct BinaryNode* rchild;
}BinaryNode;
根据图例创建二叉树
void CreateBinaryTree()
{//创建结点 BinaryNode node1{A,NULL,NULL};BinaryNode node2{B,NULL,NULL};BinaryNode node3{C,NULL,NULL};BinaryNode node4{D,NULL,NULL};BinaryNode node5{E,NULL,NULL};BinaryNode node6{F,NULL,NULL};BinaryNode node7{G,NULL,NULL};BinaryNode node8{H,NULL,NULL};//创建结点关系node1.lchildnode2;node1.rchildnode6;node2.rchildnode3;node3.lchildnode4;node3.rchildnode5;node6.rchildnode7;node7.lchildnode8;
}
递归实现先序遍历
void RecursionFirst(BinaryNode* root)
{ if(rootNULL)//遍历到空结点return;cout(root-ch) ; //输出根结点RecursionFirst(root-lchild);//要点虽然一左一右看似连在一起其实是将首个根结点的左子树全部遍历完毕才会去遍历右子树 RecursionFirst(root-rchild);//先序遍历的顺序为根-左-右
}递归实现中序遍历
void RecursionMiddle(BinaryNode* root)
{if(rootNULL)return;RecursionMiddle(root-lchild);cout(root-ch) ; RecursionMiddle(root-rchild);//中序遍历的顺序为左-根-右
}
递归实现后序遍历
void RecursionLast(BinaryNode* root)
{if(rootNULL)return;RecursionLast(root-lchild);RecursionLast(root-rchild);cout(root-ch) ; //后序遍历的顺序为左-右-根
}
在CreateBinaryTree方法中添加函数调用 //遍历结点cout先序遍历endl; RecursionFirst(node1); coutendl; cout中序遍历endl; RecursionMiddle(node1);coutendl; cout后序遍历endl; RecursionLast(node1);coutendl;
头文件及主函数
int main(int argc, char** argv) {CreateBinaryTree();//主函数只负责调用即可 return 0;
}
运行结果如下与结果相一致
