完全二叉树建立

二叉树怎么建立？

这个简单啊 // c6-2.h 二叉树的二叉链表存储表示 typedef struct BiTNode { TElemType data; BiTNode *lchild,*rchild; // 左右孩子指针 }BiTNode,*BiTree;。

// arith.cpp 二叉树的二叉链表存储(存储结构由c6-2.h定义)的基本操作，包括算法6.1～6.4 #define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样。

void InitBiTree(BiTree &T) { // 操作结果：构造空二叉树T T=NULL; }。

void DestroyBiTree(BiTree &T) { // 初始条件：二叉树T存在。操作结果：销毁二叉树T if(T) // 非空树 { if(T->lchild) // 有左孩子 DestroyBiTree(T->lchild); // 销毁左孩子子树 if(T->rchild) // 有右孩子 DestroyBiTree(T->rchild); // 销毁右孩子子树 free(T); // 释放根结点 T=NULL; // 空指针赋0 } }。

void PreOrderTraverse(BiTree T,void(*Visit)(TElemType)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。算法6.1，有改动 // 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) // T不空 { Visit(T->data); // 先访问根结点 PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树 PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树 } }。

void InOrderTraverse(BiTree T,void(*Visit)(TElemType)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) { InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树 Visit(T->data); // 再访问根结点 InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树 } }。

void CreateBiTree(BiTree &T) { // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)， // 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。有改动 TElemType ch; scanf(form, &ch); if(ch==Nil) // 空 T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点 if(!T) exit(OVERFLOW); T->data=ch; CreateBiTree(T->lchild); // 构造左子树 CreateBiTree(T->rchild); // 构造右子树 } }。

int BiTreeDepth(BiTree T) { // 初始条件：二叉树T存在。操作结果：返回T的深度 int i,j; if(!T) return 0; // 空树深度为0 i=BiTreeDepth(T->lchild); // i为左子树的深度 j=BiTreeDepth(T->rchild); // j为右子树的深度 return i>j ? i+1 : j+1; // T的深度为其左右子树的深度中的大者+1 }。

int CountLeaf (BiTree T){ //计算树中的叶子结点数量 int count = 0; if ( T ) { if ((!T->lchild) && (!T->rchild)) count++; // 对叶子结点计数 count += CountLeaf( T->lchild); count += CountLeaf( T->rchild); } // if return count;} // CountLeaf Status BiTreeEmpty(BiTree T) { // 初始条件：二叉树T存在。操作结果：若T为空二叉树，则返回TRUE，否则FALSE if(T) return FALSE; else return TRUE; }。

TElemType Root(BiTree T) { // 初始条件：二叉树T存在。操作结果：返回T的根 if(BiTreeEmpty(T)) return Nil; else return T->data; }。

TElemType Value(BiTree p) { // 初始条件：二叉树T存在，p指向T中某个结点。操作结果：返回p所指结点的值 return p->data; }。

void Assign(BiTree p,TElemType value) { // 给p所指结点赋值为value p->data=value; }。

typedef BiTree QElemType; // 设队列元素为二叉树的指针类型 #include"..\ch3_8_Queue_ln\c3-2.h" // 链队列 #include"..\ch3_8_Queue_ln\arith.cpp" // 链队列的基本操作 TElemType Parent(BiTree T,TElemType e) { // 初始条件：二叉树T存在，e是T中某个结点 // 操作结果：若e是T的非根结点，则返回它的双亲，否则返回＂空＂ LinkQueue q; QElemType a; if(T) // 非空树 { InitQueue(q); // 初始化队列 EnQueue(q,T); // 树根指针入队 while(!QueueEmpty(q)) // 队不空 { DeQueue(q,a); // 出队，队列元素赋给a if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e) // 找到e(是其左或右孩子) return a->data; // 返回e的双亲的值 else // 没找到e，则入队其左右孩子指针(如果非空) { if(a->lchild) EnQueue(q,a->lchild); if(a->rchild) EnQueue(q,a->rchild); } } } return Nil; // 树空或没找到e }。

BiTree Point(BiTree T,TElemType s) { // 返回二叉树T中指向元素值为s的结点的指针。另加 LinkQueue q; QElemType a; if(T) // 非空树 { InitQueue(q); // 初始化队列 EnQueue(q,T); // 根指针入队 while(!QueueEmpty(q)) // 队不空 { DeQueue(q,a); // 出队，队列元素赋给a if(a->data==s) return a; if(a->lchild) // 有左孩子 EnQueue(q,a->lchild); // 入队左孩子 if(a->rchild) // 有右孩子 EnQueue(q,a->rchild); // 入队右孩子 } } return NULL; }。

TElemType LeftChild(BiTree T,TElemType e) { // 初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子,则返回"空" BiTree a; if(T) // 非空树 { a=Point(T,e); // a是结点e的指针 if(a&&a->lchild) // T中存在结点e且e存在左孩子 return a->lchild->data; // 返回e的左孩子的值 } return Nil; // 其余情况返回空 }。

TElemType RightChild(BiTree T,TElemType e) { // 初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子,则返回"空" BiTree a; if(T) // 非空树 { a=Point(T,e); // a是结点e的指针 if(a&&a->rchild) // T中存在结点e且e存在右孩子 return a->rchild->data; // 返回e的右孩子的值 } return Nil; // 其余情况返回空 }。

TElemType LeftSibling(BiTree T,TElemType e) { // 初始条件：二叉树T存在，e是T中某个结点 // 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回＂空＂ TElemType a; BiTree p; if(T) // 非空树 { a=Parent(T,e); // a为e的双亲 if(a!=Nil) // 找到e的双亲 { p=Point(T,a); // p为指向结点a的指针 if(p->lchild&&p->rchild&&p->rchild->data==e) // p存在左右孩子且右孩子是e return p->lchild->data; // 返回p的左孩子(e的左兄弟) } } return Nil; // 其余情况返回空 }。

TElemType RightSibling(BiTree T,TElemType e) { // 初始条件：二叉树T存在，e是T中某个结点 // 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回＂空＂ TElemType a; BiTree p; if(T) // 非空树 { a=Parent(T,e); // a为e的双亲 if(a!=Nil) // 找到e的双亲 { p=Point(T,a); // p为指向结点a的指针 if(p->lchild&&p->rchild&&p->lchild->data==e) // p存在左右孩子且左孩子是e return p->rchild->data; // 返回p的右孩子(e的右兄弟) } } return Nil; // 其余情况返回空 }。

Status InsertChild(BiTree p,int LR,BiTree c) // 形参T无用 { // 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空 // 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点的 // 原有左或右子树则成为c的右子树 if(p) // p不空 { if(LR==0) { c->rchild=p->lchild; p->lchild=c; } else // LR==1 { c->rchild=p->rchild; p->rchild=c; } return OK; } return ERROR; // p空 }。

Status DeleteChild(BiTree p,int LR) // 形参T无用 { // 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1 // 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树 if(p) // p不空 { if(LR==0) // 删除左子树 ClearBiTree(p->lchild); else // 删除右子树 ClearBiTree(p->rchild); return OK; } return ERROR; // p空 }。

typedef BiTree SElemType; // 设栈元素为二叉树的指针类型 #include"..\ch3_1_stack_sq\c3-1.h" // 顺序栈 #include"..\ch3_1_stack_sq\arith3-1.cpp" // 顺序栈的基本操作 。

void InOrderTraverse1(BiTree T,void(*Visit)(TElemType)) { // 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.2，有改动 // 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit SqStack S; BiTree p; InitStack(S); Push(S,T); // 根指针进栈 while(!StackEmpty(S)) { while(GetTop(S,p) && p) Push(S,p->lchild); // 向左走到尽头 Pop(S,p); // 空指针退栈 if(!StackEmpty(S)) { // 访问结点，向右一步 Pop(S,p); Visit(p->data); Push(S,p->rchild); } } printf("\n"); }。

void InOrderTraverse2(BiTree T,void(*Visit)(TElemType)) { // 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.3，有改动 // 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit SqStack S; BiTree p = T; InitStack(S); while(p || !StackEmpty(S)) { if(p) { // 根指针进栈，遍历左子树 Push(S, p); p = p->lchild; } else { // 根指针退栈，访问根结点，遍历右子树 Pop(S, p); Visit(p->data); p = p->rchild; } } printf("\n"); }。

void PostOrderTraverse(BiTree T,void(*Visit)(TElemType)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) // T不空 { PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树 PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树 Visit(T->data); // 最后访问根结点 } }。

void LevelOrderTraverse(BiTree T,void(*Visit)(TElemType)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：层序递归遍历T(利用队列)，对每个结点调用函数Visit一次且仅一次 LinkQueue q; QElemType a; if(T) { InitQueue(q); // 初始化队列q EnQueue(q,T); // 根指针入队 while(!QueueEmpty(q)) // 队列不空 { DeQueue(q,a); // 出队元素(指针),赋给a Visit(a->data); // 访问a所指结点 if(a->lchild!=NULL) // a有左孩子 EnQueue(q,a->lchild); // 入队a的左孩子 if(a->rchild!=NULL) // a有右孩子 EnQueue(q,a->rchild); // 入队a的右孩子 } printf("\n"); } }。

完全二叉树的算法

二叉树建立方法：

一、我们要明确的一点是只有中序是无法创建二叉树的，它要结合先序，两者相联系才可以。

二、根据二叉树的图，得出先序的顺序是ABDECFG，而与此同时的中序DBEAFCG，根据这个建立。

三、然后就是要根据二叉树的原则编写代码，你要知道的是前序遍历序列中的首元素是二叉树的根节点。

四、然后你要做的是在中序遍历序列中找到这个节点，他是中间的分水岭，前面其左节点,后面是右节点。

五、最后要做的是建立根节点的左子树和右子树，再由中序  遍历序列中根节点的位置确定我们前面提到的子树的节点，这样二叉树就差不多建立完成了。

二叉树的建立和遍历(C++)

如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。

可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0=n2+1，则n= n0+n1+n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=(n+1)/2或n0=n/2。

总结起来，就是 n0=[n/2]，其中[]表示上取整。可根据完全二叉树的结点总数计算出叶子结点数。

请问C语言如何创建二叉树？？？？

фinclude<iostream>。

фinclude<windows.h>。

фinclude<string>。

фinclude<stdlib.h>。

фinclude<fstream>。

using namespace std;。

//------------------------------二叉树节点------------------------------------------。

class bitnode

public:

char data;

bitnode *lchild,*rchild;。

};

//-------------------------------函数-------------------------------------------------。

void visit(bitnode *T); //访问二叉树节点。

void create(bitnode *&T); //生成二叉树。

void zhongbianli(bitnode *T); //中序遍历二叉树。

void houbianli(bitnode *T); //后序遍历二叉树。

void xianbianli(bitnode *T); //先序遍历二叉树。

int pd(bitnode *T); //判断是否是完全二叉树。

int depth(bitnode *T); //二叉树的深度。

//------------------------------访问二叉树节点---------------------------------------。

void visit(bitnode *T)。

cout<<T->data<<ends;。

return;

//------------------------------生成二叉树------------------------------------------。

void create(bitnode *&T)。

//bitnode T;

char a;

//cin>>a;。

cin>>a;

cout<<a;。

if(a=='ф')

{

T=NULL;

}

else

{

T=new bitnode;。

T->data=a;

T->lchild=NULL;。

T->rchild=NULL;。

// cout<<"create "<<T->data<<"'s lchild"; 。

create(T->lchild); 。

// cout<<"create "<<T->data<<"'s rchild"; 。

create(T->rchild);。

}

//------------------------------中序遍历二叉树----------------------------------------。

void zhongbianli(bitnode *T) 。

if(T)

{

zhongbianli(T->lchild);。

visit(T);

zhongbianli(T->rchild);。

}

//------------------------------先序遍历二叉树-----------------------------------------。

void xianbianli(bitnode *T) 。

if(T)

{

visit(T);

xianbianli(T->lchild);。

xianbianli(T->rchild);。

}

//------------------------------后序遍历二叉树------------------------------------------。

void houbianli(bitnode *T) 。

if(T)

{

houbianli(T->lchild); 。

houbianli(T->rchild);。

visit(T);

}

//------------------------------二叉树的深度-----------------------------------------。

int depth(bitnode *T)。

int dep1,dep2;。

if (T==NULL) return 0;。

else

{

dep1=depth(T->lchild);。

dep2=depth(T->rchild);。

return dep1>dep2?dep1+1:dep2+1;。

}

//------------------------------判断是否是完全二叉树-----------------------------------。

int pd(bitnode *T)。

int l,r,h;

if(T->lchild)。

{

l=pd(T->lchild);。

}

else

l=0;

if(T->rchild)。

{

r=pd(T->rchild);。

}

else

r=0;

if(l==0&&r==0)。

{

return 2;

h=0;

}

if(l==0&&(r==1||r==2||r==3))。

{

return 3;

}

if(l==1&&r==0)。

{

return 1;

}

if(l==1&&(r==1||r==3))。

{

return 3;

}

if(l==1&&r==2)。

{

if(depth(T->lchild)==depth(T->rchild)+1)。

return 1;

else

return 3;

}

if(l==2&&r==0)。

{

return 1;

}

if(l==2&&r==1)。

{

if(depth(T->lchild)==depth(T->rchild))。

return 1;

else

return 3;

}

if(l==2&&r==2)。

{

if(depth(T->lchild)==depth(T->rchild))。

return 2;

else if(depth(T->lchild)==depth(T->rchild)+1)。

return 1;

else

return 0;

}

if(l==2&&r==3)。

{

return 3;

}

if(l==3)

{

return 3;

}

else return 4;。

//------------------------------主函数---------------------------------------------。

int main(void)

bitnode *T=NULL;。

//printf("文件输入为：\n");。

//ifstream in;。

//in.open("cy.txt",ios::in);。

create(T);

cout<<endl;。

cout<<"中序遍历为："<<endl;。

zhongbianli(T);。

cout<<endl;。

cout<<"先序遍历为："<<endl;。

xianbianli(T);。

cout<<endl;。

cout<<"后序遍历为："<<endl;。

houbianli(T);

cout<<endl;。

cout<<endl;。

int t;

t=pd(T);

if(t==1||t==2)。

cout<<"这个二叉树是完全二叉树。"<<endl;。

else

cout<<"这个二叉树不是完全二叉树。"<<endl;。

getchar();

getchar();

return 0;

完全二叉树

创建二叉树的源程序如下：

#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 = 0; i < n; i++)//输入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);。

原文地址：http://www.qianchusai.com/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E5%BB%BA%E7%AB%8B.html