我想要用链表来表示二叉树(复习一下),用层序遍历的方式构造二叉树再求高度,为什么不对啊!!!
#include <iostream>
#include <malloc.h>
#include <vector>
#include <queue>
using namespace std;
typedef struct Tree *TreeNode;
struct Tree
{
TreeNode Left,Right;
int data;
};
TreeNode CreateTree(vector<int> v)
{
queue<TreeNode> q;
if(v.empty())
{
return NULL;
}
TreeNode T,bt;
T = (TreeNode)malloc(sizeof(struct Tree));
T->data = v[0];
q.push(T);
vector<int>::size_type i = 1;
while(!q.empty())
{
bt = q.front();
q.pop();
if(i < v.size())
{
bt->Left = (TreeNode)malloc(sizeof(struct Tree));
bt->Left->data = v[i];
q.push(bt->Left);
i++;
}
else
{
bt->Left = NULL;
}
if(i < v.size())
{
bt->Right = (TreeNode)malloc(sizeof(struct Tree));
bt->Right->data = v[i];
q.push(bt->Right);
i++;
}
else
{
bt->Right = NULL;
}
}
return T;
}
int FindHeight(TreeNode T)
{
if(T==NULL)
{
return 0;
}
else
{
int h1 = FindHeight(T->Left);
int h2 = FindHeight(T->Right);
int h = max(h1,h2);
return h+1;
}
}
int main()
{
vector<int> v;
int n;
cin >> n;
v.push_back(1);
int l,r;
for(int i = 0 ; i < n ; i++)
{
cin >> l >> r;
v.push_back(l);
v.push_back(r);
}
TreeNode T;
T = CreateTree(v);
int h = FindHeight(T);
cout << h << endl;
return 0;
}