这篇文章主要介绍了举例讲解C语言程序中对二叉树数据结构的各种遍历方式,先序中序后序二叉树遍历几乎成了最老生常谈的数据结构基础知识,的朋友可以参考下
二叉树遍历的基本思想
二叉树的遍历本质上其实就是
来源gaodai.ma#com搞##代!^码网
入栈出栈的问题，递归算法简单且容易理解，但是效率始终是个问题。非递归算法可以清楚的知道每步实现的细节，但是乍一看不想递归算法那么好理解，各有各的好处吧。接下来根据下图讲讲树的遍历。
1、先序遍历：先序遍历是先输出根节点，再输出左子树，最后输出右子树。上图的先序遍历结果就是：ABCDEF
2、中序遍历：中序遍历是先输出左子树，再输出根节点，最后输出右子树。上图的中序遍历结果就是：CBDAEF
3、后序遍历：后序遍历是先输出左子树，再输出右子树，最后输出根节点。上图的后序遍历结果就是：CDBFEA
其中，后序遍历的非递归算法是最复杂的，我用了一个标识符isOut来表明是否需要弹出打印。因为只有当节点的左右子树都打印后该节点 才能弹出栈打印，所以标识isOut为1时打印，isOut初始值为0，这主要是为了处理非叶子节点。由后序遍历的原理决定，左右子树都被打印该节点才能打印，所以该节点肯定会被访问2次，第一次的时候不要打印，第二次打印完右子树的时候打印。叶子节点打印完后将isOut置为1。（纯粹是自己想的，应该还有逻辑更简单的算法）
实例
构造和遍历
#include #include typedef struct _NODE//节点结构 { struct _NODE* leftChild; int value; struct _NODE* rightChild; } NODE, *PNODE; PNODE createNode(int value){//创建一个新节点 PNODE n = (PNODE)malloc(sizeof(NODE)); n->value = value; n->leftChild = NULL; n->rightChild = NULL; return n; } PNODE insertLeftChild(PNODE parent, int value){//在指定节点上插入左节点 return (parent->leftChild = createNode(value)); } PNODE insertRightChild(PNODE parent, int value){//在指定节点上插入左节点 return (parent->rightChild = createNode(value)); } void createBTree(PNODE root, int i){//向树中插入一些元素 if (i == 0) { return; } else{ PNODE l = insertLeftChild(root, i * 10 + 1); PNODE r = insertRightChild(root, i * 10 + 2); createBTree(l, --i); createBTree(r, i); } } void printDLR(PNODE root){//先序遍历：对每一刻子树都是根->左->右的顺序 if (root == NULL) { return; } printf("%-4d", root->value); printDLR(root->leftChild); printDLR(root->rightChild); } void printLDR(PNODE root){//中序遍历： if (root == NULL) { return; } printLDR(root->leftChild); printf("%-4d", root->value); printLDR(root->rightChild); } void printLRD(PNODE root){//后序遍历 if (root == NULL) { return; } printLRD(root->leftChild); printLRD(root->rightChild); printf("%-4d", root->value); } void main(){ PNODE root = createNode(0);//创建根节点 createBTree(root, 3); printf("先序遍历: "); printDLR(root);//遍历 printf("\n中序遍历: "); printLDR(root); printf("\n后序遍历: "); printLRD(root); printf("\n"); }
执行结果：
先序遍历：
中序遍历：
后序遍历：
C++中可以使用类模板，从而使节点值的类型可以不止限定在整型：
#include template class Node//节点类模板 { public: Node(T value):value(value)//构造方法 { leftChild = 0; rightChild = 0; } Node* insertLeftChild(T value);//插入左孩子,返回新节点指针 Node* insertRightChild(T vallue);//插入右孩子 void deleteLeftChild();//删左孩子 void deleteRightChild();//删右孩子 void showDLR();//先序遍历 void showLDR();//中序遍历 void showLRD();//后序遍历 protected: T value;//节点值 Node* leftChild;//左孩子指针 Node* rightChild;//右孩子指针 private: }; template Node* Node::insertLeftChild(T value){//插入左孩子 return (this->leftChild = new Node(value)); } template Node* Node::insertRightChild(T value){//插入右孩子 return (this->rightChild = new Node(value)); } template void Node::deleteLeftChild(){//删除左孩子 delete this->leftChild; this->leftChild = 0; } template void Node::deleteRightChild(){//删除右孩子 delete this->rightChild; this->rightChild = 0; } template void Node::showDLR(){//先序遍历 cout<value<showDLR(); } if (rightChild) { rightChild->showDLR(); } } template void Node::showLDR(){//中序遍历 if (leftChild) { leftChild->showLDR(); } cout<value<showLDR(); } } template void Node::showLRD(){//后序遍历 if (leftChild) { leftChild->showLRD(); } if (rightChild) { rightChild->showLRD(); } cout<value<<" "; } template void createSomeNodes(Node* root, int i, T base){//构建一个二叉树 if (i == 0) { return; } Node* l = root->insertLeftChild(i + base); Node* r = root->insertRightChild(i + base); createSomeNodes(l, --i, base); createSomeNodes(r, i, base); } template void showTest(Node* root){//显示各种遍历方式结果 cout<showDLR(); cout<<endl<showLDR(); cout<<endl<showLRD(); cout<<endl; } void main(){ Node *root1 = new Node(0); createSomeNodes(root1, 3, 0); cout<<"整型:"<<endl; showTest(root1); Node *root2 = new Node('a'); createSomeNodes(root2, 3, 'a'); cout<<"字符型:"<<endl; showTest(root2); Node *root3 = new Node(0.1f); createSomeNodes(root3, 3, 0.1f); cout<<"浮点型:"<<endl; showTest(root3); }
以上就是举例讲解C语言程序中对二叉树数据结构的各种遍历方式的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：举例讲解C语言程序中对二叉树数据结构的各种遍历方式
转载请注明原文链接：举例讲解C语言程序中对二叉树数据结构的各种遍历方式
