求二叉树的高度和销毁一颗二叉树——题集九

求二叉树的高度和销毁一颗二叉树——题集九

       今天来分享一下，求二叉树的高度和销毁一颗二叉树以及如何实现链表翻转（链表逆置的升级变型）。

       求二叉树的高度和销毁一颗二叉树（Destroy(Node* root) ）的源代码和运行示例。

源代码如下：

#include<iostream>
using namespace std;
 
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x)
:val(x)
,left(NULL)
,right(NULL)
{
    }
};
 
 
int _Heigt(TreeNode* root){
if(root==NULL) return 0;
 
int left = _Heigt(root->left);
int right = _Heigt(root->right);
 
return left>right?left+1:right+1;
}
 
//二叉树的高度
int Height(TreeNode* root){//二叉树的高度
if(root == NULL)
return 0;
 
return _Heigt(root);//递归简单
}
 
void _Destroy(TreeNode*  & root){
if(root==NULL) return;
 
_Destroy(root->left);
_Destroy(root->right);
 
delete root;
root=root->left;
root=NULL;
 
return ;
}
 
//销毁一颗二叉树
void Destroy(TreeNode*& root){
if(root == NULL)
return;
 
_Destroy(root);
return ;
}
 
void TestTree(){//二叉树的高度+销毁一颗二叉树
TreeNode * pRoot1=new TreeNode(1);
TreeNode * pRoot2=new TreeNode(2);
TreeNode * pRoot3=new TreeNode(3);
TreeNode * pRoot4=new TreeNode(4);
TreeNode * pRoot5=new TreeNode(5);
TreeNode * pRoot6=new TreeNode(6);
TreeNode * pRoot7=new TreeNode(7);
TreeNode * pRoot8=new TreeNode(8);
 
pRoot1->left = pRoot2;
pRoot1->right = pRoot3;
pRoot2->left = pRoot4;
pRoot2->right = pRoot5;
pRoot3->left = pRoot6;
pRoot3->right = pRoot7;
pRoot4->left = pRoot8;
 
cout<<"求二叉树的高度"<<endl;
cout<<"Height(pRoot1): "<<Height(pRoot1)<<endl;//二叉树的高度
cout<<"Height(pRoot2): "<<Height(pRoot2)<<endl;
cout<<"Height(pRoot8): "<<Height(pRoot8)<<endl;
cout<<endl;
 
cout<<"销毁一颗二叉树"<<endl;
cout<<"Height(pRoot1): "<<Height(pRoot1)<<endl;
Destroy(pRoot1);//销毁一颗二叉树
cout<<"Destroy(pRoot1) -> Height(pRoot1): "<<Height(pRoot1)<<endl;
cout<<endl;
}
 
int main(){
TestTree();//二叉树的高度+销毁一颗二叉树
system("pause");
return 0;
}

运行结果：

 

测试用例的二叉树是长成这样的哦。

       链表翻转的源代码和运行示例。

       给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现Node* RotateList(Node* list, size_t k). 提示：这个题是链表逆置的升级变型。

源代码如下：

#include<iostream>
using namespace std;
 
struct ListNode{
int val;
ListNode* next;
ListNode(int _val)
:val(_val)
,next(NULL)
{}
};
 
void _RotateList(ListNode*& begin, ListNode*& end){//begin和end 不可能为NULL
ListNode* cur = begin;
ListNode* next = cur->next;
 
while(next != end){
ListNode* tmp=next->next;
 
next->next = cur;
cur=next;
next=tmp;
 
}
next->next = cur;
}
ListNode* RotateList(ListNode* list, size_t k){//递归
ListNode* head=list;
if(k<=1) return head;
 
ListNode* begin=list;
ListNode* end=list;
 
 
ListNode* prev=NULL;
ListNode* next=NULL;
 
while(end != NULL){
size_t i=1;
 
while(i<k && end->next != NULL){
++i;
end = end->next;
}
 
if(end->next != NULL){
next=end->next;
_RotateList(begin, end);
if(prev == NULL){
head=end;
}
else{
prev->next=end;
}
 
begin->next =next;
prev=begin;
begin=end=next;
i=1;
}
else{
end=end->next;
}
}
 
return head;
}
 
void Printf(ListNode* l1){//打印
int i=0;
while(l1!=NULL){
if(i!=0)
cout<<"->";
cout<<l1->val;
l1=l1->next;
++i;
}
printf("\n");
}
 
void TestRotateList(){////如何实现链表翻转
ListNode l1(1);
ListNode l2(2);
ListNode l3(3);
ListNode l4(4);
ListNode l5(5);
l1.next = &l2;
l2.next = &l3;
l3.next = &l4;
l4.next = &l5;
 
cout<<"原链表遍历打印："<<endl;
Printf(&l1);
ListNode* lA=RotateList(&l1, 1);//递归
cout<<"1次翻转打印->RotateList(&l1, 1)：";
Printf(lA);
 
cout<<endl<<"原链表遍历打印："<<endl;
Printf(&l1);
lA=RotateList(&l1, 2);//递归
cout<<"2次翻转打印->RotateList(&l1, 2)：";
Printf(lA);
 
l1.next = &l2;
l2.next = &l3;
l3.next = &l4;
l4.next = &l5;
 
cout<<endl<<"原链表遍历打印："<<endl;
Printf(&l1);
lA=RotateList(&l1, 3);//递归
cout<<"3次翻转打印->RotateList(&l1, 3)：";
Printf(lA);
cout<<endl;
}
 
int main(){
TestRotateList();////如何实现链表翻转
system("pause");
return 0;
}

运行结果：

 

      分享如上，如有错误，望斧正！愿大家学得开心，共同进步！