How to construct a pre-ordered binary Tree in C++

This article mainly explains "how to build a first-order binary tree in C++". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought. Let's study and learn how to build a first-order binary tree in C++.

First, define the BinaryTreeNode class

# include # include # include using namespace std; templateclass BinaryTree;template class BinaryTreeNode {public: friend class BinaryTree; BinaryTreeNode () {data = NULL; lChild = rChild = NULL;} BinaryTreeNode (T newdata) {this- > data = newdata; lChild = rChild = NULL;} T getData () {return data;} BinaryTreeNode* getLeftNode () {return lChild;} BinaryTreeNode* getRightNode () {return rChild;} T data; BinaryTreeNode* lChild; BinaryTreeNode* rChild Private:}

View Code

Second, define the BinaryTree class

Template class BinaryTree {public: BinaryTreeNode* root; char* p; BinaryTree () {root = NULL;} BinaryTree (T data) {root = new BinaryTreeNode (data); root- > lChild = NULL; root- > rChild = NULL;} ~ BinaryTree () {delete root;} / / build a binary tree and return BinaryTreeNode* CreateTree () {BinaryTreeNode* bt = NULL; char t; cin > > t If (t = ='#') {return NULL;} else {int num = t-'0trees; bt = new BinaryTreeNode (num); bt- > lChild = CreateTree (); bt- > rChild = CreateTree ();} return bt;} / / pre-build binary tree BinaryTreeNode* PreCreateTree () {BinaryTreeNode* bt = NULL; if (this- > root = NULL) {cout t If (t = ='#') {return NULL;} else {int num = t-0mm; bt = new BinaryTreeNode (num); if (this- > root = = NULL) {this- > root = bt;} cout data lChild = PreCreateTree (); cout data rChild = PreCreateTree ();} return bt;} void preOderTraversal (BinaryTreeNode * bt) / / first order traversal void inOrderTraversal (BinaryTreeNode * bt); / / medium order traversal void postOrderTraversal (BinaryTreeNode * bt); / / Post order traversal void levelTraversal (BinaryTreeNode * bt); / / layer-by-layer traversal private:}; template void BinaryTree::preOderTraversal (BinaryTreeNode * bt) {if (bt) {cout data; BinaryTree::preOderTraversal (bt- > getLeftNode ()); BinaryTree::preOderTraversal (bt- > getRightNode ()) } template void BinaryTree::inOrderTraversal (BinaryTreeNode * bt) {if (bt) {BinaryTree::inOrderTraversal (bt- > getLeftNode ()); cout data; BinaryTree::inOrderTraversal (bt- > getRightNode ());} template void BinaryTree::postOrderTraversal (BinaryTreeNode * bt) {if (bt) {BinaryTree::postOrderTraversal (bt- > getLeftNode ()); BinaryTree::postOrderTraversal (bt- > getRightNode ()); cout data;}} template void BinaryTree::levelTraversal (BinaryTreeNode * bt) {queue que Que.push (bt); while (! que.empty ()) {BinaryTreeNode* proot = que.front (); que.pop (); cout data; if (proot- > lChild! = NULL) {que.push (proot- > lChild); / / left child join the team} if (proot- > rChild! = NULL) {que.push (proot- > rChild); / / right child join the team}

View Code

Third, the main program runs

# include "pch.h" # include # include "BinaryTree.h" int main () {/ / scenario test 2 BinaryTree btree; btree.PreCreateTree (); / / build binary tree cout first