二叉树

/*二叉树练习*/
#include<iostream>
using namespace std;
struct BiTree{
int data;
BiTree*lchild, *rchild;
};
struct BiTree_char{
char data;
BiTree_char*lchild, *rchild;
};
void CreateBiTree(BiTree*&T)
{
int data;
cin >> data;
if (data == -1)T = NULL;
else
{
T = (BiTree*)malloc(sizeof(struct BiTree));
if (T == NULL)return;
T->data = data;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void PreOrder(BiTree*T)
{
if (T)
{
cout << T->data << " ";
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
#include<stack>
void PreOrder_Without(BiTree*T)
{
int sum = 0;
stack<BiTree*>s;
BiTree*p = T;
while (p || !s.empty())
{
while (p)
{
s.push(p);
if (p->lchild == NULL&&p->rchild == NULL)sum += 1;
cout << p->data << " ";
p = p->lchild;
}
if (!s.empty())
{
p = s.top();
s.pop();
p = p->rchild;
}
}
cout << endl << "叶子节点个数：" << sum << endl;
}
void BackOrder(BiTree*T)
{
int depth = 0;
stack<BiTree*>s;
BiTree*p = T, *pre = NULL;
while (p || !s.empty())
{
while (p)
{
s.push(p);
if (s.size() > depth)depth = s.size();
p = p->lchild;
}
if (!s.empty())
{
p = s.top();
s.pop();
if (p->rchild == NULL || p->rchild == pre)
{
cout << p->data << " ";
pre = p, p = NULL;
}
else
{
s.push(p);
if (s.size() > depth)depth = s.size();
p = p->rchild;
}
}
}
cout << endl << "树的深度:" << depth << endl;
}
void Back(BiTree_char*T)
{
if (T)
{
Back(T->lchild);
Back(T->rchild);
cout << T->data;
}
}
void InOrder(BiTree*T)
{
stack<BiTree*>s;
BiTree*p = T;
while (p || !s.empty())
{
while (p)
{
s.push(p);
p = p->lchild;
}
if (!s.empty())
{
p = s.top();
cout << p->data << " ";
s.pop();
p = p->rchild;
}
}
}
#include<queue>
void LevelOrder(BiTree*T)
{
int level = 0;
queue<BiTree*>q;
BiTree*p = T;
q.push(p);
while (!q.empty())
{
if (level < q.size())level = q.size();
p = q.front();
q.pop();
cout << p->data << " ";
if (p->lchild)
{
q.push(p->lchild);
//if (q.size() > level)level = q.size();
}
if (p->rchild)
{
q.push(p->rchild);
//if (q.size() > level)level = q.size();
}
}
cout << endl << "树的广度:" << level << endl;
}
void Count_K(BiTree*T, int k = 3)
{
int depth = 1, sum = 0;
stack<BiTree*>s;
BiTree*p = T, *pre = NULL;
while (p || !s.empty())
{
while (p)
{
s.push(p);
depth++;
p = p->lchild;
}
if (!s.empty())
{
p = s.top();
s.pop();
depth--;
if (p->rchild == NULL || p->rchild == pre)
{
if (depth == k)sum++;
cout << p->data << "-层级：" << depth << endl;
pre = p, p = NULL;
}
else
{
s.push(p);
depth++;
p = p->rchild;
}
}
}
cout << "第" << k << "层节点个数：" << sum << endl;
}
void If_BiTree_Totally(BiTree*T)
{
int check = 1, score = 1;
queue<BiTree*>q;
BiTree*p = T;
q.push(p);
while (!q.empty())
{
p = q.front();
q.pop();
if (p->lchild == NULL&&p->rchild != NULL)score = 0;
if (check == 0 && (p->lchild != NULL || p->rchild != NULL))score = 0;
if (p->lchild == NULL&&p->rchild == NULL || p->lchild != NULL&&p->rchild == NULL)check = 0;
if (p->lchild)
{
q.push(p->lchild);
}
if (p->rchild)
{
q.push(p->rchild);
}
}
if (score == 0)
cout << "不是完全二叉树" << endl;
else
{
cout << "是完全二叉树" << endl;
}
}
void Copy(BiTree*T,BiTree*&copy)
{
if (T)
{
copy = (BiTree*)malloc(sizeof(struct BiTree));
if (copy == NULL)return;
copy->data = T->data;
Copy(T->lchild, copy->lchild);
Copy(T->rchild, copy->rchild);
}
else
{
copy = NULL;
}
}
void Swap(BiTree*&T)
{
BiTree*temp;
if (T)
{
temp = T->lchild, T->lchild = T->rchild, T->rchild = temp;
Swap(T->lchild);
Swap(T->rchild);
}
}
void Print_Path(BiTree*T)
{
stack<BiTree*>s;
BiTree*p = T, *pre = NULL;
cout << "输出所有叶子节点到根节点的路径:" << endl;
while (p || !s.empty())
{
while (p)
{
s.push(p);
p = p->lchild;
}
if (!s.empty())
{
p = s.top();
s.pop();
if (p->rchild == NULL || p->rchild == pre)
{
if (p->lchild == NULL&&p->rchild == NULL)
{
cout << p->data << " ";
stack<BiTree*>s0 = s;
BiTree*p0;
while (!s0.empty())
{
p0 = s0.top();
cout << p0->data << " ";
s0.pop();
}
cout << endl;
}
pre = p, p = NULL;
}
else
{
s.push(p);
p = p->rchild;
}
}
}
}
#include<string>
void String(BiTree_char*&T, string pre, string in)
{
if (pre.size() == 0)
{
T = NULL;
return;
}
char root = pre[0];
int index = in.find(root);
string in_l = in.substr(0, index);
string in_r = in.substr(index + 1);
int length_l = in_l.size();
int length_r = in_r.size();
string pre_l = pre.substr(1, length_l);
string pre_r = pre.substr(length_l + 1);
T = (BiTree_char*)malloc(sizeof(struct BiTree_char));
if (T == NULL)return;
T->data = root;
String(T->lchild, pre_l, in_l);
String(T->rchild, pre_r, in_r);
}
void Create_HT(BiTree*&T, int num[], int n)
{
BiTree**tree, *P;
tree = (BiTree**)malloc(sizeof(struct BiTree));
if (tree == NULL)return;
for (int i = 0; i < n; i++)
{
tree[i] = (BiTree*)malloc(sizeof(struct BiTree));
if (tree[i] == NULL)return;
tree[i]->data = num[i];
tree[i]->lchild = tree[i]->rchild = NULL;
}
for (int i = 0; i < n - 1; i++)
{
int k1 = -1, k2;
for (int i = 0; i < n; i++)
{
if (tree[i] != NULL&&k1 == -1)
{
k1 = i;
continue;
}
if (tree[i] != NULL)
{
k2 = i;
break;
}
}
for (int i = k2; i < n; i++)
{
if (tree[i] != NULL&&tree[k1]->data > tree[i]->data)
{
k2 = k1, k1 = i;
}
else if (tree[i] != NULL&&tree[k2]->data > tree[i]->data)
{
k2 = i;
}
}
P = (BiTree*)malloc(sizeof(struct BiTree));
if (P == NULL)return;
P->data = tree[k1]->data + tree[k2]->data;
P->lchild = tree[k1];
P->rchild = tree[k2];
tree[k1] = P;
tree[k2] = NULL;
}
T = P;
}
int BackOrder_HT(BiTree*&T)
{
int depth = 0, sum = 0;
stack<BiTree*>s;
BiTree*p = T, *pre = NULL;
while (p || !s.empty())
{
while (p)
{
s.push(p);
depth++;
//if (s.size() > depth)depth = s.size();
p = p->lchild;
}
if (!s.empty())
{
p = s.top();
s.pop();
depth--;
if (p->rchild == NULL || p->rchild == pre)
{
if (p->lchild == NULL&&p->rchild == NULL)
{
sum += depth*p->data;
//cout << p->data << " ";
}
pre = p, p = NULL;
}
else
{
s.push(p);
depth++;
//if (s.size() > depth)depth = s.size();
p = p->rchild;
}
}
}
return sum;
//cout << endl << "树的深度:" << depth << endl;
}
void Coding_HT(BiTree*&T)
{
cout << "哈夫曼编码是：" << endl;
int Path[20], len = 0;
stack<BiTree*>s;
BiTree*p = T, *pre = NULL;
while (p || !s.empty())
{
while (p)
{
s.push(p);
Path[len] = 1;
len++;
// if (s.size() > depth)depth = s.size();
p = p->lchild;
}
if (!s.empty())
{
p = s.top();
s.pop();
len--;
if (p->rchild == NULL || p->rchild == pre)
{
if (p->lchild == NULL&&p->rchild == NULL)
{
cout << p->data << ":";
for (int i = 0; i < len; i++)
{
cout << Path[i];
}
cout << endl;
// cout << p->data << " ";
}
pre = p, p = NULL;
}
else
{
s.push(p);
Path[len] = 0;
len++;
// if (s.size() > depth)depth = s.size();
p = p->rchild;
}
}
}
//cout << endl << "树的深度:" << depth << endl;

}
int main()
{
BiTree*T;
/*CreateBiTree(T);
cout << "先序遍历：" << endl;
PreOrder(T);
cout << endl;
PreOrder_Without(T);
cout << endl;
cout << "中序遍历:" << endl;
InOrder(T);
cout << endl;
cout << "后序遍历：" << endl;
BackOrder(T);
cout << endl;
cout << "层次遍历:" << endl;
LevelOrder(T);
cout << endl;
Count_K(T);
cout << endl;
If_BiTree_Totally(T);
cout << endl;
cout << "复制一棵二叉树" << endl;
BiTree*copy;
copy = (BiTree*)malloc(sizeof(struct BiTree));
Copy(T, copy);
PreOrder(copy);
cout << endl;
cout << "左右子树相交换" << endl;
Swap(copy);
PreOrder(copy);
cout << endl;
Print_Path(T);
cout << endl;

cout << "请输入先序字符数组:" << endl;
string pre;
cin >> pre;
cout << "请输入中序字符数组:" << endl;
string in;
cin >> in;
BiTree_char*TT;
TT = (BiTree_char*)malloc(sizeof(struct BiTree_char));
String(TT, pre, in);
cout << "后序序列：" << endl;
Back(TT);
cout << endl;*/
cout << "输入叶子结点个数：" << endl;
int n; cin >> n;
cout << "输入权值：" << endl;
int num[50];
for (int i = 0; i < n; i++)cin >> num[i];
T = (BiTree*)malloc(sizeof(struct BiTree));
Create_HT(T, num, n);
cout << "权值是：" << BackOrder_HT(T) << endl;
Coding_HT(T);
cout << endl;
return 0;
}