Definition: A binary tree is either empty, or it consists of a node called the root together with two binary tree called the left subtree and the right subtree of the root.
1. Traversal of Binary trees
Preorder: The root is visited first. Then the traversal moves to the left subtree. Then moves to the right subtree of the root. For the subtree, the order is the same.
Inorder: The left subtree of the root is visited first. Then the traversal moves to the root. Then moves to the right subtree of the root. For the subtree, the order is the same.
Postorder: The left subtree of the root is visited first. Then the traversal moves to the right subtree of the root. Then moves to the root. The order for the subtree is the sam.
For example:
Let's look at the binary tree in the folloing picture.
The preorder traversal is: 0137849256.
The inorder traversal is: 7381940526
The postorder traversal is: 7839415620
2. Implemetation
2.1 Definition of the node struct
1
struct BNode
2
{
3
int nData;
4 BNode *pLleft;
5 BNode *pRight;
6
7 BNode(int bValue)
8
{
9 nData = nValue;
10 pLeft = NULL;
11 pRight = NULL;
12
}
13
};
2.2 Definition of the binary tree class
1class BTree
2{
3public:
4 // Default constructor
5 BTree();
6 // Copy constructor
7 BTree(const BTree &tree);
8 // Destructor
9 virtual ~BTree();
10
11public:
12 // assignment operator
13 BTree& operator = (const BTree &tree);
14 // Return whether the tree is empty or not
15 bool IsEmpty() const;
16 // Return the nodes number
17 int NodeNumber() const;
18 // Return the leaves number
19 int LeafNumber() const;
20 // Return the height of the tree
21 int Height() const;
22
23 // Preorder traversal
24 void PreOrder() const;
25 // Inorder traversal
26 void InOrder() const;
27 // Postorder traversal
28 void PostOrder() const;
29 // Level traversal
30 void LevelTraversal() const;
31
32 // change into a mirror tree
33 void Reverse();
34 // Release all nodes
35 void Destory();
36
37private:
38 void Rec_Copy(BNode *&pSubRoot, BNode *pSrc);
39 void Rec_NodeNumber(BNode *pSubRoot, int &n) const;
40 void Rec_LeafNumber(BNode *pSubRoot, int &n) const;
41 int Rec_Height(BNode *pSubRoot);
42 void Rec_PreOrder(BNode *pSubRoot) const;
43 void Rec_InOrder(BNode *pSubRoot) const;
44 void Rec_PostOrder(BNode *pSubRoot) const;
45 void Rec_Reverse(BNode *&pSubRoot, BNode *pSrc);
46 void Rec_Destory(BNode *pSubRoot);
47
48private:
49 BNode *m_pRoot;
50};
2.3 Implementation of the binary tree class
1// BTree::BTree()
2BTree::BTree()
3{
4 m_pRoot = NULL;
5}
1// BTree::BTree(const BTree &tree)
2BTree::BTree(const BTree &tree)
3{
4 m_pRoot = NULL;
5 Rec_Copy(m_pRoot, tree->m_pRoot);
6}
1// BTree::operator = (const BTree &tree)
2BTree& BTree::operator = (const BTree &tree)
3{
4 Destory();
5 Rec_Copy(m_pRoot, tree->m_pRoot);
6
7 return *this;
8}
1// void BTree::Rec_Copy(BNode *&pSubRoot, BNode *pSrc)
2void BTree::Rec_Copy(BNode *&pSubRoot, BNode *pSrc)
3{
4 if (pSrc != NULL)
5 {
6 pSubRoot = new BNode(pSrc->nData);
7
8 if (pSrc->pLeft != NULL)
9 Rec_Copy(pSubRoot->pLeft, pSrc->pLeft);
10 if (pSrc->pRight != NULL)
11 Rec_Copy(pSubRoot->pRight, pSrc->pRight);
12 }
13}
1// BTree::IsEmpty()
2bool BTree::IsEmpty() const
3{
4 return (NULL == m_pRoot);
5}
1// void BTree::PreOrder() const
2void BTree::PreOrder() const
3{
4 Rec_PreOrder(m_pRoot);
5}
6
7// void BTree::Rec_PreOrder(BNode *pSubRoot) const
8void BTree::Rec_PreOrder(BNode *pSubRoot) const
9{
10 if (pSubRoot != NULL)
11 {
12 cout << pSubRoot->nData << endl;
13 Rec_PreOrder(pSubRoot->pLeft);
14 Rec_PreOrder(pSubRoot->pRight);
15 }
16}
1// void BTree::InOrder() const
2void BTree::InOrder() const
3{
4 Rec_InOrder(m_pRoot);
5}
6
7// void BTree::Rec_InOrder(BNode *pSubRoot) const
8void BTree::Rec_InOrder(BNode *pSubRoot) const
9{
10 if (pSubRoot != NULL)
11 {
12 Rec_InOrder(pSubRoot->pLeft);
13 cout << pSubRoot->nData << endl;
14 Rec_InOrder(pSubRoot->pRight);
15 }
16}
17
1// void BTree::PostOrder() const
2void BTree::PostOrder() const
3{
4 Rec_PostOrder(m_pRoot);
5}
6
7// void BTree::Rec_PostOrder(BNode *pSubRoot) const
8void BTree::Rec_PostOrder(BNode *pSubRoot) const
9{
10 if (pSubRoot != NULL)
11 {
12 Rec_PostOrder(pSubRoot->pLeft);
13 Rec_PostOrder(pSubRoot->pRight);
14 cout << pSubRoot->nData << endl;
15 }
16}
1// void BTree::Reverse()
2void BTree::Reverse()
3{
4 BNode *pNew = NULL;
5
6 Rec_Reverse(pNew, m_pRoot);
7 Destory();
8 m_pRoot = pNew;
9}
10
11// void BTree::Rec_Reverse(BNode *&pSubRoot, BNode *pSrc)
12void BTree::Rec_Reverse(BNode *&pSubRoot, BNode *pSrc)
13{
14 if (pSrc != NULL)
15 {
16 pSubRoot = new BNode(pSrc->nData);
17
18 if (pSrc->pLeft != NULL)
19 Rec_Copy(pSubRoot->pRight, pSrc->pLeft);
20 if (pSrc->pRight != NULL)
21 Rec_Copy(pSubRoot->pLeft, pSrc->pRight);
22 }
23}
1// void BTree::Destory()
2void BTree::Destory()
3{
4 Rec_Destory(m_pRoot);
5 m_pRoot = NULL;
6}
7
8// void BTree::Rec_Destory(BNode *pSubRoot)
9void BTree::Rec_Destory(BNode *pSubRoot)
10{
11 if (pSubRoot != NULL)
12 {
13 Rec_Destory(pSubRoot->pLeft);
14 Rec_Destory(pSubRoot->pRight);
15
16 delete pSubRoot;
17 }
18}
1// void CBTree::LevelTrail() const
2void CBTree::LevelTrail() const
3{
4 if (NULL == m_pRoot)
5 return;
6
7 list<BNode *> lt;
8 lt.push_back(m_pRoot);
9
10 cout << "Level by level" << endl;
11
12 while (!lt.empty())
13 {
14 BNode *tmp = lt.front();
15 lt.pop_front();
16 cout << tmp->data << endl;
17
18 if (tmp->left != NULL)
19 {
20 lt.push_back(tmp->left);
21 }
22 if (tmp->right != NULL)
23 {
24 lt.push_back(tmp->right);
25 }
26 }
27}
1// int CBTree::Height() const
2int CBTree::Height() const
3{
4 int height = 0;
5 height = Recursive_Height(m_pRoot);
6
7 cout << "Tree height is:" << endl;
8 cout << height << endl;
9
10 return height;
11}
12
13// int CBTree::Recursive_Height(BNode *pSubRoot) const
14int CBTree::Recursive_Height(BNode *pSubRoot) const
15{
16 if (NULL == pSubRoot)
17 {
18 return 0;
19 }
20 else
21 {
22 int depl = 0;
23 int depr = 0;
24
25 depl = Recursive_Height(pSubRoot->left);
26 depr = Recursive_Height(pSubRoot->right);
27
28 return (depl > depr) ? (depl + 1) : (depr + 1);
29 }
30}
1// int CBTree::LeafNumber() const
2int CBTree::LeafNumber() const
3{
4 int count = 0;
5 Recursive_LeafNumber(m_pRoot, count);
6
7 cout << "Leaf number is: " << endl;
8 cout << count << endl;
9 return count;
10}
11
12// void CBTree::Recursive_LeafNumber(BNode *pSubRoot, int &n) const
13void CBTree::Recursive_LeafNumber(BNode *pSubRoot, int &n) const
14{
15 if (pSubRoot != NULL)
16 {
17 if ((NULL == pSubRoot->left) && (NULL == pSubRoot->right))
18 {
19 n++;
20 return;
21 }
22
23 Recursive_LeafNumber(pSubRoot->left, n);
24 Recursive_LeafNumber(pSubRoot->right, n);
25 }
26}
1// int CBTree::NodeNumber() const
2int CBTree::NodeNumber() const
3{
4 int size = 0;
5 Recursive_NodeNumber(m_pRoot, size);
6
7 cout << "Tree Node Number is: " << endl;
8 cout << size << endl;
9 return size;
10}
11
12// void CBTree::Recursive_NodeNumber(BNode *pSubRoot, int &n) const
13void CBTree::Recursive_NodeNumber(BNode *pSubRoot, int &n) const
14{
15 if (pSubRoot != NULL)
16 {
17 n++;
18 NodeNumber(pSubRoot->left, n);
19 NodeNumber(pSubRoot->right, n);
20 }
21}
1// CBTree::~CBTree()
2CBTree::~CBTree()
3{
4 Destory();
5}