美文网首页
二叉树的基本概念与遍历方法实现

二叉树的基本概念与遍历方法实现

作者: 曲谐_ | 来源:发表于2017-07-21 09:38 被阅读0次

一、二叉树的相关概念

概念:二叉树是n个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两颗互不相交的,分别称为根结点的的左子树和右子树的二叉树组成。
理解:二叉树是一个包含递归概念的树,每个结点下面的左子树和右子树依旧包含二叉树。

二叉树的特点:

  • 每个结点最多有两颗子树。
  • 左子树和右子树顺序不能颠倒。

二叉树的形态:

  • n=0,空树。
  • n=1,只有一个根结点。
  • 根节点只有左子树。
  • 根结点只有右子树。
  • 左子树和右子树都有。

特殊二叉树:

  • 满二叉树:所有分支节点都存在左子树和右子树,并且所有叶子都在同一层上。
  • 完全二叉树: 给一个具有n个结点的二叉树编号(从左到右),如果这n个结点是满二叉树的前n个结点(中间无空隙),则可以称之为完全二叉树。

完全二叉树的特点:

  • 叶子节点只能出现在在最下两层。
  • 最下层的叶子一定集中在左部连续位置。
  • 倒数二层,若有叶子节点,一定都在右部连续位置。
  • 如果结点度为1,则一定为左孩子。
  • 同样结点的二叉树,完全二叉树的深度最小。

二叉树的性质:

1)在二叉树的第i层上至多有2i-1个结点。
2)深度为k的二叉树至多有2k-1个结点。
3)对任何一颗二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。
4)具有n个结点的完全二叉树的深度为[log2n]+1(方括号为向下取整函数)。
5)如果对一颗有n个结点的完全二叉树(其深度为[log2n]+1)的结点按层序编号(从第1层到第[log2n]+1层,每层从左到右),对任一结点i(1<=i<=n)有:

  • 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是结点[i/2]。(括号含义同上)
  • 如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i。
  • 如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1。

二、二叉树遍历代码实现

//Binarytree.h

#ifndef BINARYTREE_H_
#define BINARYTREE_H_
struct BtreeNode
{
    char alpha;
    BtreeNode * lchild;
    BtreeNode * rchild;
};
class BinaryTree
{
private:
    BtreeNode * root;//树的根或子树的根
public:
    BinaryTree();
    ~BinaryTree();
    BtreeNode * Create();
    BtreeNode * Getroot();
    void Release(BtreeNode * root);
    void PreOrder(BtreeNode * root);//前序遍历
    void InOrder(BtreeNode * root);//中序遍历
    void PostOrder(BtreeNode * root);//后序遍历
    void LayerOrder(BtreeNode * root);//层序遍历
    int BinaryTreeNodeNum();//返回二叉树的结点数
    int BinaryTreeLeaves();//返回二叉树的叶子结点数
    int Depth();
};
#endif

//Binarytree.cpp

#include<iostream>
#include"BinaryTree.h"
using std::cout;
using std::endl;
using std::cin;
BinaryTree::BinaryTree()
{
    this->root = Create();
}
BinaryTree::~BinaryTree()
{
    this->Release(root);
}
BtreeNode * BinaryTree::Create()//创建过程为顺序遍历。
{
    BtreeNode * root;
    char ch;
    cout << "输入一个字符:";
    cin >> ch;
    if (ch == '#')
        root = NULL;//空指针并没有内存,加一个#是为了在电脑上让二叉树返回。毕竟有的二叉树会缺少lchild或rchild。
    else
    {
        root = new BtreeNode;
        root->alpha = ch;
        root->lchild = Create();
        root->rchild = Create();
    }
    return root;
}
BtreeNode * BinaryTree::Getroot()
{
    return this->root;
}
void BinaryTree::Release(BtreeNode * root)//后序遍历
{
    if(root!=NULL)
    {
        Release(root->lchild);
        Release(root->rchild);
        delete root;
    }
}
void BinaryTree::PreOrder(BtreeNode * root)
{
    if (root == NULL)
        return;
    cout << root->alpha << " ";
    PreOrder(root->lchild);
    PreOrder(root->rchild);
}
void BinaryTree::InOrder(BtreeNode * root)
{
    if (root == NULL)
        return;
    InOrder(root->lchild);
    cout << root->alpha << " ";
    InOrder(root->rchild);
}
void BinaryTree::PostOrder(BtreeNode * root)
{
    if (root == NULL)
        return;
    PostOrder(root->lchild);
    PostOrder(root->rchild);
    cout << root->alpha << " ";;
}
void BinaryTree::LayerOrder(BtreeNode * root)
{
    const int Maxsize = 100;
    int front = 0;
    int rear = 0;
    BtreeNode * Q[Maxsize];
    BtreeNode * q;
    if (root == NULL)
        return;
    else
    {
        Q[rear++] = root;
        while (front!=rear)
        {
            q = Q[front++];
            cout << q->alpha << " ";
            if(q->lchild!=NULL)
                Q[rear++] = q->lchild;
            if(q->rchild!=NULL)
                Q[rear++] = q->rchild;
        }
    }
}
//设计一个结点数组Q,用来分层保存二叉树中的结点;再设计一个临时结点q,用来打印当前结点。
//Q[front]赋值给q,表示当前要打印的结点数据;Q[rear]表示目前层序遍历的最后一个结点数据。
//当front==rear时,表示已经打印到了最后一个。、
//相当于把根结点的子树从左到右遍历,再把左子树从左到右遍历,再把右子树从左到右遍历,从而达到层序遍历。

//main.cpp

#include<iostream>
#include"BinaryTree.h"
using namespace std;
int main()
{
    BinaryTree Btree;
    BtreeNode * root = Btree.Getroot();
    cout << "前序遍历: " << endl;
    Btree.PreOrder(root);
    cout << endl;
    cout << "中序遍历: " << endl;
    Btree.InOrder(root);
    cout << endl;
    cout << "后序遍历: " << endl;
    Btree.PostOrder(root);
    cout << endl;
    cout << "层序遍历: " << endl;
    Btree.LayerOrder(root);
    cout << endl;
    return 0;
}

相关文章

  • 二叉树的各种遍历方法

    二叉树的常用遍历方法 二叉树常用的遍历方法包括: 前序遍历 中序遍历 后序遍历 层次遍历 而前三种遍历的具体实现上...

  • 数据结构基础--二叉树

    本文主要作为自己的学习笔记,并不具备过多的指导意义。 目录 基本概念 二叉树的重点 二叉树的遍历 实现先序遍历 实...

  • 二叉树遍历

    二叉树遍历 二叉树遍历分为先序中序后序,是否递归,实现方法和原理注释都在下方

  • 数据结构与算法二叉树的遍历与线索二叉树以及森林

    1.二叉树的遍历先序遍历、中序遍历、后序遍历 2.层次遍历利用队列实现 3.由遍历序列构成二叉树先序、后序可以与众...

  • 经典算法——二叉树遍历问题

    姓名:谭旭东 学号:19011210016 一、基本概念 二叉树有一般有三种遍历方法:根据遍历顺序不同而区分 前序...

  • Java二叉树的遍历

    Java二叉树的遍历 利用递归和非递归实现二叉树的先序,中序,后序遍历以及使用队列实现二叉树的层次遍历

  • 算法精选题总结之二叉树类

    1.二叉树的中序遍历中序遍历的迭代方法中序遍历的递归方法2.二叉树前序遍历3.二叉树后续遍历4.二叉树的最近公共祖...

  • 二叉树的三种深度优先遍历算法与思路

    看了一些关于二叉树遍历算法的文章,例如:二叉树三种遍历方式的递归和循环实现二叉树的递归与非递归遍历(前序、中序、后...

  • 算法之二叉树

    二叉树之C++实现 创建二叉树 复制二叉树 先序遍历 递归实现 非递归实现 中序遍历 递归实现 非递归实现 后序遍...

  • 二叉树的基本概念与遍历方法实现

    一、二叉树的相关概念 概念:二叉树是n个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两颗互不相...

网友评论

      本文标题:二叉树的基本概念与遍历方法实现

      本文链接:https://www.haomeiwen.com/subject/jiuskxtx.html