什么是二叉树
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。
一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
二叉树的节点定义
typedef struct BTree
{
int value;
BTree* pLeft;
BTree* pRight;
};代码实现
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;
typedef struct BTree
{
int value;
struct BTree *pLeft;
struct BTree *pRight;
}BTree;
/*
前序遍历建立二叉树，0代表NULL
{1,2,4,8,0,0,9,0,0,5,0,0,3,6,0,0,9,0,0}
*/
BTree *CreateBTree(BTree * node,int *num,int &index)
{
if (num[index] == 0 )
{
return NULL;
}
else
{
node = new BTree;
node->value = num[index];
node->pLeft = CreateBTree(node->pLeft,num,++index);
node->pRight = CreateBTree(node->pRight,num,++index );
}
return node;
}
void Visit(BTree *node)
{
cout<<node->value<<ends;
}
/*
前序遍历
定义： 先访问根节点，在访问左子树，最后访问右子树；
*/
void PreorderTraverse( BTree *pRoot)
{
if( pRoot == NULL )
return ;
Visit( pRoot);
PreorderTraverse( pRoot->pLeft );
PreorderTraverse( pRoot->pRight);
}
/*
根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，
因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：
对于任一结点P：
1)访问结点P，并将结点P入栈;
2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);
若不为空，则将P的左孩子置为当前的结点P;
3)直到P为NULL并且栈为空，则遍历结束。
*/
void preOrder2(BTree *root) //非递归前序遍历
{
stack<BTree*> s;
BTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->value<<" ";
s.push(p);
p=p->pLeft;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->pRight;
}
}
}
/*
中序遍历
定义：首先访问左子树，然后访问根节点，最后访问右子树
*/
void InorderTraverse( BTree *pRoot)
{
if( pRoot == NULL )
return ;
InorderTraverse( pRoot->pLeft );
Visit( pRoot);
InorderTraverse( pRoot->pRight);
}
/*
非递归实现
根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，
直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：
对于任一结点P，
1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束
*/
void inOrder2(BTree *root) //非递归中序遍历
{
stack<BTree*> s;
BTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->pLeft;
}
if(!s.empty())
{
p=s.top();
cout<<p->value<<" ";
s.pop();
p=p->pRight;
}
}
}
/*
后序遍历
定义： 给定根节点，首先遍历左子树，然后遍历右子树，最后遍历根节点
*/
void PostorderTraverse( BTree *pRoot)
{
if( pRoot == NULL )
return ;
PostorderTraverse( pRoot->pLeft );
PostorderTraverse( pRoot->pRight);
Visit( pRoot);
}
/*
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不
存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子
都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次
入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在
根结点前面被访问。
*/
void postOrder3(BTree *root) //非递归后序遍历
{
stack<BTree*> s;
BTree *cur; //当前结点
BTree *pre=NULL; //前一次访问的结点
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->pLeft==NULL&&cur->pRight==NULL)||
(pre!=NULL&&(pre==cur->pLeft||pre==cur->pRight)))
{
cout<<cur->value<<" "; //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop();
pre=cur;
}
else
{
if(cur->pRight!=NULL)
s.push(cur->pRight);
if(cur->pLeft!=NULL)
s.push(cur->pLeft);
}
}
}
/*
二叉树的销毁
后序遍历销毁
*/
void ReleaseBTree(BTree *&pRoot)
{
if (pRoot == NULL)
{
return;
}
ReleaseBTree(pRoot->pLeft);
ReleaseBTree(pRoot->pRight);
cout<<pRoot->value<<ends;
delete pRoot;
pRoot = NULL;
}
/*
从上至下分层遍历二叉树
第一步：需要借助队列，首先将根节点pRoot入队；
第二步：当队列不空时，获得队首元素并出队，赋给pRoot，执行第三步；
第三步：如果pRoot左节点存在，则入队；如果pRoot右节点存在，则入队；执行第二步。
*/
void LevelTraverse( BTree *pRoot)
{
if (pRoot == NULL)
{
return;
}
queue<BTree *> queueBTree;
queueBTree.push(pRoot);
while(queueBTree.size())
{
BTree* node = queueBTree.front();
queueBTree.pop();
Visit(node);
if (node->pLeft)
{
queueBTree.push(node->pLeft);
}
if (node->pRight)
{
queueBTree.push(node->pRight);
}
}
}
/*
从上至下分层遍历二叉树 且每一层打印一行
*/
void LevelTraverseByRow( BTree *pRoot)
{
if (pRoot == NULL)
{
return;
}
queue<BTree *> queueBTree;
queueBTree.push(pRoot);
int nextLevel = 0;
int toBePrinted = 1;
while(queueBTree.size())
{
BTree* node = queueBTree.front();
queueBTree.pop();
Visit(node);
if (node->pLeft)
{
queueBTree.push(node->pLeft);
nextLevel++;
}
if (node->pRight)
{
queueBTree.push(node->pRight);
nextLevel++;
}
toBePrinted --;
if (toBePrinted == 0)
{
cout<<endl;
toBePrinted = nextLevel;
nextLevel = 0;
}
}
}
/*
按照之字形上至下分层 打印二叉树
*/
void ZigzagPrint(BTree *pRoot)
{
if (pRoot == NULL)
{
return;
}
queue<BTree *> queueBTree;
queueBTree.push(pRoot);
int nextLevel = 0;
int toBePrinted = 1;
vector<vector<int>> rows;
vector<int> curRow;
while(queueBTree.size())
{
BTree* node = queueBTree.front();
queueBTree.pop();
curRow.push_back(node->value);
if (node->pLeft != NULL)
{
queueBTree.push(node->pLeft);
nextLevel ++;
}
if (node->pRight != NULL)
{
queueBTree.push(node->pRight);
nextLevel ++;
}
toBePrinted--;
if (toBePrinted == 0)
{
toBePrinted = nextLevel;
nextLevel = 0;
rows.push_back(curRow);
curRow.clear();
}
}
for (int i =0 ;i < rows.size();i++)
{
if (i %2 == 0)
{
for (int j = 0; j < rows[i].size();j ++)
{
cout<<rows[i][j]<<ends;
}
cout<<endl;
}
else
{
for (int j = rows[i].size() - 1; j >= 0;j --)
{
cout<<rows[i][j]<<ends;
}
cout<<endl;
}
}
}
void ZigzagPrint_2(BTree *pRoot)
{
if (pRoot == NULL)
{
return;
}
queue<BTree *> queueBTree;
queueBTree.push(pRoot);
int nextLevel = 0;
int toBePrinted = 1;
vector<int> curRow;
while(queueBTree.size())
{
BTree* node = queueBTree.front();
queueBTree.pop();
curRow.push_back(node->value);
if (node->pLeft != NULL)
{
queueBTree.push(node->pLeft);
nextLevel ++;
}
if (node->pRight != NULL)
{
queueBTree.push(node->pRight);
nextLevel ++;
}
toBePrinted--;
if (toBePrinted == 0)
{
static bool flag = false;
flag = !flag /*(flag == false) ? true : false*/;
toBePrinted = nextLevel;
nextLevel = 0;
if (flag)
{
for (int j = 0; j < curRow.size();j ++)
{
cout<<curRow[j]<<ends;
}
cout<<endl;
}
else
{
for (int j = curRow.size() - 1; j >= 0;j --)
{
cout<<curRow[j]<<ends;
}
cout<<endl;
}
curRow.clear();
}
}
}
/*
求二叉树深度
定义：对任意一个子树的根节点来说，它的深度=左右子树深度的最大值+1
如果根节点为NULL，则深度为0
如果根节点不为NULL，则深度=左右子树的深度的最大值+1
*/
int GetBTreeDepth(BTree *pRoot)
{
if (pRoot == NULL)
{
return 0;
}
int nLeft = GetBTreeDepth(pRoot->pLeft);
int nRight = GetBTreeDepth(pRoot->pRight);
return (nLeft > nRight) ? (nLeft + 1): (nRight + 1);
}
/*
判断是否是平衡二叉树
在遍历每个节点的时候，调用GetBTreeDepth获取左右的深度，判断结果的差值
但是重复率比较高，效率低下
*/
bool IsBalanced(BTree *pRoot)
{
if (NULL == pRoot)
{
return true;
}
int nLeft = GetBTreeDepth(pRoot->pLeft);
int nRight = GetBTreeDepth(pRoot->pRight);
if (abs(nLeft - nRight) > 1)
{
return false;
}
return IsBalanced(pRoot->pLeft) && IsBalanced(pRoot->pRight);
}
/*
由于上述方法在求该结点的的左右子树深度时遍历一遍树，再次判断子树的平衡性时又遍历一遍树结构，
造成遍历多次。因此方法二是一边遍历树一边判断每个结点是否具有平衡性。
*/
bool IsBalanced(BTree *pRoot,int &Depth)
{
if (pRoot == NULL)
{
Depth = 0;
return true;
}
int nLeft;
int nRight;
if (IsBalanced(pRoot->pLeft,nLeft) && IsBalanced(pRoot->pRight,nRight))
{
if (abs(nLeft - nRight) <= 1)
{
Depth = 1 + ((nRight > nLeft) ? nRight : nLeft);
return true;
}
}
return false;
}
/*
判断是否是平衡二叉树 不允许重复遍历
*/
bool IsBalancedWithoutRepeat(BTree *pRoot)
{
int nDepth = 0;
return IsBalanced(pRoot,nDepth);
}
/*
二叉树叶子节点数
叶子节点：即没有左右子树的结点
如果给定节点pRoot为NULL，则是空树，叶子节点为0，返回0；
如果给定节点pRoot左右子树均为NULL，则是叶子节点，且叶子节点数为1，返回1；
如果给定节点pRoot左右子树不都为NULL，则不是叶子节点，
以pRoot为根节点的子树叶子节点数=pRoot左子树叶子节点数+pRoot右子树叶子节点数
*/
int GetBTreeLeafNodesTotal(BTree *pRoot)
{
if (pRoot == NULL)
{
return 0;
}
if (pRoot->pLeft == NULL && pRoot->pRight == NULL)
{
return 1;
}
return GetBTreeLeafNodesTotal(pRoot->pLeft) + GetBTreeLeafNodesTotal(pRoot->pRight);
}
/*
求二叉树第K层的节点数
给定根节点pRoot：
如果pRoot为空，或者层数KthLevel <= 0，则为空树或者不合要求，则返回0；
如果pRoot不为空，且此时层数KthLevel==1，则此时pRoot为第K层节点之一，则返回1；
如果pRoot不为空，且此时层数KthLevel > 1，则此时需要求pRoot左子树（KthLevel - 1 ）层节点数和pRoot右子树（KthLevel-1）层节点数；
*/
int GetBTreeKthLevelNodesTotal( BTree *pRoot, int KthLevel)
{
if (pRoot == NULL || KthLevel <= 0)
{
return 0;
}
if (pRoot != NULL && KthLevel == 1)
{
return 1;
}
return GetBTreeKthLevelNodesTotal(pRoot->pLeft,KthLevel - 1)
+ GetBTreeKthLevelNodesTotal(pRoot->pRight,KthLevel - 1);
}
/*
求二叉树第K层叶子节点数
给定节点pRoot：
如果pRoot为空，或者层数KthLevel <= 0, 则为空树或者是层数非法，则返回0；
如果pRoot不为空，且此时层数KthLevel==1时，需要判断是否为叶子节点：
如果pRoot左右子树均为空，则pRoot为第K层叶子节点之一，则返回1；
如果pRoot左右子树之一存在，则pRoot不是叶子节点，则返回0；
如果pRoot不为空，且此时层数KthLevel > 1，需要返回 KthLevel-1层的左子树和右子树结点数。
*/
int GetBTreeKthLevelLeafNodesTotal( BTree *pRoot, int KthLevel)
{
if (pRoot == NULL || KthLevel <= 0)
{
return 0;
}
if (pRoot != NULL && KthLevel == 1)
{
if (pRoot->pLeft == NULL && pRoot->pRight == NULL)
{
return 1;
}
else
{
return 0;
}
}
return GetBTreeKthLevelLeafNodesTotal(pRoot->pLeft,KthLevel - 1)
+ GetBTreeKthLevelLeafNodesTotal(pRoot->pRight,KthLevel - 1);
}
/*
比较两个二叉树结构是否相同，不涉及存储的数据
如果两个二叉树pRoot都为空树，则自然相同，返回true；
如果两个二叉树pRoot一个为空树，另一个不为空树，则不相同，返回false；
如果两个二叉树都不为空树，则需要分别比较左右子树后，根据比较结果共同判定，只要有一个为false，则返回false。
*/
bool BTreeCompare( BTree *pRoot1, BTree *pRoot2)
{
if (pRoot1 == NULL && pRoot2 == NULL)
{
return true;
}
if ((pRoot1 == NULL && pRoot2 != NULL) ||
(pRoot1 != NULL && pRoot2 == NULL))
{
return false;
}
bool bLeft = BTreeCompare(pRoot1->pLeft,pRoot2->pLeft);
bool bRight = BTreeCompare(pRoot1->pRight,pRoot2->pRight);
return (bLeft && bRight);
}
/*
求二叉树镜像
如果pRoot为NULL，则为空树，返回；
如果pRoot不为NULL，交换pRoot左右结点，然后分别求左右子树的镜像；
*/
void BTreeMirror( BTree *pRoot)
{
if (pRoot == NULL)
{
return ;
}
BTree * pTemp = pRoot->pLeft;
pRoot->pLeft = pRoot->pRight;
pRoot->pRight = pTemp;
BTreeMirror(pRoot->pLeft);
BTreeMirror(pRoot->pRight);
}
/*
判断二叉树是否对称
左右子树同时遍历，若出现不一致，则说明不对称。
*/
bool IsSymmetrical(BTree *pRoot1,BTree *pRoot2)
{
if (pRoot1 == NULL && pRoot2 == NULL)
{
return true;
}
if (pRoot1 == NULL && pRoot2 != NULL)
{
return false;
}
if (pRoot1 != NULL && pRoot2 == NULL)
{
return false;
}
return IsSymmetrical(pRoot1->pLeft,pRoot2->pRight)&&
IsSymmetrical(pRoot1->pRight,pRoot2->pLeft);
}
bool IsSymmetrical(BTree *pRoot)
{
return IsSymmetrical(pRoot,pRoot);
}
/*
查找二叉树中两个节点的最低祖先节点（或最近公共父节点等）
如果给定pRoot是NULL，即空树，则返回的公共节点自然就是NULL；
如果给定pRoot与两个节点中任何一个相同，说明，pRoot在就是所要找的两个节点之一，则直接返回pRoot，表明在当前链路中找到至少一个节点；
如果给定pRoot不是两个节点中任何一个，则说明，需要在pRoot的左右子树中重新查找，此时有三种情况：两个节点都在左子树上；两个节点都在右子树上；一个在左子树，一个在右子树上；具体来说，就是：
情况一：如果左子树查找出的公共节点是NULL，则表明从左子树根节点开始到左子树的所有叶子节点等所有节点中，没有找到两个节点中的任何一个，这就说明，这两个节点不在左子树上，不在左子树，则必定在右子树上；
情况二：如果右子树查找的公共节点是NULL，说明在右子树中无法找到任何一个节点，则两个节点必定在左子树上；
情况三： 如果左右子树查找的公共节点都不是NULL，说明左右子树中各包含一个节点，则当前节点pRoot就是最低公共节点，返回就可以了。
三种情况是互斥的， 只能是其中之一。
*/
BTree *GetLastCommonParent( BTree *pRoot, int key1, int key2)
{
if( pRoot == NULL ) //说明是空树，不用查找了，也就找不到对应节点，则返回NULL
return NULL;
if( pRoot->value == key1 || pRoot->value == key2 )//说明在当前子树的根节点上找到两个节点之一
return pRoot;
BTree *pLeft = GetLastCommonParent( pRoot->pLeft, key1, key2); //左子树中的查找两个节点并返回查找结果
BTree *pRight = GetLastCommonParent( pRoot->pRight, key1, key2);//右子树中查找两个节点并返回查找结果
if( pLeft == NULL )//如果在左子树中没有找到，则断定两个节点都在右子树中，可以返回右子树中查询结果；否则，需要结合左右子树查询结果共同断定
return pRight;
if ( pRight == NULL )//如果在右子树中没有找到，则断定两个节点都在左子树中，可以返回左子树中查询结果；否则，需要结合左右子树查询结果共同断定
return pLeft;
return pRoot;//如果在左右子树中都找两个节点之一，则pRoot就是最低公共祖先节点，返回即可。
}
/*
求父节点与子节点之间的距离
前序遍历二叉树 获取距离
*/
bool GetLenBetweenParentAndSon(BTree *pParent,int key,int path,int &result)
{
if (pParent == NULL)
{
return false;
}
if (pParent->value == key)
{
result = path;
return true;
}
bool bRtn = GetLenBetweenParentAndSon(pParent->pLeft,key,++path,result);
if(bRtn == false)
GetLenBetweenParentAndSon(pParent->pRight,key,path,result);
return false;
}
/*
二叉树中任意两个节点之间的距离
根本上是求二叉树中任意两个节点的最近祖先节点（最近公共父节点），
求出最近祖先节点之后，由最近祖先节点到这两个节点的距离之和就是。
首先根据递归方式求出最近祖先节点；
然后根据递归方式，从最近祖先节点通过前序遍历方式遍历到给定节点，找到路径，
同时计算出距离即可（本处距离可以认为是两节点之间的边可以看成是单位1）
*/
int GetLenBetweenNodes( BTree *pRoot, int key1, int key2)
{
BTree * pCommonParent = GetLastCommonParent(pRoot,key1,key2);
int path1 = 0,path2 = 0;
int result1,result2;
GetLenBetweenParentAndSon(pCommonParent,key1,path1,result1);
GetLenBetweenParentAndSon(pCommonParent,key2,path2,result2);
return result1 + result2;
}
/***************************二叉搜索树*************************************
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）
它或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。
*********************************************************************/
/*
二叉搜索树的查找
递归查找二叉排序树T中是否存在key,
指针f指向T的双亲，其初始调用值为NULL
若查找成功，则指针p指向该数据元素结点，并返回TRUE
否则指针p指向查找路径*问的最后一个结点并返回FALSE
*/
bool SearchBST(BTree* T, int key, BTree* f, BTree *&p)
{
if (T == NULL)
{
p = f;
return false;
}
else if (key == T->value)
{
p = T;
return false;
}
else if (key > T->value)
{
return SearchBST(T->pRight,key,T,p);
}
else
{
return SearchBST(T->pLeft,key,T,p);
}
}
/*
二叉搜索树的插入
当二叉排序树T中不存在关键字等于key的数据元素时，
插入key并返回TRUE，否则返回FALSE
*/
bool InsertBST(BTree *&T, int key)
{
BTree *p;
if (SearchBST(T,key,NULL,p) == false)
{
BTree *newNode = new BTree;
newNode->value = key;
newNode->pLeft = NULL;
newNode->pRight = NULL;
if (p == NULL)//说明插入的是根节点
{
T = newNode;
}
else if (key < p->value)
{
p->pLeft = newNode;
}
else
{
p->pRight = newNode;
}
return true;
}
else
{
return false;
}
}
/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
bool Delete(BTree *&p)
{
BTree* Node,*s;
if(p->pRight == NULL) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */
{
Node = p;
p = p->pLeft;
delete Node;
}
else if(p->pLeft == NULL) /* 只需重接它的右子树 */
{
Node = p;
p = p->pRight;
delete Node;
}
else /* 左右子树均不空 */
{
Node = p;
s = p->pLeft;
while(s->pRight) /* 转左，然后向右到尽头（找待删结点的前驱） */
{
Node = s;
s = s->pRight;
}
p->value = s->value; /* s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */
if(Node != p)
Node->pRight = s->pLeft; /* 重接q的右子树 */
else
Node->pLeft = s->pLeft; /* 重接q的左子树 */
delete s;
// Node = p->pLeft;
// //找到指向被删结点的直接前驱，然后交换数据，再删除delNode即可
// while(Node->pRight != NULL)
// {
// Node = Node->pRight;
// }
//
// int temp = p->value;
// p->value = Node->value;
// Node->value = temp;
//
// Delete(Node);
}
return true;
}
/*
二叉排序树的节点删除
若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点,
并返回TRUE；否则返回FALSE。 */
bool DeleteBST(BTree *&T,int key)
{
if(T == NULL) /* 不存在关键字等于key的数据元素 */
return false;
else
{
if (key == T->value) /* 找到关键字等于key的数据元素 */
return Delete(T);
else if (key < T->value)
return DeleteBST(T->pLeft,key);
else
return DeleteBST(T->pRight,key);
}
}
int main()
{
/*
1
2 3
4 5 6 7
8 9
*/
int nums1[] = {1,2,4,8,0,0,9,0,0,5,0,0,3,6,0,0,7,0,0};
BTree *pHead = NULL;
int index = 0;
pHead = CreateBTree(pHead,nums1,index);
cout<<"前序遍历:"<<ends;
PreorderTraverse(pHead);
cout<<endl;
cout<<"中序遍历:"<<ends;
InorderTraverse(pHead);
cout<<endl;
cout<<"后序遍历:"<<ends;
PostorderTraverse(pHead);
cout<<endl;
cout<<endl;
cout<<"分层遍历:"<<ends;
LevelTraverse(pHead);
cout<<endl;
cout<<"分层按行遍历:"<<endl;
LevelTraverseByRow(pHead);
cout<<endl;
cout<<"分层按行之字形遍历:"<<endl;
ZigzagPrint(pHead);
cout<<endl;
cout<<"分层按行之字形遍历_2:"<<endl;
ZigzagPrint_2(pHead);
cout<<endl;
cout<<endl;
cout<<"二叉树的深度:"<<ends;
cout<<GetBTreeDepth(pHead)<<endl;
cout<<endl;
cout<<endl;
cout<<"两种方法判断是否为平衡二叉树:"<<ends;
cout<<IsBalanced(pHead)<<endl;
cout<<IsBalancedWithoutRepeat(pHead)<<endl;
cout<<endl;
cout<<"二叉树叶子节点数:"<<ends;
cout<<GetBTreeLeafNodesTotal(pHead)<<endl;
cout<<endl;
cout<<"二叉树第3层的节点数:"<<ends;
cout<<GetBTreeKthLevelNodesTotal(pHead,3)<<endl;
cout<<endl;
cout<<"二叉树第3层叶子节点数:"<<ends;
cout<<GetBTreeKthLevelLeafNodesTotal(pHead,3)<<endl;
cout<<endl;
cout<<"比较两个二叉树结构是否相同，不涉及存储的数据:"<<ends;
cout<<BTreeCompare(pHead,pHead)<<endl;
cout<<endl;
cout<<"二叉树镜像前:"<<ends;
LevelTraverse(pHead);
cout<<endl;
cout<<"二叉树镜像后:"<<ends;
BTreeMirror(pHead);
LevelTraverse(pHead);
cout<<endl;
cout<<"二叉树镜像还原:"<<ends;
BTreeMirror(pHead);
LevelTraverse(pHead);
cout<<endl;
cout<<endl;
cout<<"查找二叉树中两个节点的最低祖先节点（或最近公共父节点等）"<<endl;
BTree *pNode = GetLastCommonParent(pHead,5,3);
if (pNode != NULL)
{
cout<<pNode->value<<endl;
}
else
{
cout<<"NULL"<<endl;
}
cout<<endl;
cout<<endl;
cout<<"二叉树中任意两个节点之间的距离:"<<ends;
cout<<GetLenBetweenNodes(pHead,5,3)<<endl;
cout<<endl;
cout<<"判断二叉树是否对称:"<<ends;
cout<<IsSymmetrical(pHead)<<endl;
cout<<endl<<"二叉树的销毁"<<endl;
ReleaseBTree(pHead);
cout<<endl;
/************************************************************************/
cout<<endl<<"***********二叉搜索树************"<<endl;
int nums2[]={5,3,8,2,4,7,9,1,6};
BTree * T=NULL;
for(int i=0;i<sizeof(nums2)/sizeof(int);i++)
{
InsertBST(T, nums2[i]);
}
cout<<"中序遍历:"<<ends;
InorderTraverse(T);
cout<<endl;
cout<<"分层按行遍历:"<<endl;
LevelTraverseByRow(T);
cout<<endl;
cout<<"删除搜索二叉树的节点"<<endl;
DeleteBST(T,5);
cout<<"分层按行遍历:"<<endl;
LevelTraverseByRow(T);
cout<<endl;
cout<<endl;
cout<<"两种方法判断是否为平衡二叉树:"<<ends;
cout<<IsBalanced(T)<<endl;
cout<<IsBalancedWithoutRepeat(T)<<endl;
cout<<endl;
return 0;
}