二叉树的操作

对于二叉树的操作，做一个简单的总结；
Tips：针对于任何树的操作，首先需要判断是不是空树
树的结构体：
int index = 0;

typedef struct BiTree
{
int data;
    BiTree* lchild;
    BiTree* rchild;
}*Tree;

创建树的操作：

void createBT(Tree &root,int data[])
{
    int value = data[index++];
if(value == -1)
    {
        root = NULL;
    }
else
    {
        root = new BiTree;
        root->data = value;
        createBT(root->lchild,data);
        createBT(root->rchild,data);
    }
}

计算结点个数：

int Count_Leaf(Tree &root)
{
int count = 0;
if(!root)
    {
return count;
    }
count = Count_Leaf(root->lchild)+Count_Leaf(root->rchild)+1;
return count;
}

计算树中叶子结点个数

int Count(Tree &root)
{
if(!root)
return 0;
if(root->lchild == NULL && root->rchild == NULL)
return 1;
    int numLeft = Count(root->lchild);
    int numRight = Count(root->rchild);
return (numLeft+numRight);
}

二叉树的深度：

int BT_depth(Tree &root)
{
if(!root)
return 0;
int depth_left = BT_depth(root->lchild)+1;
int depth_right = BT_depth(root->rchild)+1;
return depth_left>depth_right?depth_left:depth_right;
}

二叉树的bfs遍历：

void Level(Tree &root)
{
cout << "二叉树的层次遍历" << endl;
queue<BiTree*> que;
if(!root)
return;
    que.push(root);
while(!que.empty())
    {
        root = que.front();
        que.pop();
cout << root->data << " ";
if(root->lchild)
            que.push(root->lchild);
if(root->rchild)
            que.push(root->rchild);
    }
}

二叉树的dfs遍历：

void dfs(Tree &root)
{
stack<BiTree*> s;
if(!root)
return;
    s.push(root);
while(!s.empty())
    {
        root = s.top();
cout << root->data << " ";
        s.pop();
if(root->rchild)
            s.push(root->rchild);
if(root->lchild)
            s.push(root->lchild);
    }
}

二叉树第K层结点数：

int K_level(Tree &root,int k)
{
if(!root || k<1)
return 0;
if(k == 1)
return 1;
int numLeft = K_level(root->lchild,k-1);
int numright = K_level(root->rchild,k-1);
return (numLeft+numright);
}

判断俩个二叉树是否是一样的？

bool Same_BT(Tree &root1,Tree &root2)
{
if(!root1 && !root2)
return true;
if(!root1 || !root2)
return false;
    bool leftSame = Same_BT(root1->lchild,root2->lchild);
    bool rightSame = Same_BT(root1->rchild,root2->rchild);
return (leftSame&&rightSame);
}

二叉树的镜像：

BiTree* Mirror(Tree &root)
{
if(!root)
return NULL;
    BiTree* left = Mirror(root->lchild);
    BiTree* right = Mirror(root->rchild);
    root->lchild = right;
    root->rchild = left;
return root;
}

是否是平衡二叉树：

bool isAVL(Tree &root,int &height)
{
if(!root)
    {
        height = 0;
return true;
    }
int heightLeft;
bool left = isAVL(root->lchild,heightLeft);
int heightRight;
bool right = isAVL(root->rchild,heightRight);
if(left && right && abs(heightLeft-heightRight)<=1)
    {
        height = max(heightLeft,heightRight)+1;
return true;
    }
else
    {
         height = max(heightLeft,heightRight)+1;
return false;
    }
}

操作的main（）函数：

int main()
{
int data[] = {8,6,4,-1,-1,7,-1,-1,10,9,-1,-1,11,-1,-1};
int data1[] = {8,6,4,-1,-1,7,-1,-1,10,9,-1,-1,11,-1,-1};
    Tree tree;
    Tree tree1;
    createBT(tree,data);
/*
 //int height;
 if(isAVL(tree,height))
 {
 cout << "isAVL" << endl;
 }*/
    createBT(tree1,data1);

if(Same_BT(tree,tree1))
    {
cout<< "这俩二叉树是一样的" << endl;
    }
else
    {
cout << "这俩二叉树是不一样的" << endl;
    }
//cout << "二叉树的叶子节点个数" << endl;
//cout<<Count_Leaf(tree);
//cout<<Count(tree)<<endl;
//cout<<BT_depth(tree);*/
//Level(tree);

//cout << endl;
//Mirror(tree);
//Level(tree);
//cout<< endl;
// dfs(tree);
//cout<< K_level(tree,3)<<endl;
return 0;
}