二叉树ADT_BinaryTree
最后更新于：2022-04-01 20:51:28
二叉树是结点的有限集合, 该集合或者为空集, 或者是由一个根和两棵互不相交的称为该根的左子树和右子树的二叉树组成.
二叉树可以为空集, 可以有空二叉树, 也可以有空的左子树 或/和 又子树.
二叉树的性质: 1.第i层至多有2^(i - 1)个结点. 2.高度为h的二叉树上至多有2*h - 1个结点. 3.包含n个元素的二叉树高度至少为>=log2(n + 1)取整. 3.任意一颗二叉树中, 若叶结点的个数为n0, 度为2的结点个数为n2, 则必有n0 = n2 + 1.
树与二叉树区别: 1.树不能为空树, 二叉树可以为空. 2.树的子树之间是无序的, 其子树不分次序. 二叉树中结点的子树要分左右子树.
满二叉树: 高度为h的二叉树恰好有2^h - 1个结点.
完全二叉树: 一棵二叉树中, 只有最下面两层结点的度可以小于2, 并且最下面一层的叶结点集中在靠左的若干位置上.
扩充二叉树(2 - 树): 除叶子结点外, 其余结点都必须有两个孩子.
树与二叉树区别: 1.树不能为空树, 二叉树可以为空. 2.树的子树之间是无序的, 其子树不分次序. 二叉树中结点的子树要分左右子树.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
template
struct BTNode
{
/* data */
BTNode() { lChild = rChild = NULL; }
BTNode(const T& x) {
element = x;
lChild = rChild = NULL;
}
BTNode(const T& x, BTNode* l, BTNode* r) {
element = x;
lChild = l;
rChild = r;
}
T element;
BTNode* lChild, *rChild;
};
template
class BinaryTree
{
public:
BinaryTree() { root = NULL; }
bool IsEmpty() const; // 判断是否为空, 是返回true
void Clear(); // 移去所有结点, 成为空二叉树
bool Root(T& x) const; // 若二叉树为空, 则x为根的值, 返回true
BTNode* Root();
int Size();
int Count() { return Count(root); }
void MakeTree(const T& x, BinaryTree& left, BinaryTree& right); // 构造一颗二叉树, 根的值为x, left & right为左右子树
void BreakTree(T& x, BinaryTree& left, BinaryTree& right); // 拆分二叉树为三部分, x为根的值, left & right为左右子树
void PreOrder(void (*Visit)(T& x)); // 先序遍历二叉树
void InOrder(void (*Visit)(T& x)); // 中序遍历二叉树
void PostOrder(void (*Visit)(T& x)); // 后序遍历二叉树
/* data */
protected:
BTNode* root;
private:
void Clear(BTNode* t);
int Size(BTNode *t); // 返回二叉树结点个数
int Count(BTNode *t); // 返回二叉树只有一个孩子的结点个数
void PreOrder(void (*Visit)(T &x), BTNode *t);
void InOrder(void (*Visit)(T &x), BTNode *t);
void PostOrder(void (*Visit)(T &x), BTNode *t);
};
template
void Visit(T &x)
{
cout << x << '\t';
}
template
BTNode* BinaryTree::Root()
{
return root;
}
template
bool BinaryTree::Root(T &x) const
{
if(root) {
x = root -> element;
return true;
}
return false;
}
template
void BinaryTree::Clear(BTNode* t)
{
if(t) {
Clear(t -> lChild);
Clear(t -> rChild);
cout << "delete" << t -> element << "..." << endl;
delete t;
}
}
template
void BinaryTree::MakeTree(const T& x, BinaryTree& left, BinaryTree& right)
{
if(root || &left == &right) return;
root = new BTNode(x, left.root, right.root);
left.root = right.root = NULL;
}
template
void BinaryTree::BreakTree(T& x, BinaryTree& left, BinaryTree& right)
{
if(!root || &left == &right || left.root || right.root) return;
x = root -> element;
left.root = root -> lChild;
right.root = root -> rChild;
delete root;
root = NULL;
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x))
{
PreOrder(Visit, root);
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
Visit(t -> element);
PreOrder(Visit, t -> lChild);
PreOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::InOrder(void (*Visit)(T& x))
{
InOrder(Visit, root);
}
template
void BinaryTree::InOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
InOrder(Visit, t -> lChild);
Visit(t -> element);
InOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x))
{
PostOrder(Visit, root);
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
PostOrder(Visit, t -> lChild);
PostOrder(Visit, t -> rChild);
Visit(t -> element);
}
}
template
int BinaryTree::Size()
{
return Size(root);
}
template
int BinaryTree::Size(BTNode *t)
{
if(!t) return 0;
return Size(t -> lChild) + Size(t -> rChild) + 1;
}
template
int BinaryTree::Count(BTNode *t)
{
if(!t) return 0;
if(((t -> lChild) && (!t -> rChild)) || ((!t -> lChild) && (t -> rChild))) return 1;
return Count(t -> lChild) + Count(t -> rChild);
}
int main(int argc, char const *argv[])
{
BinaryTree a, b, x, y, z; // 构造过程见课本75页.
char e;
y.MakeTree('E', a, b);
z.MakeTree('F', a, b);
x.MakeTree('C', y, z);
y.MakeTree('D', a, b); // 用y前y已经被置空
z.MakeTree('B', y, x);
cout << endl << "PreOrder\t";
z.PreOrder(Visit);
cout << endl << "InOrder\t\t";
z.InOrder(Visit);
cout << endl << "PostOrder\t";
z.PostOrder(Visit);
cout << endl;
cout << "Tree's size = " << z.Size() << endl;
cout << "Tree's count = " << z.Count() << endl;
z.BreakTree(e, y, x);
cout << endl << "PreOrder\t";
z.PreOrder(Visit);
cout << endl << "InOrder\t\t";
z.InOrder(Visit);
cout << endl << "PostOrder\t";
z.PostOrder(Visit);
cout << endl;
cout << "Tree's size = " << z.Size() << endl;
cout << "Tree's count = " << z.Count() << endl;
return 0;
}
~~~
';