数据结构示例——二叉树

《数据结构示例——二叉树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1、二叉树templatestructTreeNode{Tdata;TreeNode*left,*right;};templateclassBinaryTree{public:BinaryTree(){root=NULL;}BinaryTree(constTreeNode&tree);~BinaryTree(){destroy(root);}boolIsEmpty()const{returnroot==NULL;}voidPreOrder(){PreOrder(root);}v

2、oidInOrder(){InOrder(root);}voidPostOrder(){PostOrder(root);}voidLevelOrder();intHeight(){returnHeight(root);}//二叉树高度intLeaf(){returnLeaf(root);}//叶子结点数intSize(){returnSize(root);}//结点数voidCreate(Tx){Create(root,x);}//建立二叉树BinaryTree&operator=(constBinaryTree<

3、T>&);private:TreeNode*root;voidPreOrder(TreeNode*t);voidInOrder(TreeNode*t);voidPostOrder(TreeNode*t);voiddestroy(TreeNode*t);intHeight(TreeNode*t);intLeaf(TreeNode*t);intSize(TreeNode*t);voidCreate(TreeNode*&t,Tx);voidcopyTree(TreeNode

4、*&t,TreeNode*t1);};templateBinaryTree::BinaryTree(constTreeNode&tree){if(tree.root==NULL)root=NULL;elsecopyTree(root,tree.root);}templatevoidBinaryTree::PreOrder(TreeNode*t){if(t){cout<data<<"";PreOrder(t->left);PreOrder(t->r

5、ight);}}templatevoidBinaryTree::InOrder(TreeNode*t){if(t){InOrder(t->left);cout<data<<"";InOrder(t->right);}}templatevoidBinaryTree::PostOrder(TreeNode*t){if(t){PostOrder(t->left);PostOrder(t->right);cout<data<<"";}}template

6、assT>voidBinaryTree::destroy(TreeNode*t){if(t){destroy(t->left);destroy(t->right);deletet;}}templateintBinaryTree::Height(TreeNode*t){if(t==NULL)return0;intl=Height(t->left);intr=Height(t->right);returnl>r?l+1:r+1;}templateintBinaryTre

7、e::Leaf(TreeNode*t){if(t==NULL)return0;if(t->left==NULL&&t->right==NULL)return1;returnLeaf(t->left)+Leaf(t->right);}templateintBinaryTree::Size(TreeNode*t){if(t==NULL)return0;elsereturnSize(t->left)+Size(t->right)+1;}templatevoidBinary

8、Tree::Create(TreeNode*&t,Tx){//以先序序列输入各结点的数据，某结点的左子树或右子树为空时输入一个特定的值x。Td;cin>>d;if(d==x)t=NULL;else{t=newTreeNode;t->data=d;Create(t->left,x);Create(t-