【算法学习4】树与二叉树基础

首先是部分树方面的概念

节点：节点包括一个数据元素及若干指向其他子树的分支。

叶节点：度为0的节点称为叶结点，叶结点也称为终端节点。

根节点：树的最顶端的节点称为根节点。

子节点：树中一个节点的子树的根节点称为该节点的孩子节点，即除根节点之外的节点都是其上一个节点的子节点。

分支节点：度不为0的节点称为分支节点，分支节点又称非终端节点。

一棵树中排除叶结点外的所有节点都是分支节点。

度：节点所拥有子树的个数称为节点的度，树中所有节点的度的最大值是树的度。

二叉树

二叉树是树中最重要的一种，也是我们最常用的树结构之一，即除叶节点之外每个节点都有且只有左（lchild）右（rchild）两个分支的树。

二叉树的用途

二叉树和链表、数组等结构一样可以用来储存数据，但是不同的是后者利用数据的存储位置进行访问，因此只能通过遍历进行数据的访问，二叉树则是按值保存元素，因此可以做到直接按值访问。

二叉树的分类

满二叉树：除了叶节点外，所以节点的左右节点都存在。

完全二叉树：所有子节点都从左到右，不存在间隔。

平衡二叉树：空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树也都是平衡树。

·二叉搜索树：空树或者二叉树的所有节点比他的左子节点大，比他的右子节点小。

（1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值。

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值。

（3）左右子树也是二叉搜索树。

·红黑树：不仅是具有二叉搜索树的属性，还具有平衡树的属性，有序且子树差不超过1，

二叉树的遍历

前序遍历 ：遍历路径：根节点 ——左节点——右节点。

中序遍历 ：遍历路径：左节点——根节点 ——右节点。

后序遍历 ：遍历路径：左节点——右节点——根节点 。

二叉树的C++实现

头文件：class.h

定义了二叉树的节点结构体和二叉树类，结构体中包含每个节点的数据和左右子树的指针，类中包含树的创建和树的前中后序遍历。

#ifndef CLASS_H
#define CLASS_H
#include
using namespace std;
using namespace std;

template 
struct BiNode
{
    int data;
    BiNode* lchild, * rchild;
};

template 
class BiTree
{
public:
    BiTree()
    {
        root = Create(root);
    }
    ~BiTree()
    {
        Release(root);
    }
    void PreOrder()      //前序遍历
    {
        PreOrder(root);
    }
    void InOrder()       //中序遍历
    {
        InOrder(root);
    }
    void PostOrder()     //后序遍历
    {
        PostOrder(root);
    }
private:
    BiNode* root;
    BiNode* Create(BiNode* bt);
    void PreOrder(BiNode* bt);
    void InOrder(BiNode* bt);
    void PostOrder(BiNode* bt);
};


#endif

文件 class.cpp

实现在头文件class.h的类中定义过的方法。

#include"class.h"
#include
#include

template 
BiNode*BiTree::Create(BiNode*bt)  //二叉树的创建
{
    int ch;
    cin >> ch;
    if (ch == '#')
    {
        bt = NULL;
    }
    else
    {
        bt = new BiNode;
        bt->data = ch;
        bt->lchild = Create(bt->lchild);
        bt->rchild = Create(bt->rchild);
    }
}

template 
void BiTree::PreOrder(BiNode* bt) //前序遍历
{
    if (bt == NULL) return;
    else {
        cout << bt->data;
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }

}

template 
void BiTree::InOrder(BiNode* bt) //中序遍历
{
    if (bt == NULL) return;
    else {
        PreOrder(bt->lchild);
        cout << bt->data;
        PreOrder(bt->rchild);
    }

}

template 
void BiTree::PostOrder(BiNode* bt)  //后序遍历
{
    if (bt == NULL) return;
    else
    {
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
        cout << bt->data;
    }
}

以上是主要代码段以及三种遍历的C++实现，可以根据具体问题进行灵活更改运用。