二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 [1] 。
2.结构模型图如上图为一个二叉树，父节点最多只能有两个子节点
二、常用函数- 求节点个数
- 求树的高度
- 求根节点
- 求当前节点的左孩子
- 求当前节点的右孩子
- 查找当前节点
- 查找当前节点的父节点
- 将二叉树置空
- 两个二叉树是否相同的比较
- 复制一个二叉树
- 前序遍历
- 中序遍历
- 后序遍历
- 层次遍历
- 前序法构建二叉树
binTree.h
#pragma once #include#include #include template //为的是声明友元类，调用BinTreeNode 的私有数据 class BinTree; template struct Node //二叉树结点，结构体 { friend class BinTree ; Type data; //数据 Node *leftChild, *rightChild; //分别为左孩子和右孩子 Node() : data(Type()), leftChild(nullptr), rightChild(nullptr) {} //无参构造 Node(Type value, Node *left = nullptr, Node *rigth = nullptr) //有参构造 { data = value; leftChild = left; rightChild = rigth; } ~Node(){}; }; template class BinTree //二叉树类 { private: Node *root; //指向二叉树的根 /以下为内部接口// private: //以下为内部接口 void clear(Node *t); int size(Node *t) const; int height(Node *t) const; int leafNum(Node *t) const; Node *findI(const Type &value, Node *t) const; //查找当前节点 Node *findParent(Node *child, Node *t) const; //查找当前节点的父节点 Node *copy(Node *t) const; //复制一个二叉树 bool equal(Node *t1, Node *t2) const; //两个二叉树是否相同的比较 void clear(Node *t); //清空二叉树 void preOrder(Node *t) const; //递归前序遍历 void inOrder(Node *t) const; //递归中序遍历 void postOrder(Node *t) const; //递归后序遍历 void preOrderCreate(Type flag, Node *&t); //前序法创建二叉树 //以下为外部接口 public: BinTree() : root(nullptr) {} ~BinTree() { clear(); } bool empty() const { return root == nullptr; } //判空 void clear() //清空 { if (root) clear(root); root = nullptr; } int size() const { return size(root); } //求结点个数 int height() const { return height(root); } //求二叉树高度 int leafNum() const { return leafNum(root); } //求二叉树叶子数 Node *findRoot() const { return root; } //求根节点 Node *findLeft(Node *t) const { return t->leftChild; } //求当前节点的左孩子 Node *findRight(Node *t) const { return t->rightChild; }; //求当前节点的右孩子 Node *findI(const Type &value) const { return findI(value, root); } //查找当前结点 Node *findParent(Node *child) const { return findParent(child, root); } //查找当前节点的父节点 Node *copy() const { return copy(root); }; //复制一个二叉树 bool equal(Node *t) const { return equal(root, t); } //两个二叉树是否相同的比较 void preOrderTraverse() const { preOrder(root); } //前序遍历 void inOrederTraverse() const { inOrder(root); } //中序遍历 void postOrderTraverse() const { postOrder(root); } //后序遍历 void preOrderCreate(Type flag) { preOrderCreate(flag, root); } //前序法创建二叉树 }; //以下为接口实现// template void BinTree ::clear(Node *t) //清空二叉树 { if (t->leftChild) { clear(t->leftChild); } //利用递归完成释放空间的功能 if (t->rightChild) { clear(t->rightChild); } delete t; } template int BinTree ::size(Node *t) const //返回返回结点个数 { if (t == nullptr) { return 0; } return 1 + size(t->leftChild) + size(t->rightChild); } template int BinTree ::height(Node *t) const //返回二叉树高度 { if (t == nullptr) { return 0; } else { int l = height(t->leftChild); int r = height(t->rightChild); return 1 + (l > r ? l : r); } } template int BinTree ::leafNum(Node *t) const //返回二叉树叶子数 { if (t == nullptr) { return 0; } else if (t->leftChild == nullptr && t->rightChild == nullptr) //根就是叶子的时候 { return 1; } else { return leafNum(t->leftChild) + leafNum(t->rightChild); } } template Node *BinTree ::findParent(Node *child, Node *t) const //查找当前节点的父节点 { if (t == nullptr || child == nullptr || child == t) { return nullptr; } if (t->leftChild == child || t->rightChild) { return t; } Node *p = findParent(t->leftChild); if (p) { return p; } return findParent(t->rightChild); } template Node *BinTree ::findI(const Type &value, Node *t) const //查找当前节点 { if (t == nullptr) return nullptr; if (t->data == value) return t; Node *p = findI(value, t->leftChild); if (p) return p; return findI(value, t->rightChild); } template Node *BinTree ::copy(Node *t) const //复制一个二叉树 { if (!t) { return nullptr; } Node *copyT = new Node (t->data); copyT->leftChild = copy(t->leftChild); copyT->rightChild = copy(t->rightChild); return copyT; } template void BinTree ::preOrder(Node *t) const //递归前序遍历 { if (t) { std::cout << t->data << ' '; //前序是从根开始遍历，所以输出语句放在第一条 preOrder(t->leftChild); preOrder(t->rightChild); } } template bool BinTree ::equal(Node *t1, Node *t2) const //两个二叉树是否相同的比较 { if (t1 == nullptr && t2 == nullptr) { return true; } if (t1 != nullptr && t2 != nullptr && t1->data == t2->data && equal(t1->leftChild, t2->leftChild) && equal(t1->rightChild, t2->rightChild)) { return true; } else { return false; } } template void BinTree ::inOrder(Node *t) const //递归中序遍历 { if (t) { inOrder(t->leftChild); std::cout << t->data << ' '; inOrder(t->rightChild); } } template void BinTree ::postOrder(Node *t) const //递归后序遍历 { if (t) { postOrder(t->leftChild); postOrder(t->rightChild); std::cout << t->data << ' '; } } template void BinTree ::preOrderCreate(Type flag, Node *&t) //前序法创建二叉树 { Type value; //键盘输入的值 std::cin >> value; //输入 if (value != flag) { t = new Node (value); preOrderCreate(flag, t->leftChild); preOrderCreate(flag, t->rightChild); } }
main.cpp
#include "binTree.h" #include四、总结using namespace std; void test01() { //测试的二叉树先序为：abd**eg***c*fh**i** BinTree t1; t1.preOrderCreate('*'); cout << "二叉树结点个数为：" << t1.size() << endl; cout << "二叉树高度为：" << t1.height() << endl; cout << "二叉树叶子数为：" << t1.leafNum() << endl; Node *iNode = t1.findI('c'); cout << "iNode->data = " << iNode->data << endl; cout << "元素c的父结点：" << t1.findParent(iNode)->data << endl; cout << "前序遍历二叉树t1："; t1.preOrderTraverse(); cout << "n中序遍历二叉树t1："; t1.inOrederTraverse(); cout << "n后序遍历二叉树t1："; t1.postOrderTraverse(); cout << endl; BinTree t2; t2.preOrderCreate('*'); bool p = t2.equal(t1.findRoot()); if (p) { cout << "相同！" << endl; } else { cout << "不相同！" << endl; } } int main() { test01(); return 0; }
二叉树是一种特殊的数，他有树形结构递归的性质特点，可以通过二叉树这种特殊的数存储数据。而二叉树的类型也有很多，比如线索二叉树、B二叉树和B+二叉树等等，同时它们也都有各自的特点。
