{
for (int i = midBegini <= midEndi++)
if (root == mid[i])
return i
}
int findFirstMid(char first[], int firstBegin, int firstEnd, char mid[], int midBegin, int midMid)
{
if (midBegin == midMid)
return firstBegin
int curMidPos = firstBegin
for (int i = midBegini <midMidi++)
for (int j = firstBegin + 1 j <= firstEndj++)
{
if ((first[j] == mid[i]) &&(j >curMidPos))
curMidPos = j
}
return curMidPos
}
//构建二叉树
TreeNode * BuildTree（char first[], int firstBegin, int firstEnd, char mid[], int midBegin, int midEnd）
{
TreeNode *root = new TreeNode()
root->value = first[firstBegin] //前序的第一个元素即为根结点
//中序序列中找到根的位置，其左边为左子树，右边为右子树
int midMid = findMidMid(mid, midBegin, midEnd, first[firstBegin])
//找到中序序列中左子树所有节点在前序序列中的最后位置，此时该位置的右边为右子树
int firstMid = findFirstMid(first, firstBegin, firstEnd, mid, midBegin, midMid)
if (midMid != midBegin) //如果树的根结点有左子树
root->left = BuildTree(first, firstBegin+ 1, firstMid , mid, midBegin, midMid - 1)
else
root->left = NULL
if (midMid != midEnd) //如果树的根结点有右子树
root->right = BuildTree(first, firstMid + 1, firstEnd, mid, midMid + 1, midEnd)
else
root->right = NULL
return root
}
//遍历二叉树输出度1的结点
void findDegreeOne(TreeNode *root)
{
if (root == NULL)
return
if ((root->left == NULL &&root->right != NULL) ||
(root->left != NULL &&root->right == NULL) )
printf("%c ", root->value)
findDegreeOne(root->left)
findDegreeOne(root->right)
}
创建二叉树的源程序如下：
#include <cstdlib>
#include <stdio.h>
typedef struct node
{ //树的结点
int data
struct node* left
struct node* right
} Node
typedef struct
{ //树根
Node* root；
} Tree
void insert(Tree* tree, int value)//创建树
{
Node* node=(Node*)malloc(sizeof(Node))//创建一个节点
node->data = value
node->left = NULL
node->right = NULL
if (tree->root == NULL)//判断树是不是空树
{
tree->root = node
}
else
{//不是空树
Node* temp = tree->root//从树根开始
while (temp != NULL)
{
if (value <temp->data)//小于就进左儿子
{
if (temp->left == NULL)
{
temp->left = node
return
}
else
{//继续判断
temp = temp->left
}
}
else {//否则进右儿子
if (temp->right == NULL)
{
temp->right = node
return
}
else {//继续判断
temp = temp->right
}
}
}
}
return；
}
void inorder(Node* node)//树的中序遍历
{
if (node != NULL)
{
inorder(node->left)
printf("%d ",node->data)
inorder(node->right)
}
}
int main()
{
Tree tree
tree.root = NULL//创建一个空树
int n
scanf("%d",&n)
for (int i = 0i <ni++)//输入n个数并创建这个树
{
int temp
scanf("%d",&temp)
insert(&tree, temp)
}
inorder(tree.root)//中序遍历
getchar()
getchar()
return 0
}
扩展资料：
简单二叉树定义范例：此树的顺序结构为：ABCDE
#include <cstdlib>
#include <stdio.h>
#include <string>
int main()
{
node* p = newnode
node* p = head
head = p
string str
cin >>str
creat(p, str, 0)//默认根结点在str下标0的位置
return 0
}
//p为树的根结点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置
void creat(node* p, string str, int r)
{
p->data = str[r]
if (str[r * 2 + 1] == '#' || r * 2 + 1 >str.size() - 1)p->lch = NULL；
else
{
p->lch = newnode
creat(p->lch, str, r * 2 + 1)
}
if (str[r * 2 + 2] == '#' || r * 2 + 2 >str.size() - 1)p->rch = NULL
else
{
p->rch = newnode
creat(p->rch, str, r * 2 + 2)
}
}
刚刚回答了一个类似的问题，以下代码供参考：#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char TElemType
typedef int Status
typedef struct BiTNode { // 结点结构
TElemType data
struct BiTNode *lchild, *rchild
// 左右孩子指针
} BiTNode, *BiTree
//以下是建立二叉树存储结构，空节点输入作为#结束标识
Status CreateBiTree(BiTree &T) {
//请将该算法补充完整，参见第6章课件算法或课本
char ch
scanf("%c",&ch)
if(ch=='#') T=NULL
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW)
T->data=ch
CreateBiTree(T->lchild)
CreateBiTree(T->rchild)
}
return OK
} // CreateBiTree
void Preorder(BiTree T)
{
if(T)
{
printf("%c",T->data)
Preorder(T->lchild)
Preorder(T->rchild)
}
}
void Inorder(BiTree T)
{ // 中序遍历二叉树
//请将该算法补充完整，参见第6章课件算法
if(T)
{
Inorder(T->lchild)
printf("%c",T->data)
Inorder(T->rchild)
}
}
void Postorder(BiTree T)
{ // 后序遍历二叉树
//请将该算法补充完整，参见第6章课件算法
if(T)
{
Postorder(T->lchild)
Postorder(T->rchild)
printf("%c",T->data)
}
}
//以下是求叶子结点数
void CountLeaf(BiTree T,int&count){
//请将该算法补充完整，参见第6章课件算法
if(T){
if((!T->lchild)&&(!T->rchild))
count++
CountLeaf(T->lchild,count)
CountLeaf(T->rchild,count)
}
}
//以下是求二叉树的深度
int Depth(BiTree T ){
//请将该算法补充完整，参见第6章课件算法
int depthval,depthLeft,depthRight
if(!T) depthval=0
else{
depthLeft = Depth(T->lchild)
depthRight = Depth(T->rchild)
if(depthLeft>depthRight)depthval = 1+depthLeft
else depthval = 1+depthRight
}
return depthval
}
void main(){
BiTree T
int s=0,d
printf("\n creat of the bitree:\n")
CreateBiTree(T)
printf("\n output result of Preorder:\n")
Preorder(T)
CountLeaf(T,s)
d=Depth(T)
printf("\n leaves=%d\n",s)
printf("\n depth=%d\n",d)
}
