树是一种递归定义的数据结构，如果树中节点的各子树从左到右是有次序的，不能互换，则称该树为有序树，否则叫无序树。
关于树的节点：
- 节点拥有的子树的个数叫做节点的度
- 如果度为0，那么该节点叫做叶节点或终端节点，除了根节点外的分支节点称为内部节点
- 树的度是各节点度的最大值。节点的子树的根称为该节点的子节点，某个节点只能有一个父节点。
- 节点的子树的根称为该节点的子节点
- 节点的层次从树根开始计算，树的深度或高度是树中节点的最大层数
- 相同父节点的孩子之间互称兄弟节点
二叉树的特点是每个节点最多有两棵子树，这意味着每个节点的度不会大于2，并且是一棵有序树
关于满二叉树：
- 所有分支节点都存在左子树和右子树
- 所有叶节点都在同一层
- 不存在非0或非2的节点
- 高度为H，含有(2^H-1)个节点
关于完全二叉树：
- 叶节点在最底下两层
- 最后一层叶节点都靠左侧排列，除了最后一层，其他层的节点个数达到最大
- 倒数第二层如果有叶节点，则叶节点都靠右排列
- 如果节点度为 1，则该节点只有左子树，不可以只有右子树。而且最多只有一个度为 1 的节点
- 高度为 H，每个节点都与高度为 H 的满二叉树中编号为 1~n 的节点一一对应
由此可见，满二叉树一定是完全二叉树，反之不一定成立
判断完全二叉树：
- 按照满二叉树的情形给二叉树的节点逐层编号，编号出现空缺则不是完全二叉树
- 一棵满二叉树，依次把编号最大的 1 到多个节点去掉，得到的就是一棵完全二叉树
- 如果一个完全二叉树有 n 个节点，当节点的编号≤(n/2) 时，这些节点就是分支节点，而当节点的编号>(n/2) 时，这些节点就是叶节点(n/2 如果没有整除则去掉小数部分)
二叉树的性质：
- 在二叉树的第i层上，最多有2^(i-1)个节点
- 高度为K的二叉树至多有(2^K-1)个节点
- 二叉树节点的总数量等于节点的总度数+1
- 对于任何一棵二叉树，如果其叶节点数量为n0，度为 2 的节点数量为n2，则叶节点的数量比有两棵子树的节点数量多一个，即n0=n2+ 1
- 具有 n（n>0）个节点的完全二叉树的高度为⌈log2(n+1)⌉ 或者 ⌊log2n⌋ +1。
顺序存储
顺序存储方式用一段连续的内存单元依次从上到下、从左到右存储二叉树各个节点元素
假设存储的是一棵完全二叉树，如果将根节点存储在数组下标i=1的位置，则左子树下标为i*2=2的位置，右子树在3的位置
如果存储的是一棵非完全二叉树，也按照完全二叉树的编号来存储，但会浪费较多的内存空间
#include <iostream>
#include <cmath>
#define MaxSize 100
enum ECCHILDSIGN {
E_Root, // 树根
E_ChildLeft, // 左孩子
E_ChildRight // 右孩子
};
template <typename T>
struct BinaryTreeNode {
T data; // 数据域
bool isValid; // 节点是否有效
};
template <typename T>
class BinaryTree {
public:
BinaryTree() {
for (int i=0;i<=MaxSize;i++) {
// 初始时节点无效
SeqBiTree[i].isValid = false;
}
}
~BinaryTree() {};
public:
// 创建节点
int CreateNode(int parindex,ECCHILDSIGN pointSign,const T &e);
// 获取父节点下标
int getParentIdx(int sonindex) {
if (ifValidRangeIdx(sonindex) == false) {
return -1;
}
if (SeqBiTree[sonindex].isValid == false) {
return -1;
}
return int(sonindex / 2);
}
// 获取指定节点所在高度
int getPointLevel(int index) {
if (ifValidRangeIdx(index) == false) {
return -1;
}
if (SeqBiTree[index].isValid == false) {
return -1;
}
int level = int(log(index)/log(2)+1);
return level;
}
// 获取二叉树深度
int getLevel() {
if (SeqBiTree[1].isValid == false) {
return 0;
}
int i;
for (i = MaxSize;i >= 1;i--) {
// 找到最后一个有效节点
if (SeqBiTree[i].isValid == true) {
break;
}
}
return getPointLevel(i);
}
// 判断是否为完全二叉树
bool ifCompleteBT() {
if (SeqBiTree[1].isValid == false) {
return false;
}
int i;
for (i = MaxSize;i >= 1;i--) {
// 找到最后一个节点
if (SeqBiTree[i].isValid == true) {
break;
}
}
for (int k = 1;k <= i;k++) {
// 所有节点有效
if (SeqBiTree[k].isValid == false) {
return false;
}
}
return true;
}
void preOrder() {
if (SeqBiTree[1].isValid == false) {
return;
}
preOrder(1);
}
void preOrder(int index) {
if (ifValidRangeIdx(index) == false) {
return;
}
if (SeqBiTree[index].isValid == false) {
return;
}
std::cout << (char)SeqBiTree[index].data << "";
preOrder(2 * index);
preOrder(2 * index + 1);
}
private:
bool ifValidRangeIdx(int index) {
if (index < 1 || index > MaxSize) {
return false;
}
return true;
}
private:
BinaryTreeNode<T> SeqBiTree[MaxSize + 1];
};
template <class T>
int BinaryTree<T>::CreateNode(int parindex,ECCHILDSIGN pointSign,const T &e) {
if (pointSign != E_Root) {
if (ifValidRangeIdx(parindex) == false) {
return -1;
}
if (SeqBiTree[parindex].isValid == false) {
return -1;
}
}
int index = -1;
if (pointSign == E_Root) {
index = 1; // 根节点下标为1
} else if (pointSign == E_ChildLeft) {
// 左孩子
index = 2 * parindex;
if (ifValidRangeIdx(index) == false) {
return -1;
}
} else {
// 右孩子
index = 2 * parindex + 1;
if (ifValidRangeIdx(index) == false) {
return -1;
}
}
SeqBiTree[index].data = e;
// 标记该下标中有效数据
SeqBiTree[index].isValid = true;
return index;
}
int main(void) {
BinaryTree<int> tree;
int indexRoot = tree.CreateNode(-1,E_Root,'A');
int indexNodeB = tree.CreateNode(indexRoot,E_ChildLeft,'B');
int indexNodeC = tree.CreateNode(indexRoot,E_ChildRight,'C');
int indexNodeD = tree.CreateNode(indexNodeB,E_ChildLeft,'D');
int indexNodeE = tree.CreateNode(indexNodeC,E_ChildRight,'E');
int iParentIndexE = tree.getParentIdx(indexNodeE);
std::cout << "node E parent node index: " << iParentIndexE << std::endl;
int iLevel = tree.getPointLevel(indexNodeD);
std::cout << "the height of node D: " << iLevel << std::endl;
iLevel = tree.getPointLevel(indexNodeE);
std::cout << "the height of node E: " << iLevel << std::endl;
std::cout << "the depth of binary tree: " << tree.getLevel() << std::endl;
std::cout << "compelete binary tree: " << tree.ifCompleteBT() << std::endl;
std::cout << "-----------------" << std::endl;
std::cout << "preorder: ";
tree.preOrder();
return 0;
}
链式存储
链式存储要存储额外的左右子节点，多用于存储普通的二叉树
#include <iostream>
enum ECCHILDSIGN {
E_Root, // 树根
E_ChildLeft, // 左孩子
E_ChildRight // 右孩子
};
template <typename T>
struct BinaryTreeNode {
T data; // 数据域
BinaryTreeNode *leftChild;
BinaryTreeNode *rightChild;
};
template <typename T>
class BinaryTree {
public:
BinaryTree();
~BinaryTree();
public:
// 创建节点
BinaryTreeNode<T> *CreateNode(BinaryTreeNode<T> *parentnode,ECCHILDSIGN pointSign,const T &e);
void ReleaseNode(BinaryTreeNode<T> *pnode); // 释放树节点
void CreateBTreeAccordPT(char *pstr); // 前序遍历顺序创建BTree
public:
// 前序遍历
void preOrder() {
preOrder(root);
}
void preOrder(BinaryTreeNode<T> *tNode) {
if (tNode != nullptr) {
std::cout << (char)tNode->data << " ";
preOrder(tNode->leftChild);
preOrder(tNode->rightChild);
}
}
// 中序遍历
void inOrder() {
inOrder(root);
}
void inOrder(BinaryTreeNode<T> *tNode) {
if (tNode != nullptr) {
inOrder(tNode->leftChild);
std::cout << (char)tNode->data << " ";
inOrder(tNode->rightChild);
}
}
// 后序遍历
void postOrder() {
postOrder(root);
}
void postOrder(BinaryTreeNode<T> *tNode) {
if (tNode != nullptr) {
postOrder(tNode->leftChild);
postOrder(tNode->rightChild);
std::cout << (char)tNode->data << " ";
}
}
private:
BinaryTreeNode<T> *root;
void CreateBTreeAccordPTRecu(BinaryTreeNode<T>* &tnode,char* &pstr);
};
template <class T>
BinaryTree<T>::BinaryTree() {
root = nullptr;
}
template <class T>
BinaryTree<T>::~BinaryTree() {
ReleaseNode(root);
}
template <class T>
void BinaryTree<T>::ReleaseNode(BinaryTreeNode<T> *pnode) {
if (pnode != nullptr) {
ReleaseNode(pnode->leftChild);
ReleaseNode(pnode->rightChild);
}
delete pnode;
}
template <class T>
BinaryTreeNode<T> *BinaryTree<T>::CreateNode(BinaryTreeNode<T> *parentnode,ECCHILDSIGN pointSign,const T &e) {
BinaryTreeNode<T> *tmpnode = new BinaryTreeNode<T>;
tmpnode->data = e;
tmpnode->leftChild = nullptr;
tmpnode->rightChild = nullptr;
if (pointSign == E_Root) {
root = tmpnode;
}
if (pointSign == E_ChildLeft) {
parentnode->leftChild = tmpnode;
} else if (pointSign == E_ChildRight) {
parentnode->rightChild = tmpnode;
}
return tmpnode;
}
template <class T>
void BinaryTree<T>::CreateBTreeAccordPT(char *pstr) {
CreateBTreeAccordPTRecu(root,pstr);
}
template <class T>
void BinaryTree<T>::CreateBTreeAccordPTRecu(BinaryTreeNode<T> *&tnode,char *&pstr) {
if (*pstr == '#') {
tnode = nullptr;
} else {
tnode = new BinaryTreeNode<T>;
tnode->data = *pstr;
CreateBTreeAccordPTRecu(tnode->leftChild,++pstr);
CreateBTreeAccordPTRecu(tnode->rightChild,++pstr);
}
}
int main(void) {
BinaryTree<int> tree;
BinaryTreeNode<int> *rootpoint = tree.CreateNode(nullptr,E_Root,'A');
BinaryTreeNode<int> *subpoint = tree.CreateNode(rootpoint,E_ChildLeft,'B');
subpoint = tree.CreateNode(subpoint,E_ChildLeft,'D');
subpoint = tree.CreateNode(rootpoint,E_ChildRight,'C');
subpoint = tree.CreateNode(subpoint,E_ChildRight,'E');
// tree.CreateBTreeAccordPT((char*)"ABD###C#E##"); // 直接通过前序遍历创建二叉树
std::cout << "preorder: ";
tree.preOrder();
std::cout << std::endl;
std::cout << "inorder: ";
tree.inOrder();
std::cout << std::endl;
std::cout << "postorder: ";
tree.postOrder();
std::cout << std::endl;
return 0;
}
