数据结构二叉树

桃扇骨 2022-04-18 00:29 195阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

# 二叉树的定义 #

**二叉树**（BinaryTree）是n（n>=0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵互不相交的、分别称作这个根的**左子树**和**右子树**的二叉树组成。

# 二叉树的性质    #

性质1　**二叉树第i层上的结点数目最多为2i-1(i≥1)。**  
证明：

用数学归纳法证明。  
　　归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。  
　　归纳假设：假设对所有的j（1≤j<i）命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。  
　　归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。  
  
性质2　**深度为k的二叉树至多有2k\-1个结点(k≥1)。**  
证明：

在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：  
　　　　20\+21\+…+2k-1=2k\-1  
　　故命题正确。  
  
性质3　**在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2\+1。**  
证明：

因为二叉树中所有结点的度数均不大于2，所以结点总数（记为n）应等于0度结点数n0、1度结点数n1和2度结点数n2之和，即

n=n0\+n1\+n2　（式子1）

另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是n1\+2n2，而树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为

n=n1\+2n2\+1　（式子2）

由式子1和式子2得到：

n0=n2\+1

# 二叉树的实现（C++） #

#include <iostream>#define NULL 0using namespace std;template<class T>struct BTNode{
          T data; BTNode<T> *lChild, *rChild; BTNode(); BTNode(const T &val, BTNode<T> *Childl = NULL, BTNode<T> *Childr = NULL) {  data = val;  lChild = Childl;  rChild = Childr; } BTNode<T>* CopyTree() {  BTNode<T> *l, *r, *n;  if(&data == NULL)  {   return NULL;  }  l = lChild->CopyTree();  r = rChild->CopyTree();  n = new BTNode<T>(data, l, r);  return n; }};template<class T>BTNode<T>::BTNode(){ lChild = rChild = NULL;}template<class T>class BinaryTree{
         public: BTNode<T> *root; BinaryTree(); ~BinaryTree(); void Pre_Order(); void In_Order(); void Post_Order(); int TreeHeight() const; int TreeNodeCount() const; void DestroyTree(); BTNode<T>* MakeTree(const T &element, BTNode<T> *l, BTNode<T> *r) {  root = new BTNode<T> (element, l, r);  if(root == NULL)  {   cout << "Failure for applying storage address, system will close the process." << endl;   exit(1);  }  return root; }private: void PreOrder(BTNode<T> *r); void InOrder(BTNode<T> *r); void PostOrder(BTNode<T> *r); int Height(const BTNode<T> *r) const; int NodeCount(const BTNode<T> *r) const; void Destroy(BTNode<T> *&r);};template<class T>BinaryTree<T>::BinaryTree(){ root = NULL;}template<class T>BinaryTree<T>::~BinaryTree(){ DestroyTree();}template<class T>void BinaryTree<T>::Pre_Order(){ PreOrder(root);}template<class T>void BinaryTree<T>::In_Order(){ InOrder(root);}template<class T>void BinaryTree<T>::Post_Order(){ PostOrder(root);}template<class T>int BinaryTree<T>::TreeHeight() const{ return Height(root);}template<class T>int BinaryTree<T>::TreeNodeCount() const{ return NodeCount(root);}template<class T>void BinaryTree<T>::DestroyTree(){ Destroy(root);}template<class T>void BinaryTree<T>::PreOrder(BTNode<T> *r){ if(r != NULL) {  cout << r->data << ' ';  PreOrder(r->lChild);  PreOrder(r->rChild); }}template<class T>void BinaryTree<T>::InOrder(BTNode<T> *r){ if(r != NULL) {  InOrder(r->lChild);  cout << r->data << ' ';  InOrder(r->rChild); }}template<class T>void BinaryTree<T>::PostOrder(BTNode<T> *r){ if(r != NULL) {  PostOrder(r->lChild);  PostOrder(r->rChild);  cout << r->data << ' '; }}template<class T>int BinaryTree<T>::NodeCount(const BTNode<T> *r) const{ if(r == NULL) {  return 0; } else {  return 1 + NodeCount(r->lChild) + NodeCount(r->rChild); }}template<class T>int BinaryTree<T>::Height(const BTNode<T> *r) const{ if(r == NULL) {  return 0; } else {  int lh, rh;  lh = Height(r->lChild);  rh = Height(r->rChild);  return 1 + (lh>rh?lh:rh); }}template<class T>void BinaryTree<T>::Destroy(BTNode<T> *&r){ if(r != NULL) {  Destroy(r->lChild);  Destroy(r->rChild);  delete r;  r = NULL; }}void main(){ BTNode<char> *b, *c, *d, *e, *f, *g; BinaryTree<char> a; b = a.MakeTree('F', NULL, NULL); c = a.MakeTree('E', NULL, NULL); d = a.MakeTree('D', NULL, NULL); e = a.MakeTree('C', b, NULL); f = a.MakeTree('B', d, c); g = a.MakeTree('A', f, e); cout << "Pre Order: "; a.Pre_Order(); cout << endl; cout << "In Order: "; a.In_Order(); cout << endl; cout << "Post Order: "; a.Post_Order(); cout << endl; cout << "Tree Height: "; cout << a.TreeHeight(); cout << endl; cout << "The Count of Tree Nodes: "; cout << a.TreeNodeCount(); cout << endl;}// Output:/*Pre Order: A B D E C FIn Order: D B E A F CPost Order: D E B F C ATree Height: 2The Count of Tree Nodes: 6*/

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[SouthEast]: /images/20220418/f9bfc31891764267a7e8dca829b3a653.png