c++先序二叉树的构建详解

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

第一、定义BinaryTreeNode 类

#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

第二、定义BinaryTree 类

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;

  }

 

  //构建二叉树并返回

  BinaryTreeNode* CreateTree() {

    BinaryTreeNode* bt = NULL;

    char t;

    cin >> t;

    if (t == '#')

    {

      return NULL;

    }

    else {

      int num = t - '0';

      bt = new BinaryTreeNode(num);

      bt->lChild = CreateTree();

      bt->rChild = CreateTree();

    }

    return bt;

  }

 

  //先序构建二叉树

  BinaryTreeNode* PreCreateTree() {

    BinaryTreeNode* bt = NULL;

    if (this->root == NULL)

    {

      cout << "请输入根节点（#代表空树）:";

    }

    else {

      cout << "请输入节点（#代表空树）:";

    }

    char t;

    cin >> t;

    if (t == '#')

    {

      return NULL;

    }

    else {

      int num = t - '0';

      bt = new BinaryTreeNode(num);

      if (this->root == NULL)

      {

 this->root = bt;

      }

      cout << bt->data << "的左孩子";

      bt->lChild = PreCreateTree();

 

      cout << bt->data << "的右边孩子";

      bt->rChild = PreCreateTree();

    }

    return bt;

  }  

 

  void preOderTraversal(BinaryTreeNode *bt); //先序遍历

  void inOrderTraversal(BinaryTreeNode *bt); //中序遍历

  void postOrderTraversal(BinaryTreeNode *bt);//后序遍历

  void levelTraversal(BinaryTreeNode *bt);  //逐层遍历

 

private:

 

};

 

template 

void BinaryTree::preOderTraversal(BinaryTreeNode *bt) {

  if (bt)

  {

    cout << bt->data;

    BinaryTree::preOderTraversal(bt->getLeftNode());

    BinaryTree::preOderTraversal(bt->getRightNode());

  }

}

 

template 

void BinaryTree::inOrderTraversal(BinaryTreeNode *bt) {

  if (bt)

  {

    BinaryTree::inOrderTraversal(bt->getLeftNode());

    cout << bt->data;

    BinaryTree::inOrderTraversal(bt->getRightNode());

  }

}

 

template 

void BinaryTree::postOrderTraversal(BinaryTreeNode *bt) {

  if (bt)

  {

    BinaryTree::postOrderTraversal(bt->getLeftNode());

    BinaryTree::postOrderTraversal(bt->getRightNode());

    cout << bt->data;

  }

}

 

template 

void BinaryTree::levelTraversal(BinaryTreeNode *bt) {

 

  queue*> que;

  que.push(bt);

  while (!que.empty())

  {

    BinaryTreeNode* proot = que.front();

    que.pop();

    cout << proot->data;

 

    if (proot->lChild != NULL)

    {

      que.push(proot->lChild);//左孩子入队

    }

    if (proot->rChild != NULL)

    {

      que.push(proot->rChild);//右孩子入队

    }

  }

}

View Code

第三、主程序运行

#include "pch.h"

#include 

#include "BinaryTree.h"

 

int main()

{

  //场景测试2

  BinaryTree btree;

  btree.PreCreateTree();//先序构建二叉树

  cout << "先序遍历:";

  btree.preOderTraversal(btree.root); cout << endl;//先序遍历  

  cout << "中序遍历:";

  btree.inOrderTraversal(btree.root); cout << endl;//中序遍历

  cout << "后序遍历:";

  btree.postOrderTraversal(btree.root); cout << endl;//后序遍历

  cout << "逐层序遍历:";

  btree.levelTraversal(btree.root);

 

}

View Code

最终测试运行截图