博客

1. 二叉树的定义

后续更新

2.二叉树的性质

后续更新

3.二叉树的存储结构

• 顺序存储结构。顺序存储结构使用一组地址连续的存储单元来存储数据元素，为了能够在存储结构中反映出结点之间的逻辑关系，必须将二叉树中的结点依照一定的规律安排在这组单元中。
• 链式存储结构设计不同的结点结构可构成不同形式的链式存储结构。由二叉树的定义得知，二叉树的结点由一个数据元素和分别指向其左、 右子树的两个分支构成，则表示二叉树的链表
  
  中的结点至少包含 3 个域：数据域和左、 右指针域。


注意:本文对于二叉树采用链式存储结构实现。(C++)


4. 代码

binary_tree.h

实现二叉树的各种操作

#ifndef BINARY_TREE_H
#define BINARY_TREE_H
#include <iostream>
#include <vector>
#include <array>
using std::vector;
using std::array;
using std::cout;
using std::endl;
using std::cin;
using std::cerr;
template <typename T>
struct BitNode {
    /* data */
    T data;
    BitNode* lchild;
    BitNode* rchild;
    BitNode(T data) : data(data), lchild(nullptr), rchild(nullptr) {};
};
template <typename T>
class BinaryTree {
    private:
        int count;
        void PreOrderTraverse(BitNode<T>* node,void (*visit)(T));//用于先序遍历二叉树
        void MidOrderTraverse(BitNode<T>* node,void (*visit)(T)); //用于中序遍历二叉树
        void EndOrderTraverse(BitNode<T>* node,void (*visit)(T)); //用于后序遍历二叉树
        void LevelOrderTraverse(void (*visit)(T));//用于层序遍历二叉树
        void PreOrderTraverseStack(void (*visit)(T)); //用栈先序遍历二叉树
        void MidOrderTraverseStack(void (*visit)(T)); //用栈中序遍历二叉树
    public:
        BitNode<T>* root;
        BinaryTree() : root(nullptr),count(0){}; //无参构造函数
        BinaryTree(const BitNode<T>*& rhs) : root(rhs),count(0){}; //复制构造函数
        bool Empty(); // 判断二叉树是否为空
        void Traverse(int key,void (*visit)(T));//用于遍历二叉树
        void CreateTree(BitNode<T> *&ptr);
};
template <typename T>
inline bool BinaryTree<T>::Empty() {
    if (this -> root = nullptr) {
        return true;
    }
    return false;
}
template <typename T>
void BinaryTree<T>::Traverse(int key,void (*visit)(T)) {
    if (key == 1) {
        PreOrderTraverse(this -> root,visit);
    }
    else if (key == 2) {
        MidOrderTraverse(this -> root,visit);
    }
    else if (key == 3) {
        EndOrderTraverse(this -> root,visit);
    }
    else if (key == 4) {
        LevelOrderTraverse(visit);
    }
    else if (key == 5) {
        PreOrderTraverseStack(visit);
    }
    else if (key == 6) {
        MidOrderTraverseStack(visit);
    }
    else if (key == 7) {
        EndOrderTraverseStack(visit);
    }
}
template <typename T>
void BinaryTree<T>::PreOrderTraverse(BitNode<T>* node,void (*visit)(T)) {
    if (node) {
        visit(node -> data);
        PreOrderTraverse(node -> lchild,visit);
        PreOrderTraverse(node -> rchild,visit);
    }
}
template <typename T>
void BinaryTree<T>::MidOrderTraverse(BitNode<T>* node,void (*visit)(T)) {
    if (node) {
        MidOrderTraverse(node -> lchild,visit);
        visit(node -> data);
        MidOrderTraverse(node -> rchild,visit);
    }
}
template <typename T>
void BinaryTree<T>::EndOrderTraverse(BitNode<T>* node,void (*visit)(T)) {
    if (node) {
        EndOrderTraverse(node -> lchild,visit);
        EndOrderTraverse(node -> rchild,visit);
        visit(node -> data);
    }
}
template <typename T>
void BinaryTree<T>::LevelOrderTraverse(void (* visit)(T)) {
    BitNode<T>* queue[2*count];
    BitNode<T> *tmp;
    int l = 0,r = 0;
    queue[r++] = this -> root;
    while (l < r) {
        tmp = queue[l++];
        visit(tmp -> data);
        if (tmp -> lchild != nullptr) {
            queue[r++] = tmp -> lchild;
        }
        if (tmp -> rchild != nullptr) {
            queue[r++] = tmp -> rchild;
        }
    }
}
template <typename T>
void BinaryTree<T>::PreOrderTraverseStack(void (*visit)(T)) {
    BitNode<T>* stack[2*count];
    BitNode<T>* tmp = this -> root;
    int l = 0;
    while ((tmp != nullptr) || l > 0) {
        while (tmp != nullptr) {
            visit(tmp -> data);
            stack[l++] = tmp;
            tmp = tmp -> lchild;
        }
        tmp = stack[--l];
        tmp = tmp -> rchild;
    }
}
template <typename T>
void BinaryTree<T>::MidOrderTraverseStack(void (*visit)(T)) {
    BitNode<T>* stack[2*count];
    BitNode<T>* tmp = this -> root;
    int l = 0;
    while ((tmp != nullptr) || l > 0) {
        while (tmp != nullptr) {
            stack[l++] = tmp;
            tmp = tmp -> lchild;
        }
        tmp = stack[--l];
        visit(tmp -> data);
        tmp = tmp -> rchild;
    }
}
template <typename T>
void BinaryTree<T>::CreateTree(BitNode<T> *&ptr) {
    T ch;
	ch=getchar();
	if(ch=='#') {
        ptr = nullptr;
	}
    else {
        count++;
        ptr=new BitNode<T>(ch);
        ptr -> data = ch;
		CreateTree(ptr->lchild);
		CreateTree(ptr->rchild);
    }
}
template <typename T>
void visit(T data) {
    cout << data << " ";
}
#endif

main.cpp测试

#include "binary_tree.h"
int main(int argc, char const *argv[])
{
    BinaryTree<char> tree;
	tree.CreateTree(tree.root);
    cout << "先序递归遍历" << endl;
    tree.Traverse(1,visit);
    cout << "中序递归遍历" << endl;
    tree.Traverse(2,visit);
    cout << "后序递归遍历" << endl;
    tree.Traverse(3,visit);
    cout << "层次遍历" << endl;
    tree.Traverse(4,visit);
    cout << "先序非递归遍历" << endl;
    tree.Traverse(5,visit);
    cout << "中序非递归遍历" << endl;
    tree.Traverse(6,visit);
    return 0;
}

5.测试截图

软件为vscode



其中第一行用于先序创建二叉树,二叉树的形状如下图所示