二叉树命题作业

《二叉树命题作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、问题一：代码定义一个树的结点：templatestructBinaryTreeNode{BinaryTreeNode(constT&x):_data(x),_left(NULL),_right(NULL){}T_data;//数值域BinaryTreeNode*_left;//左子树BinaryTreeNode*_right;//右子树};前序：这种遍历方式是遇到根节点先输出根节点，再递归遍历左子树，直到左子树为NULL，就开始返回并遍历右子树void_prevOrder(Node*ro

2、ot)//前---根、左、右---123456{if(root==NULL)return;Node*cur=root;if(cur){cout<_data<<"";_prevOrder(cur->_left);_prevOrder(cur->_right);}}中序和后序：这两种遍历方式的思想与前序遍历的方式类似，只是输出根节点的位置不同void_inOrder(Node*root)//中---左、根、右---324165{if(root==NULL)return;Node*cur=root;if(cu

3、r){_inOrder(cur->_left);cout<_data<<"";_inOrder(cur->_right);}}void_postOrder(Node*root)//后---左、右、根---342651{if(root==NULL)return;Node*cur=root;if(cur){_postOrder(cur->_left);_postOrder(cur->_right);cout<_data<<"";}}以上就是递归实现的二叉树的三种遍历算法了，之后还会附上二叉树的非

4、递归遍历算法！接下来是二叉树的实现代码：//结点定义templatestructBinaryTreeNode{BinaryTreeNode(constT&x):_data(x),_left(NULL),_right(NULL){}T_data;//数值域BinaryTreeNode*_left;//左子树BinaryTreeNode*_right;//右子树};//二叉树实现templateclassBinaryTree{typedefBinaryTreeNodeN

5、ode;public:BinaryTree():_root(NULL){}BinaryTree(T*a,size_tsize,constT&invalid){size_tindex=0;_root=_CreatTree(a,size,index,invalid);//构造树}BinaryTree(constBinaryTree&t)//拷贝构造{_root=_Copy

6、(t._root);}BinaryTree&operator=(constBinaryTree&t){if(this!=&t){BinaryTreetmp(t);//拷贝构造std::swap(_root,tmp._root);}}~BinaryTree(){_Destory(_root);}voidPrevOrder()//前序{if(_root)_prevOrder(_root);cout<

7、ut<_left=_CreatTree(a,si

8、ze,++index,invalid);//左子树root->_right=_CreatTree(a,size,++index,invalid);//右子树}returnroot;}Node*_Copy(Node*root){if(root==NULL){returnNULL;}Node*newroot=NULL;if(root){newroot=newNo