c++ 先序构建二叉树 - PHP

TOP

c++ 先序构建二叉树(一)

2019-09-17 16:19:33 【大中小】浏览:95次

二叉树首先要解决构建问题，才能考虑后续的遍历，这里贴出通过先序构建二叉树，同时包含四种二叉树的遍历方法（先序，中序，后序，逐层）

第一、定义BinaryTreeNode 类

 1 #include <iostream>
 2 #include <string>
 3 #include <queue>
 4 using namespace std;
 5 
 6 template<typename T >class BinaryTree;
 7 template <typename T> class BinaryTreeNode {
 8 public:
 9     friend class BinaryTree<T>;
10     BinaryTreeNode() {
11         data = NULL;
12         lChild = rChild = NULL;
13     }
14     BinaryTreeNode(T newdata) {
15         this->data = newdata;
16         lChild = rChild = NULL;
17     }
18     T getData() {
19         return data;
20     }
21     BinaryTreeNode<T> * getLeftNode() {
22         return lChild;
23     }
24     BinaryTreeNode<T> * getRightNode() {
25         return rChild;
26     }
27     T data;
28     BinaryTreeNode<T>* lChild;
29     BinaryTreeNode<T>* rChild;
30 private:
31 
32 };

View Code

第二、定义BinaryTree 类

  1 template <typename T> class BinaryTree {
  2 public:
  3     BinaryTreeNode<T> *root;
  4     char* p;
  5     BinaryTree() { root = NULL; }
  6     BinaryTree(T data) {
  7         root = new BinaryTreeNode<T>(data);
  8         root->lChild = NULL;
  9         root->rChild = NULL;
 10     }
 11     ~BinaryTree() {
 12         delete root;
 13     }
 14 
 15     //构建二叉树并返回
 16     BinaryTreeNode<T>* CreateTree() {
 17         BinaryTreeNode<int>* bt = NULL;
 18         char t;
 19         cin >> t;
 20         if (t == '#')
 21         {
 22             return NULL;
 23         }
 24         else {
 25             int num = t - '0';
 26             bt = new BinaryTreeNode<T>(num);
 27             bt->lChild = CreateTree();
 28             bt->rChild = CreateTree();
 29         }
 30         return bt;
 31     }
 32 
 33     //先序构建二叉树
 34     BinaryTreeNode<T>* PreCreateTree() {
 35         BinaryTreeNode<int>* bt = NULL;
 36         if (this->root == NULL)
 37         {
 38             cout << "请输入根节点（#代表空树）:";
 39         }
 40         else {
 41             cout << "请输入节点（#代表空树）:";
 42         }
 43         char t;
 44         cin >> t;
 45         if (t == '#')
 46         {
 47             return NULL;
 48         }
 49         else {
 50             int num = t - '0';
 51             bt = new BinaryTreeNode<T>(num);
 52             if (this->root == NULL)
 53             {
 54                 this->root = bt;
 55             }
 56             cout << bt->data << "的左孩子";
 57             bt->lChild = PreCreateTree();
 58 
 59             cout << bt->data << "的右边孩子";
 60             bt->rChild = PreCreateTree();
 61         }
 62         return bt;
 63     }   
 64 
 65     void preOderTraversal(BinaryTreeNode<T> *bt);  //先序遍历
 66     void inOrderTraversal(BinaryTreeNode<T> *bt);  //中序遍历
 67     void postOrderTraversal(BinaryTreeNode<T> *bt);//后序遍历
 68     void levelTraversal(BinaryTreeNode<T> *bt);    //逐层遍历
 69 
 70 private:
 71 
 72 };
 73 
 74 template <typename T>
 75 void BinaryTree<T>::preOderTraversal(BinaryTreeNode<T> *bt) {
 76     if (bt)
 77     {
 78         cout << bt->data;
 79         BinaryTree<T>::preOderTraversal(bt->getLeftNode());
 80         BinaryTree<T>::preOderTraversal(bt->getRightNode());
 81     }
 82 }
 83 
 84 template <typename T>
 85 void BinaryTree<T>::inOrderTraversal(BinaryTreeNode<T> *bt) {
 86     if (bt)
 87     {
 88         BinaryTree<T>::inOrderTraversal(bt->getLeftNode());
 89         cout << bt->data;
 90         BinaryTree<T>::inOrderTraversal(bt->getRightNode());
 91     }
 92 }
 93 
 94 template <typename T>
 95 void BinaryTree<T>::postOrderTraversal(BinaryTreeNode<T> *bt) {
 96     if (bt)
 97     {
 98         BinaryTree<T>::postOrderTraversal(

首页上一页 1 2 下一页尾页 1/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：[PHP] 持续交付Jenkins安装	下一篇：ecstore Fatal error: Class '..