《二叉树的遍历：前序,中序,后序,层序--包括递归和非递归实现》由会员分享，可在线阅读，更多相关《二叉树的遍历：前序,中序,后序,层序--包括递归和非递归实现（13页珍藏版）》请在金锄头文库上搜索。
1、二叉树的遍历：前序，中序，后序，层序包括递归和非递归实现后序遍历还没有明白，继续学习_，过几天写个huffman编码的例子来玩玩，不多说了，看代码吧，注意：程序申请的空间并没有释放_ /* created: 2005/12/30 created: 30:12:2005 10:39 filename: bintree.h author: Liu Qi purpose: 二叉树的3 种遍历方式 ( 包括非递归实现), 前序，后序和中序，先访问根节点就是前序 (部分书籍称为先根遍历,个人觉得该说法更好_)，类似的，最后访问根节点就是后序*/#ifndef TREE_H #define TREE_H
2、#include #include #include #include #include usingnamespace std; typedef int ElemType; typedef struct treeT ElemType key; struct treeT* left; struct treeT* right; treeT, *pTreeT; /*= * Function name: visit * Parameter: root:树根节点指针* Precondition: * Description: * Return value: * Author: Liu Qi, /- =*
3、/staticvoid visit(pTreeT root) if (NULL != root) printf(“ %dn“, root-key); /*= * Function name: BT_MakeNode * Parameter: target:元素值* Precondition: None * Postcondition: NULL != pTreeT * Description: 构造一个tree 节点，置左右指针为空，并且返回指向新节点的指针* Return value: 指向新节点的指针* Author: Liu Qi, 12/30/2005 =*/static pTreeT
4、 BT_MakeNode(ElemType target) pTreeT pNode = (pTreeT) malloc(sizeof (treeT); assert( NULL != pNode ); pNode-key = target; pNode-left = NULL; pNode-right = NULL; return pNode; /*= * Function name: BT_Insert * Parameter: target:要插入的元素值, pNode:指向某一个节点的指针* Precondition: NULL != ppTree * Description: 插入
5、target到 pNode的后面* Return value: 指向新节点的指针* Author: Liu Qi, 12/29/2005 =*/pTreeT BT_Insert(ElemType target, pTreeT* ppTree) pTreeT Node; assert( NULL != ppTree ); Node = *ppTree; if (NULL = Node) return *ppTree = BT_MakeNode(target); if (Node-key = target) / 不允许出现相同的元素 return NULL; elseif (Node-key ta
6、rget) / 向左 return BT_Insert(target, else return BT_Insert(target, /*= * Function name: BT_PreOrder * Parameter: root:树根节点指针* Precondition: None * Description: 前序遍历* Return value: void * Author: Liu Qi, 12/29/2005 =*/void BT_PreOrder(pTreeT root) if (NULL != root) visit(root); BT_PreOrder(root-left);
7、 BT_PreOrder(root-right); /*= * Function name: BT_PreOrderNoRec * Parameter: root:树根节点指针* Precondition: Node * Description: 前序 ( 先根 )遍历非递归算法* Return value: void * Author: Liu Qi, 1/1/2006 =*/void BT_PreOrderNoRec(pTreeT root) stack s; while (NULL != root) | !s.empty() if (NULL != root) visit(root);
8、s.push(root); root = root-left; else root = s.top(); s.pop(); root = root-right; /*= * Function name: BT_InOrder * Parameter: root:树根节点指针* Precondition: None * Description: 中序遍历* Return value: void * Author: Liu Qi, 12/30/2005 =*/void BT_InOrder(pTreeT root) if (NULL != root) BT_InOrder(root-left);
9、visit(root); BT_InOrder(root-right); /*= * Function name: BT_InOrderNoRec * Parameter: root:树根节点指针* Precondition: None * Description: 中序遍历 ,非递归算法* Return value: void * Author: Liu Qi, 1/1/2006 =*/void BT_InOrderNoRec(pTreeT root) stack s; while (NULL != root) | !s.empty() if (NULL != root) s.push(ro
10、ot); root = root-left; else root = s.top(); visit(root); s.pop(); root = root-right; /*= * Function name: BT_PostOrder * Parameter: root:树根节点指针* Precondition: None * Description: 后序遍历* Return value: void * Author: Liu Qi, 12/30/2005 =*/void BT_PostOrder(pTreeT root) if (NULL != root) BT_PostOrder(root-left); BT_PostOrder(root-right); visit(root); /*= * Funct
