二叉树的生成和操作

真的没想到，这种简单的问题居然还要开一个Topic，

I Slay!

• 二叉树的生成和操作
  • 二叉树的结构
  • 生成树
    • 数据的输入格式
    • 树的显示
      • 前序法等
      • 层次法(按照每层进行显示)

二叉树的结构

一个无性繁殖人生了两个孩子，没想到吧，孩子还是无性繁殖的…

那么最简单元就是上图这样了。

代码如此：

struct BinaryTree {
  Element data;    //节点的数据类型
  struct BiTree* leftChild;  //1号孩子
  struct BiTree* rightChild; //2号孩子
}tree;  //搞个tree多好

生成树

数据的输入格式

这里我们使用#号作为空节点(char为数据类型).

当然,输入的顺序十分重要, 假定优先级为:根>左孩子>右孩子 (又被称为先序)

既然有最小单元,我们可以通过递归法写出一个生成树的方法:

//前序递归创建二叉树
bool InitTree(BiTree& tree) {   //传引用
    char data;
    cin >> data;
    if (data == '#')  //跳出递归判断
        return false;   //跳出时若为flase则说明该内存空间应被销毁
    tree.data = data;   //赋值
    tree.leftChild  = new BiTree;   //为左孩子开辟空间
    if(!InitTree(*tree.leftChild))  { //判断左孩子是否为空并销毁
        delete tree.leftChild;
        tree.leftChild = NULL;
    }
    if (!InitTree(*tree.rightChild)) { //判段右孩子是否为空并销毁
        delete tree.rightChild;
        tree.rightChild = NULL;
    }
    return true;
}

树的显示

前序法等

最简单的树的显示方法就是前序法,中序法和后序法了,下面是前序法的代码:

//前序法输出树
void PreOrder(BiTree& tree) {  //传引用
    BiTree* treePtr = &tree;  //创建指针指向树
    if (treePtr != NULL) {
        cout << treePtr->data << "\t";
        PreOrder(*treePtr->leftChild);  //解引用指针
        PreOrder(*treePtr->rightChild);  //解引用指针
    }
}

层次法(按照每层进行显示)

实现层次显示需要对元素进行出入栈操作.

首先定义栈的结构:

struct Quere {
    vector<BiTree*> vector;
}quere;

这里使用了vector模板类方便出入栈.

层次法代码如下(无需递归):

void LvlOrder(BiTree &tree) {   //传值引用
    if (&tree != NULL) {    //若树不为空
        quere.vector.emplace_back(&tree);   //入栈
        BiTree* popNode;    //定义一个临时变量保存弹出指针
        while (quere.vector.size() != 0) {  //栈内非空时则说明仍有元素需要出栈
            popNode = quere.vector.at(0);   //拿取栈内首个元素
            quere.vector.erase(quere.vector.begin());   //删除栈内首个元素
            cout << popNode->data << ',';  //输出
            if (popNode->leftChild) 
                quere.vector.emplace_back(popNode->leftChild);   //将左孩子入栈
            if (popNode->rightChild)
                quere.vector.emplace_back(popNode->rightChild);  //将右孩子入栈
        }
    }
    return;
}

(对了，这样使用Vector的开销是O(n^2))