二叉树的操作

对于二叉树的操作，做一个简单的总结； 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;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;};}

，我只愿，在你的理想和希望里能为你增加一点鼓励，