二叉树命题作业.docx

问题一：代码定义一个树的结点：template struct BinaryTreeNode BinaryTreeNode(const T& x) :_data(x) ,_left(NULL) ,_right(NULL) T _data; /数值域 BinaryTreeNode* _left; /左子树 BinaryTreeNode* _right; /右子树 ; 前序：这种遍历方式是遇到根节点先输出根节点，再递归遍历左子树，直到左子树为 NULL，就开始返回并遍历右子树void _prevOrder(Node* root) /前-根、左、右-1 2 3 4 5 6 if(root = NULL) return ; Node* cur = root; if(cur) cout_data_left); _prevOrder(cur-_right); 中序和后序：这两种遍历方式的思想与前序遍历的方式类似，只是输出根节点的位置不同void _inOrder(Node* root) /中-左、根、右-3 2 4 1 6 5 if(root = NULL) return ; Node* cur = root; if (cur) _inOrder(cur-_left); cout_data_right); void _postOrder(Node* root) /后-左、右、根-3 4 2 6 5 1 if (root = NULL) return ; Node* cur = root; if (cur) _postOrder(cur-_left); _postOrder(cur-_right); cout_data ; 以上就是递归实现的二叉树的三种遍历算法了，之后还会附上二叉树的非递归遍历算法！接下来是二叉树的实现代码：/结点定义 template struct BinaryTreeNode BinaryTreeNode(const T& x) :_data(x) ,_left(NULL) ,_right(NULL) T _data; /数值域 BinaryTreeNode* _left; /左子树 BinaryTreeNode* _right; /右子树 ; /二叉树实现 template class BinaryTree typedef BinaryTreeNode Node; public: BinaryTree() :_root(NULL) BinaryTree(T* a,size_t size,const T& invalid) size_t index = 0; _root = _CreatTree(a,size,index,invalid); /构造树 BinaryTree(const BinaryTree& t) /拷贝构造 _root = _Copy(t._root); BinaryTree& operator=(const BinaryTree& t) if (this != &t) BinaryTree tmp(t); /拷贝构造 std:swap(_root,tmp._root); BinaryTree() _Destory(_root); void PrevOrder() /前序 if (_root) _prevOrder(_root); coutendl; void InOrder() /中序 if (_root) _inOrder(_root); coutendl; void PostOrder() /后序 if(_root) _postOrder(_root); coutendl; protected: Node* _CreatTree(T* a,size_t size,size_t& index,const T& invalid) assert(a); Node* root = NULL; while(index_left = _CreatTree(a,size,+index,invalid); /左子树 root-_right = _CreatTree(a,size,+index,invalid); /右子树 return root; Node* _Copy(Node* root) if (root = NULL) return NULL; Node* newroot = NULL; if (root) newroot = new Node(root-_data); newroot-_left = _Copy(root-_left); newroot-_right = _Copy(root-_right); return newroot; void _Destory(Node* root) Node* cur = root; if (cur != NULL) _Destory(cur-_left); _Destory(cur-_right); delete cur; cur = NULL; void _prevOrder(Node* root) /前-根、左、右-1 2 3 4 5 6 if(root = NULL) return ; Node* cur = root; if(cur) cout_data_left); _prevOrder(cur-_right); void _inOrder(Node* root) /中-左、根、右-3 2 4 1 6 5 if(root = NULL) return ; Node* cur = root; if (cur) _inOrder(cur-_left); cout_data_right); void _postOrder(Node* root) /后-左、右、根-3 4 2 6 5 1 if (root = NULL) return ; Node* cur = root; if (cur) _postOrder(cur-_left); _postOrder(cur-_right); cout_data ; protected: Node* _root; /定义一个根结点 ; void TestBinaryTree() int a110 = 1,2,3,#,#,4,#,#,5,6; int a215 = 1,2,#,3,#,#,4,5,#,6,#,7,#,#,8; BinaryTree t1(a1,10,#); BinaryTree T1(a2,15,#); /BinaryTree t2(t1); /BinaryTree t3 = t1; t1.PrevOrder(); /1 2 3 4 5 6 t1.InOrder(); /3 2 4 1 6 5 t1.PostOrder(); /3 4 6 2 5 1 二、二叉树的遍历前序遍历-先遍历根节点，再遍历左子树，最后遍历右子树（根-左-右）中序遍历-先遍历左子树，再遍历根节点，最后遍历右子树（左-根-右）后序遍历-先遍历左子树，再遍历右子树，最后遍历根节点（左-右-根）前序遍历结果：1 2 3 4 5 6 中序遍历结果：3 2 4 1 6 5后序遍历结果：3 4 6 2 5 1由于遍历二叉树的过程是一层一层往下循环的过程，因此在这里用递归方式就比较简单一些问题二： /冒泡排序void BublleSort(int A,int n) int t,flag=0; for(int i=0; ii; j-) /从后往前冒泡 if(AjAj-1) t=Aj; Aj=Aj-1; Aj-1=t; flag=1; if(!flag) return; 问题三：三种算法比较：从比较次数而言：冒泡和选择排序的时间复杂度是一样的，而插入排序的效率是冒泡和选择排序的两倍。从交换（复制）次数而言：插入排序的效率是冒泡排序的3倍(一次交换的复杂度约等于三次复制，冒泡排序中是要交换，而插入排序时要复制就可