一、二叉树的相关概念
概念：二叉树是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;
}
