数据结构上机实验报告二叉树.docx

1、数据结构上机实验报告二叉树实现代码: #ifndef TREE_H#define TREE_H#include #include #include #include #include using namespace std;typedef int ElemType;typedef struct treeT ElemType key; struct treeT* left; struct treeT* right;treeT, *pTreeT;static void visit(pTreeT root) if (NULL != root) printf( %dn, root-key); stat

2、ic pTreeT BT_MakeNode(ElemType target) pTreeT pNode = (pTreeT) malloc(sizeof(treeT); assert( NULL != pNode ); pNode-key = target; pNode-left = NULL; pNode-right = NULL; return pNode;pTreeT BT_Insert(ElemType target, pTreeT* ppTree) pTreeT Node; assert( NULL != ppTree ); Node = *ppTree; if (NULL = No

3、de) return *ppTree = BT_MakeNode(target); if (Node-key = target) /不允许出现相同的元素 return NULL; else if (Node-key target) /向左 return BT_Insert(target, &Node-left); else return BT_Insert(target, &Node-right); void BT_PreOrder(pTreeT root) if (NULL != root) visit(root); BT_PreOrder(root-left); BT_PreOrder(r

4、oot-right); void BT_PreOrderNoRec(pTreeT root) stack s; while (NULL != root) | !s.empty() if (NULL != root) visit(root); s.push(root); root = root-left; else root = s.top(); s.pop(); root = root-right; void BT_InOrder(pTreeT root) if (NULL != root) BT_InOrder(root-left); visit(root); BT_InOrder(root

5、-right); void BT_InOrderNoRec(pTreeT root) stack s; while (NULL != root) | !s.empty() if (NULL != root) s.push(root); root = root-left; else root = s.top(); visit(root); s.pop(); root = root-right; void BT_PostOrder(pTreeT root) if (NULL != root) BT_PostOrder(root-left); BT_PostOrder(root-right); vi

6、sit(root); void BT_PostOrderNoRec(pTreeT root)void BT_LevelOrder(pTreeT root) queue q; treeT *treePtr; assert( NULL != root ); q.push(root); while (!q.empty() treePtr = q.front(); q.pop(); visit(treePtr); if (NULL != treePtr-left) q.push(treePtr-left); if (NULL != treePtr-right) q.push(treePtr-right

7、); #endif#include #include #include #define MAX_CNT 5#define BASE 100void main(int argc, char *argv) int i; char temp; pTreeT root = NULL; srand( (unsigned)time( NULL ) ); printf(请输入元素：nA.自动生成.nB.手动输入.n); do temp=getchar(); while(!(temp=A|temp=a|temp=B|temp=b); if(temp)=A|(temp)=a) for (i=0; iMAX_CN

8、T; i+) BT_Insert(rand() % BASE, &root); else if(temp)=B|(temp)=b) printf(请输入元素,元素以#结尾n); while(temp=getchar()!=#) BT_Insert(temp, &root); /前序 printf(PreOrder:n); BT_PreOrder(root); printf(n); printf(PreOrder no recursion:n); BT_PreOrderNoRec(root); printf(n); /中序 printf(InOrder:n); BT_InOrder(root); printf(n); printf(InOrder no recursion:n); BT_InOrderNoRec(root); printf(n); /后序 printf(PostOrder:n); BT_PostOrder(root); printf(n); /层序 printf(LevelOrder:n); BT_LevelOrder(root); printf(n);