创建二叉树算法
⑴ 数据结构-二叉树的创建
如果要在内存中建立一个如下左图这样的树，wield能让每个结点确认是否有左右孩子，我们对它进行扩展，变成如下右图的样子，也就是将二叉树中的每个结点的空指针引出一个虚结点，其值为一个特定值，比如”#”，称之为扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。如前序遍历序列为AB#D##C##。
//创建树方法二
intCreateTree2(BiTree*t)
{
charch;
scanf("%c",&ch);
if(ch=='#')
{
(*t)=NULL;
}
else
{
(*t)=(BiTree)malloc(sizeof(BitNode));
if((*t)==NULL)
{
fprintf(stderr,"malloc()errorinCreateTree2.
");
returnERROR;
}
(*t)->data=ch;
CreateTree2(&((*t)->lchild));
CreateTree2(&((*t)->rchild));
}
returnOK;
}
其实建立二叉树，也是利用了递归的原理。只不过在原来应该打印结点的地方，改成生成结点、给结点赋值的操作而已。因此，完全可以用中序或后序遍历的方式实现二叉树的建立，只不过代码里生成结点和构造左右子树的代码顺序交互一下即可。
⑵ 二叉树如何建立
先序递归创建二叉树，并对其进行 先序、中序、后序遍历
#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树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)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
⑶ 1、创建一棵二叉树，以二叉链表作存储结构，实现先根遍历算法 2、创建一棵二叉树，实现先根遍历算法、中根
你需要的东西这里面都包含了，你自己看哪里用得上就摘一段下来吧。
// 数据结构.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#define MAX 20
#define NULL 0
typedef char ElemType;
typedef int Status;
typedef enum{link,thread} pointertag;
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
pointertag Ltag,Rtag;
}BiTNode,*BiTree;
BiTree pre;
Status CreateBiTree(BiTree *T)//按前序构建二叉树。
{
char ch;
ch=getchar();
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
(*T)->data=ch;
(*T)->Ltag=(*T)->Rtag=link;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return 1;
}
Status CreateBiTree1(BiTree *T)//按中序输入构建二叉树。
{
char ch;
ch=getchar();
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
CreateBiTree(&(*T)->lchild);
(*T)->data=ch;
CreateBiTree(&(*T)->rchild);
}
return 1;
}
void MidOrder(BiTree T)//递归中序输出。
{
if(T)
{
MidOrder(T->lchild);
printf("%2c",T->data);
MidOrder(T->rchild);
}
}
void PreOrder(BiTree T)//前序输出。
{
if(T)
{
printf("%2c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void EndOrder(BiTree T)//后序输出。
{
if(T)
{
EndOrder(T->lchild);
EndOrder(T->rchild);
printf("%2c",T->data);
}
}
void MidOrder1(BiTree T)//非递归中序输出。
{
int i=0;
BiTree p,s[100];
p=T;
do
{
while(p)
{
s[i++]=p;
p=p->lchild;
}
if(i>0)
{
p=s[--i];
printf("%2c",p->data);
p=p->rchild;
}
}while(i>0||p!=NULL);
}
void Levle(BiTree T)//按层次遍历二叉树。
{
BiTree Queue[MAX],b;
int front,rear;
front=rear=0;
if(T)
{
Queue[rear++]=T;
while(front!=rear)
{
b=Queue[front++];
printf("%2c",b->data);
if(b->lchild!=NULL)
Queue[rear++]=b->lchild;
if(b->rchild!=NULL)
Queue[rear++]=b->rchild;
}
}
}
int depth(BiTree 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;
}
}
void InThreading(BiTree p)//线索化。
{
if(p)
{
InThreading(p->lchild);
if(p->lchild=NULL){p->Ltag=thread;p->lchild=pre;}
if(pre->rchild==NULL){pre->Rtag=thread;pre->rchild=p;}
pre=p;
InThreading(p->rchild);
}
}
Status InorderThreading(BiTree *Thrt,BiTree T)//中序遍历二叉树T，并将其线索化。
{
(*Thrt)=(BiTree)malloc(sizeof(BiTNode));
(*Thrt)->Ltag=link;
(*Thrt)->Rtag=thread;
(*Thrt)->rchild=*Thrt;
if(T==NULL)
(*Thrt)->lchild=*Thrt;
else
{
(*Thrt)->lchild=T;
pre=*Thrt;
InThreading(T);
pre->rchild=(*Thrt);
pre->Rtag=thread;
(*Thrt)->rchild=pre;
}
return 1;
}
Status InorderTraverse(BiTree Thrt)//中序遍历线索二叉树Thrt,Thrt指向头结点。
{
BiTree p;
p=Thrt->lchild;
while(p!=Thrt)
{
while(p->Ltag==link)p=p->lchild;
printf("%2c",p->data);
while(p->Rtag==thread&&p->lchild!=Thrt)
{
p=p->rchild;
printf("%2c",p->data);
}
p=p->rchild;
}
return 1;
}
void main()
{
BiTree T=NULL,Thrt=NULL;
printf("创建一个二叉树\n");
CreateBiTree(&T);
//InorderThreading(&Thrt,T);
//InorderTraverse(Thrt);
//printf("中序遍历的结果是：");
//MidOrder(T);
//printf("\n");
printf("先序遍历的结果是：");
PreOrder(T);
printf("\n");
/*printf("后序遍历的结果是：");
EndOrder(T);
printf("\n");
printf("按层次遍历二叉树的结果是：");
Levle(T);
printf("\n");
printf("深度输出为：%d",depth(T));
printf("\n");*/
}
⑷ 二叉树的建立
// 中序遍历伪代码：非递归版本，用栈实现，版本2
void InOrder2(TNode* root)
{
Stack S;
if( root != NULL )
{
S.push(root);
}
while ( !S.empty() )
{
TNode* node = S.pop();
if ( node->bPushed )
{ // 如果标识位为true,则表示其左右子树都已经入栈，那么现在就需要访问该节点了
Visit(node);
}
else
{ // 左右子树尚未入栈，则依次将 右节点，根节点，左节点 入栈
if ( node->right != NULL )
{
node->right->bPushed = false; // 左右子树均设置为false
S.push(node->right);
}
node->bPushed = true; // 根节点标志位为true
S.push(node);
if ( node->left != NULL )
{
node->left->bPushed = false;
S.push(node->left);
}
}
}
}
对比先序遍历，这个算法需要额外的增加O(n)的标志位空间。另外，栈空间也扩大，因为每次压栈的时候都压入根节点与左右节点，因此栈空间为O(n)。时间复杂度方面，每个节点压栈两次，作为子节点压栈一次，作为根节点压栈一次，弹栈也是两次。因此无论从哪个方面讲，这个方法效率都不及InOrder1。
后序
void postOrder(TreeNode<T> *root)
{
stack<TreeNode<T>*> st;
TreeNode<T> *p = root;
TreeNode<T> *pre = NULL;//pre表示最近一次访问的结点
while(p || st.size()!=0)
{
//沿着左孩子方向走到最左下 。
while(p)
{
st.push(p);
p = p->left;
}
//get the top element of the stack
p = st.top();
//如果p没有右孩子或者其右孩子刚刚被访问过
if(p->right == NULL || p->right == pre)
{
/ isit this element and then pop it
cout << "visit: " << p->data << endl;
st.pop();
pre = p;
p = NULL;
}
else
{
p = p->right;
}
}//end of while(p || st.size()!=0)
}
怎么样
⑸ java构建二叉树算法
//******************************************************************************************************//
//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//
//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//
//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//
//*******************************CopyRight By phoenix*******************************************//
//************************************Jan 12,2008*************************************************//
//****************************************************************************************************//
public class BinTree {
public final static int MAX=40;
private Object data; //数据元数
private BinTree left,right; //指向左,右孩子结点的链
BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点
int front;//层次遍历时队首
int rear;//层次遍历时队尾
public BinTree()
{
}
public BinTree(Object data)
{ //构造有值结点
this.data = data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //构造有值结点
this.data = data;
this.left = left;
this.right = right;
}
public String toString()
{
return data.toString();
}//前序遍历二叉树
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}//中序遍历二叉树
public void inOrder(BinTree parent){
if(parent == null)
return;
inOrder(parent.left);
System.out.print(parent.data+" ");
inOrder(parent.right);
}//后序遍历二叉树
public void postOrder(BinTree parent){
if(parent == null)
return;
postOrder(parent.left);
postOrder(parent.right);
System.out.print(parent.data+" ");
}// 层次遍历二叉树
public void LayerOrder(BinTree parent)
{
elements[0]=parent;
front=0;rear=1;
while(front<rear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}
}catch(Exception e){break;}
}
}//返回树的叶节点个数
public int leaves()
{
if(this == null)
return 0;
if(left == null&&right == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}//结果返回树的高度
public int height()
{
int heightOfTree;
if(this == null)
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeight<rightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
}
//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object object)
{
int levelInTree;
if(this == null)
return -1;
if(object == data)
return 1;//规定根节点为第一层
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel<0&&rightLevel<0)
return -1;
levelInTree = leftLevel<rightLevel?rightLevel:leftLevel;
return 1+levelInTree;
}
//将树中的每个节点的孩子对换位置
public void reflect()
{
if(this == null)
return;
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}// 将树中的所有节点移走,并输出移走的节点
public void defoliate()
{
String innerNode = "";
if(this == null)
return;
//若本节点是叶节点，则将其移走
if(left==null&&right == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左子树若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本节点，放在中间表示中跟移走...
innerNode += this + " ";
data = null;
//移走右子树若其存在
if(right!=null){
right.defoliate();
right = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交换每个节点的孩子节点后......");
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
}
⑹ 二叉树的创建与访问算法的设计
Node{
Node* left;
Node* right;
int value;
};
void traverse(Node* tree)
{
if( !tree) return;
traverse(tree->left);
traverse(tree->right);
// do something here on tree->value -> e.g.
printf("%d\n", tree->value);
}
Finish entering tree elements by yourself.
⑺ 请问C语言如何创建二叉树
创建二叉树的源程序如下：
#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;
}
(7)创建二叉树算法扩展阅读：
简单二叉树定义范例：此树的顺序结构为：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 <iostream.h>
typedef struct BiTNode
{
char data;
int bit;
struct BiTNode *lchild,*rchild,*parent;
}BiTNode;
void InitBT(BiTNode *&t)//1、初始化，不带头结点
{
t=NULL;
}
/*void InitBT(BiTNode *t)//初始化，带头结点
{
t=new BiTNode;
t->lchild=t->rchild=t->parent=NULL;
}*/
int EmptyBT(BiTNode *t)//判断队空
{
if(t==0)
return 1;
else
return 0;
}
BiTNode *creatBT(BiTNode *t,int b)//2、创建二叉树
{
BiTNode *p;
char ch;
cin>>ch;
if(ch=='#')return 0;
else
{
p=new BiTNode;
p->data=ch;
p->parent=t;
p->bit=b;
t=p;
t->lchild=creatBT(t,0);
t->rchild=creatBT(t,1);
}
return t;
}
void preorder(BiTNode *t)//3、先序遍历
{
if(!EmptyBT(t))
{
cout<<t->data;
preorder(t->lchild);
preorder(t->rchild);
}
}
void inorder(BiTNode *t)//中序遍历
{
if(!EmptyBT(t))
{
inorder(t->lchild);
cout<<t->data;
inorder(t->rchild);
}
}
void postorder(BiTNode *t)//后序遍历
{
if(!EmptyBT(t))
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data;
}
}
void coutBT(BiTNode *t,int &m,int &n,int &i)//4、计算二叉树中叶子结点、度为2的结点和度为1的结点的个数
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
m++;//叶子结点
else if((t->lchild!=0) && (t->rchild!=0))
i++;//度为2的结点
else
n++;//度为1的结点
coutBT(t->lchild,m,n,i);
coutBT(t->rchild,m,n,i);
}
}
void coutNode(BiTNode *t,int &k)//5、求二叉树中结点个数
{
if(!EmptyBT(t))
{
k++;
coutNode(t->lchild,k);
coutNode(t->rchild,k);
}
}
int BTdepth(BiTNode *t)//6、求二叉树的深度
{
int i,j;
if(EmptyBT(t))
return 0;
else
{
i=BTdepth(t->lchild);
j=BTdepth(t->rchild);
return (i>j?i:j)+1;
}
}
int Xdepth(BiTNode *t,char x)//7、查找x的层数
{
int num1,num2,n;
if(t==NULL)
return 0;
else{
if(t->data==x)
return 1;
num1=Xdepth(t->lchild,x);
num2=Xdepth(t->rchild,x);
n=num1+num2;
if(num1!=0||num2!=0)
n++;
return n;
}
}
static int flag;
void SearchChild(BiTNode *t,int k)//8、查找第k个结点的左右孩子
{
if(!EmptyBT(t))
{
if(k==0)
{
cout<<"位置不能为0!"<<endl;
return;
}
else
{
flag++;
if(flag==k)
{
if(t->lchild==0)
cout<<"无左孩子! ";
else
cout<<"左孩子为："<<(t->lchild->data)<<" ";
if(t->rchild==0)
cout<<"无右孩子!"<<endl;
else
cout<<"右孩子为："<<(t->rchild->data)<<endl;
}
else
{
SearchChild(t->lchild,k);
SearchChild(t->rchild,k);
}
}
}
}
int Xancestor(BiTNode *t,char x)//9、查找x结点祖先
{
int n,num1,num2;
if(t==NULL)
return 0;
else
{
if(t->data==x)
return 1;
num1=Xancestor(t->lchild,x);
num2=Xancestor(t->rchild,x);
n=num1+num2;
if(n!=0)
{
n++;
cout<<t->data<<" "<<endl;
}
}
}
void BTNodePath(BiTNode *t)//10、输出所有叶子结点路径
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
{
cout<<t->data<<"的路径为：";
for(BiTNode *p=t;p!=0;p=p->parent)
cout<<p->data;
cout<<endl;
}
else
{
BTNodePath(t->lchild);
BTNodePath(t->rchild);
}
}
}
void BTNodebit(BiTNode *t)//11、输出所有叶子结点编码
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
{
cout<<t->data<<"的编码为：";
for(BiTNode *p=t;p->parent!=0;p=p->parent)
cout<<p->bit;
cout<<endl;
}
else
{
BTNodebit(t->lchild);
BTNodebit(t->rchild);
}
}
}
void main()
{
BiTNode *t;
int m,n,i,d,q,k;
char x;
cout<<"1、初始化..."<<endl;
InitBT(t);
cout<<"2、创建二叉树..."<<endl;
t=creatBT(t,0);
cout<<"3.1、先序遍历..."<<endl;
preorder(t);
cout<<endl;
cout<<"3.2、中序遍历..."<<endl;
inorder(t);
cout<<endl;
cout<<"3.3、后序遍历..."<<endl;
postorder(t);
cout<<endl;
m=n=i=0;
cout<<"4、计算叶子结点，度为1的结点和度为2的结点的个数..."<<endl;
coutBT(t,m,n,i);
cout<<"叶子结点个数为："<<m<<endl;
cout<<"度为1的结点个数为："<<n<<endl;
cout<<"度为2的结点个数为："<<i<<endl;
q=0;
cout<<"5、计算结点个数..."<<endl;
coutNode(t,q);
cout<<"结点个数为："<<q<<endl;
d=0;
cout<<"6、计算深度..."<<endl;
d=BTdepth(t);
cout<<"深度为："<<d<<endl;
cout<<"7、求x的层数..."<<endl;
cout<<"输入x：";
cin>>x;
if(Xdepth(t,x)==0)
cout<<"x不存在！"<<endl;
else
cout<<Xdepth(t,x)<<endl;
cout<<"8、输入要查找孩子的结点在先序遍历中的位置k（不等于0）：";
cin>>k;
SearchChild(t,k);
if(k>flag)
cout<<"位置超出长度!"<<endl;
cout<<"9、查询结点的所有祖先，请输入结点x：";
cin>>x;
int num;
num=Xancestor(t,x);
if(num==0)
cout<<"结点不存在！"<<endl;
if(num==1)
cout<<"根结点无祖先！"<<endl;
cout<<"10、输出所有叶子结点路径（叶→根）："<<endl;
BTNodePath(t);
cout<<"11、输出所有叶子结点编码（叶→根）："<<endl;
BTNodebit(t);
}
⑼ 怎样理解递归建立二叉树算法
递归=传递+回归，即任务的下放和结果的回收。
这个需要自己慢慢体会，其实所有递归算法实质上都是一样的，理解了就万变不离其宗了。
create（node
*root）
{
root=new
node；
写上关于root的信息//初始化root节点
if(root满足自定义的条件)//自定义一个递归的条件，即传递和回归的界限，这是必须的。
{
create(root->lchild);//建左子树
create(root->rchild);//建右子树
}
}
总体上来看，建一颗树，每一次调用creat（）都是只创建一个节点，把剩下的任务下放给create（root->lchild)和create(root->rchild)
，而这两个也会重复第一个create（root）的做法，实质体现的是任务的不断下放，当达到最后的回归的界限的，结果又将不断回收，对应的是函数的不断返回，实质是退栈的过程。这个过程其实经历了一个不断进栈和不断出栈的过程，对应的是任务的不断下放和不断提交，最后栈空，即告全部任务完成！