二叉树bt的存储结构
❶ 数据结构中的二叉树题目,求大神帮忙做下,谢谢!
设二叉树bt的一种存储结构如表所示。其中，bt为树根结点指针，lchild、rchild分别为结点的左、右孩子指针域，使用结点编号作为指针域值，0表示指针域值为空；data为结点的数据域。请完成：（1）画出二叉树bt的树形表示。（2）写出按先序、中序和后序遍历二叉树bt所得到的结点序列。
❷ 在vb中二叉树是什么东西，我们的书上没有，而且二叉树的相关知识有哪些要考，最后二叉树的结点怎么算。
二叉树
在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的（i-1）次方个结点；深度为k的二叉树至多有2k次 − 1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
树和二叉树的2个主要差别：
1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
2. 树的结点无左、右之分，而二叉树的结点有左、右之分。……
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
❸ 二叉树的存储方式有哪些
二叉树的存储方式通常有动态存储。用结构体表示二叉树的一个节点。用数据域保持保存节点的值，用链接语保存两个孩子的指针。还有就是采用满二叉树的顺序存储方式。
❹ 设二叉树的存储结构为二叉链表，试写出算法（C函数）：将所有结点的左右子树互换
1、以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。
#define M 10
typedef int DataType;/*元素的数据类型*/
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BitTNode,*BiTree;
int front=0,rear=0;
BitTNode *que[10];
BitTNode *creat()
{BitTNode *t;
DataType x;
scanf("%d",&x);
if(x==0) t=NULL;
else{ t=(BitTNode *)malloc(sizeof(BitTNode));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return(t);
}/*creat*/
/* 前序遍历二叉树t */
void preorder(BiTree t)
{ if(t!=NULL)
{ printf("%4d",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
/* 中序遍历二叉树t */
void inorder(BiTree t)
{ if(t!=NULL)
{ inorder(t->lchild);
printf("%4d",t->data);
inorder(t->rchild);
}
}
/* 后序遍历二叉树t */
void postorder(BiTree t)
{ if(t!=NULL)
{ postorder(t->lchild);
postorder(t->rchild);
printf("%4d",t->data);
}
}
void enqueue(BitTNode *t)
{if (front!=(rear+1)%M)
{ rear=(rear+1)%M;
que[rear]=t;
}
}/*enqueue*/
BitTNode * delqueue()
{ if(front==rear)return NULL;
{ front=(front+1)%M;
return (que[front]);
}
}/*delqueue*/
/* 按层次遍历二叉树t */
void levorder(BiTree t)
{ BitTNode *p;
if(t!=NULL)
{ enqueue(t);
while (front!=rear)
{ p=delqueue();
printf("%4d",p->data);
if(p->lchild!=NULL) enqueue(p->lchild);
if(p->rchild!=NULL) enqueue(p->rchild);
}
}
}/* levorder */
main()
{BitTNode *root;
root=creat();
printf("\n按先序遍历次序生成的二叉树");
printf("\n前序遍历二叉树");
preorder(root);
printf("\n中序遍历二叉树");
inorder(root);
printf("\n后序遍历二叉树");
postorder(root);
printf("\n层次顺序遍历二叉树");
levorder(root);
}
2、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
#include <stdio.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
} BTree;
BTree * createbt( )
{ BTree *q;
struct node1 *s[30];
int j,i,x;
printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");
printf("i,x = ");
scanf("%d,%c",&i,&x);
while(i != 0 && x != '$')
{ q = (BTree*)malloc(sizeof(BTree)); /*建立一个新结点q*/
q->data = x; q->left = NULL; q->right = NULL;
s[i] = q; /*q新结点地址存入s指针数组中*/
if(i != 1) /*i = 1，对应的结点是根结点*/
{ j = i / 2; /*求双亲结点的编号j*/
if(i % 2 == 0)
s[j]->left = q; /*q结点编号为偶数则挂在双亲结点j的左边*/
else
s[j]->right = q; /*q结点编号为奇数则挂在双亲结点j的右边*/
}
printf("i,x = ");
scanf("%d,%c",&i,&x);
}
return s[1]; /*返回根结点地址*/
}
void preorder(BTree *BT)
/* 前序遍历二叉树t */
{ if(BT!=NULL)
{ printf("%4c", BT ->data);
preorder(BT ->left);
preorder(BT ->right);
}
}
int BTreeDepth(BTree *BT)
{
int leftdep,rightdep;
if (BT==NULL)
return(0);
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if (leftdep>rightdep)
return(leftdep+1);
else
return(rightdep+1);
}
}
int nodecount(BTree *BT)
{
if (BT==NULL)
return(0);
else
return(nodecount(BT->left)+nodecount(BT->right)+1);
}
int leafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(1);
else
return(leafcount(BT->left)+leafcount(BT->right));
}
int notleafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(0);
else
return(notleafcount(BT->left)+notleafcount(BT->right)+1);
}
int onesoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if ((BT->left==NULL && BT->right!=NULL) ||
(BT->left!=NULL && BT->right==NULL))
return(onesoncount(BT->left)+onesoncount(BT->right)+1);
else
return(onesoncount(BT->left)+onesoncount(BT->right));
}
int twosoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL || BT->right==NULL)
return(twosoncount(BT->left)+twosoncount(BT->right));
else if (BT->left!=NULL && BT->right!=NULL)
return(twosoncount(BT->left)+twosoncount(BT->right)+1);
}
main()
{
BTree *B;
B=creatree();
printf("\n按先序遍历次序生成的二叉树");
preorder(B);
printf("\n二叉树深度:%d\n",BTreeDepth(B));
printf("总结点个数:%d\n",nodecount(B));
printf("叶子结点个数:%d\n",leafcount(B));
printf("非叶子结点个数:%d\n",notleafcount(B));
printf("具有双孩子结点个数:%d\n",twosoncount(B));
printf("具有单孩子结点个数:%d\n",onesoncount(B));
}
如果还没解决你的问题，可以加我网络HI账号。
❺ 分析题： 5 对于一个栈，给出输入项A、B、C、。如果输入项序列由A，B，C所组成，试给出全部可能的输出
输入项序列是ABC，ACB，BAC。若序列的项属于一个偏序集，则单调递增序列就是其中每个项都大于等于之前的项；
若每个项都严格大于之前的项，这个序列就是严格单调递增的。类似可定义单调递减序列。单调序列是单调函数的一个特例。
(5)二叉树bt的存储结构扩展阅读：
一个相对正式的定义：其项属于集合S的有限序列是一个从 {1,2,...,n} 到S的函数，这里n≥0。属于S的无限序列是从 {1,2,...}（自然数集合）到S的函数。
有限序列也称作 n 元组。一个从所有整数到到集合的函数有时也称作双无限序列，这里将以负整数索引的序列认为是另一个以正整数索引的序列。
❻ 计算机软件基础一，二叉链存储结构存储，求二叉树深度的问题
1
BTnodeDepth、lchilddep、BTNode、rchilddep、lchild和rchild 这些都是变量
其中BTnodeDepth是函数名，BTNode结构体，其他都是简单类型变量
2
因为遍历到当层的话，发现如果还有左子树或者右子树，就要加1遍历下一层。。
❼ 二叉树相关知识
二叉树 (binary tree) 是另一种树型结构，它的特点是每个结点至多只有二棵子 树 (即二叉树中不存在度大于 2的结点 )，并且，二叉树的子树有左右之分，其次序不能任意颠倒 . 二叉树是一种数据结构 :
Binary_tree=(D,R)
其中： D是具有相同特性的数据元素的集合 ;若 D等于空 ,则 R等于空称为空的二叉树 ;若 D等于空则 R是 D上某个二元关系 H的集合，即 R={H}，且
(1) D 中存在唯一的称为根的元素 r，它的关系 H下无前驱 ;
(2) 若 D-{r}不等于空，则 D-{r}={Dl,Dr}，且 Dl交 Dr等于空 ;
(3) 若 Dl不等于空 ,则在 Dl中存在唯一的元素 xl,〈 r,xl〉属于 H，且存在 Dl上的关系 Hl属于 H； 若 Dr不等于空 ,则在 Dr中存在唯一的元素 xr,〈 r,xr〉 >属于 H, 且存 Dr上的关 系 Hr属于 H； H={r,xl,＜ r,xr＞ ,Hl, Hr};
(4) (Dl, Hl) 是一棵合本定义的二叉树，称为根 r的左子树 ,(Dr,Hr)是一棵符合定义的二叉树，称为根的右子树。
其中，图 6.2 是各种形态的二叉树 .
(1) 为空二叉树 (2)只有一个根结点的二叉树 (3)右子树为空的二叉树 (4)左子树为空的二叉树 (5)完全二叉树
二叉树的基本操作：
(1)INITIATE(BT ） 初始化操作。置 BT为空树。
(2)ROOT(BT)\ROOT(x) 求根函数。求二叉树 BT的根结点或求结点 x所在二叉树的根结点。
若 BT是空树或 x不在任何二叉树上，则函数值为 “空 ”。
(3)PARENT(BT,x) 求双亲函数。求二叉树 BT中结点 x的双亲结点。若结点 x是二叉树 BT 的根结点
或二叉树 BT中无 x结点，则函数值为 “空 ”。
(4)LCHILD(BT,x) 和 RCHILD(BT,x) 求孩子结点函数。分别求二叉树 BT中结点 x的左孩 子和右孩子结点。
若结点 x为叶子结点或不在二叉树 BT中，则函数值为 “空 ”。
(5)LSIBLING(BT,x) 和 RSIBING(BT,x) 求兄弟函数。分别求二叉树 BT中结点 x的左兄弟和右兄弟结点。
若结点 x是根结点或不在 BT中或是其双亲的左 /右子树根 ,则函树值 为 “空 ”。
(6)CRT_BT(x,LBT,RBT) 建树操作。生成一棵以结点 x为根，二叉树 LBT和 RBT分别为左， 右子树的二叉树。
(7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子树操作。将以结点 x为根且右子树为空的二叉树
分别置为二叉树 BT中结点 y的左子树和右子树。若结点 y有左子树 /右子树，则插入后是结点 x的右子树。
(8)DEL_LCHILD(BT,x) 和 DEL-RCHILD(BT,x) 删除子树操作。分别删除二叉树 BT中以结点 x为根的左子树或右子树。
若 x无左子树或右子树，则空操作。
(9)TRAVERSE(BT) 遍历操作。按某个次序依此访问二叉树中各个结点，并使每个结点只被访问一次。
(10)CLEAR(BT) 清除结构操作。将二叉树 BT置为空树。
5.2.2 二叉树的存储结构
一 、顺序存储结构
连续的存储单元存储二叉树的数据元素。例如图 6.4(b)的完全二叉树 , 可以向量 (一维数组 ) bt(1:6)作它的存储结构，将二叉树中编号为 i的结点的数据元素存放在分量 bt[i]中 ,如图 6.6(a) 所示。但这种顺序存储结构仅适合于完全二叉树 ,而一般二叉树也按这种形式来存储 ,这将造成存 贮浪费。如和图 6.4(c)的二叉树相应的存储结构图 6.6(b)所示，图中以 “0”表示不存在此结点 .
二、 链式存储结构
由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成 ,则表 示二叉树的链表中的结点至少包含三个域 :数据域和左右指针域 ,如图 (b)所示。有时 ,为了便于找 到结点的双亲 ,则还可在结点结构中增加一个指向其双亲受的指针域，如图 6.7(c)所示。
5.3 遍历二叉树
遍历二叉树 (traversing binary tree)的问题， 即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 其中常见的有三种情况：分别称之为先 (根 )序遍历，中 (根 )序遍历和后 (根 )序遍历。
5.3.1 前序遍历
前序遍历运算：即先访问根结点，再前序遍历左子树，最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。例如：
按前序遍历此二叉树的结果为： Hello!How are you?
proc preorder(bt:bitreprtr)
if (bt<>null)[
print(bt^);
preorder(bt^.lchild);
preorder(bt^.rchild);]
end;
5.3.2 中序遍历
中序遍历运算：即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。例如：
按中序遍历此二叉树的结果为： a*b-c
proc inorder(bt:bitreprtr)
if (bt<>null)[
inorder(bt^.lchild);
print(bt^);
niorder(bt^.rchild);]
end;
5.3.3 后序遍历
后序遍历运算：即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。例如：
按后序遍历此二叉树的结果为： Welecome to use it!
proc postorder(bt:bitreprtr)
if (bt<>null)[
postorder(bt^.lchild);
postorder(bt^.rchild);]
print(bt^);
end;
五、例：
1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。
2.用链表存储方式建立一棵如图三、4所示的二叉树，并对其进行先序遍历。
3.给出一组数据：R={10.18,3,8,12,2,7,3}，试编程序，先构造一棵二叉树，然后以中序遍历访问所得到的二叉树，并输出遍历结果。
4.给出八枚金币a,b,c,d,e,f,g,h，编程以称最少的次数，判定它们蹭是否有假币，如果有，请找出这枚假币，并判定这枚假币是重了还是轻了。
❽ 设二叉树bt存储结构如下
字符a是根结点,a的左分支是b,而a没有右分支.
二叉树示意图:
a
/
b
/
cd
//
efg
//
hi
/
j
二叉树的(链式)逻辑结构示意图:
#a^
/
#b#
/
#c^#d#
//
^e^#f^#g^
//
^h^#i^
/
^j^
上述示意图,符号#表示指针域,符号^表示NULL(空指针)
先序遍历序列:abcedfhgij
中序遍历序列:ecbhfdjiga
后序遍历序列:echfjigdba
//C语言测试程序
#include"stdio.h"
#include"stdlib.h"
structtree
{
chardata;
structtree*left;
structtree*right;
};
typedefstructtreetreenode;
typedeftreenode*btree;
btreecreatebtree(char*data,intpos,intmaxPos)//递归创建法
{
btreenewnode;
if(data[pos]==0||pos>maxPos)
{
returnNULL;
}
else
{
newnode=(btree)malloc(sizeof(treenode));
newnode->data=data[pos];
newnode->left=createbtree(data,2*pos,maxPos);
newnode->right=createbtree(data,2*pos+1,maxPos);
returnnewnode;
}
}
voidpreorder(btreeptr)//先序遍历(递归法)
{
if(ptr!=NULL)
{
printf("%C",ptr->data);
preorder(ptr->left);
preorder(ptr->right);
}
}
voidinorder(btreeptr)//中序遍历(递归法)
{
if(ptr!=NULL)
{
inorder(ptr->left);
printf("%C",ptr->data);
inorder(ptr->right);
}
}
voidpostorder(btreeptr)//后序遍历(递归法)
{
if(ptr!=NULL)
{
postorder(ptr->left);
postorder(ptr->right);
printf("%C",ptr->data);
}
}
intmain()
{
btreeroot=NULL;
inti;
chardata[64]={0,'a','b',0,'c','d',0,0,
'e',0,'f','g',0,0,0,0,
0,0,0,0,'h',0,'i',0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,'j',0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0};
root=createbtree(data,1,63);
printf("二叉树的顺序存储内容:");
for(i=1;i<64;i++)
{
if(data[i]==0)
{
printf("^");
}
else
{
printf("%c",data[i]);
}
}
printf(" 二叉树的先序遍历序列:");
preorder(root);
printf(" 二叉树的中序遍历序列:");
inorder(root);
printf(" 二叉树的后序遍历序列:");
postorder(root);
printf(" ");
return0;
}
❾ 急！二叉树的存储结构，并完成：建立、查找、计算结点数、求高度、三种遍历方式
public class BinaryTree<E> //二叉树类
{
protected BinaryNode<E> root; //根结点
public BinaryTree() //构造空二叉树
{
root=null;
}
public BinaryTree(BinaryNode<E> root) //构造指定根结点的二叉树
{
this.root=root;
}
public boolean isEmpty() //判断是否空二叉树
{
return this.root==null;
}
public BinaryNode<E> getRoot() //返回二叉树的根结点
{
return this.root;
}
//6.3.3 二叉树的遍历
public void preOrder() //先根次序遍历二叉树
{
System.out.print("\n先根序列： ");
preOrder(root);
}
private void preOrder(BinaryNode<E> p) //先根次序遍历以p结点为根的子二叉树
{
if(p!=null) //若二叉树不空
{
System.out.print(p.data+" "); //访问当前结点
preOrder(p.left); //按先根次序遍历当前结点的左子树
preOrder(p.right); //按先根次序遍历当前结点的右子树
}
}
public void inOrder() //中根次序遍历二叉树
{
System.out.print("\n中根序列： ");
inOrder(root);
}
private void inOrder(BinaryNode<E> p) //中根次序遍历以p结点为根的子二叉树
{
if (p!=null)
{
inOrder(p.left); //中根次序遍历左子树
System.out.print(p.data+" ");
inOrder(p.right); //中根次序遍历右子树
}
}
public void postOrder() //后根次序遍历二叉树
{
System.out.print("\n后根序列： ");
postOrder(root);
}
private void postOrder(BinaryNode<E> p) //后根次序遍历以p结点为根的子二叉树
{
if (p!=null)
{
postOrder(p.left);
postOrder(p.right);
System.out.print(p.data+" ");
}
}
//【例6.1】 构造并遍历二叉树。
//3. 基于遍历的操作
public int count() //求一棵二叉树中所有结点个数
{
return count(root);
}
public int count(BinaryNode<E> p) //求以p结点为根的子树的结点个数
{
if (p!=null)
return 1+count(p.left)+count(p.right);
else
return 0;
}
public int depth() //求二叉树的深度
{
return depth(root);
}
public int depth(BinaryNode<E> p) //求以p结点为根的子树的深度，后根次序遍历
{
if (p!=null)
{
int ld = depth(p.left); //求左子树的深度
int rd = depth(p.right);
return (ld>=rd) ? ld+1 : rd+1;
}
return 0;
}
public BinaryNode<E> search(E value) //查找值为value的结点
{
return search(root, value);
}
public BinaryNode<E> search(BinaryNode<E> p, E value) //在以p为根的子树中查找值为value的结点
{ //先根次序遍历，返回查找到结点，若未找到返回null
BinaryNode<E> find=null; //记载找到结点
if (p!=null && value!=null)
{
if (p.data.equals(value))
find = p; //查找成功
else
{
find = search(p.left, value); //在左子树中查找
if (find==null)
find=search(p.right, value); //若左子树中未找到，则继续在右子树中查找
}
}
return find; //返回找到结点
}
public BinaryNode<E> getParent(BinaryNode<E> node) //返回指定结点node的父母结点
{ //若空树、未找到或node为根，返回null
if (root==null || node==null || node==root)
return null;
return getParent(root, node);
}
public BinaryNode<E> getParent(BinaryNode<E> p, BinaryNode<E> node)
{ //在以p为根的子树中查找并返回node结点的父母结点
BinaryNode<E> find=null; //记载找到结点
if (p!=null)
{
if (p.left==node || p.right==node)
find = p; //查找成功
else
{
find = getParent(p.left, node); //在左子树中查找
if (find==null)
find = getParent(p.right, node); //若左子树中未找到，则继续在右子树中查找
}
}
return find; //返回找到的父母结点
}
//6.3.4 构造二叉树
// 1、以先根、中根次序遍历序列建立二叉树
public BinaryTree(String prestr,String instr) //1、以先根、中根次序遍历序列建立二叉树
{
root=create(prestr,instr);
//root=create2(prestr,instr);
}
public BinaryNode create(String prestr, String instr)
{
BinaryNode<String> p=null;
int k,n;
String first,presub,insub;
n=prestr.length();
if(n>0)
{
System.out.print("prestr="+prestr+"\t instr="+instr);
first=prestr.substring(0,1);
p=new BinaryNode<String>(first);
k=instr.indexOf(first);
System.out.println("\t first="+first+"\t k="+k);
presub=prestr.substring(1,k+1);
insub=instr.substring(0,k);
p.left=create(presub,insub);
presub=prestr.substring(k+1,n);
insub=instr.substring(k+1,n);
p.right=create(presub,insub);
}
return p;
}
public BinaryNode create2(String instr, String poststr) //以中根、后根次序遍历序列建立二叉树
{
BinaryNode<String> p=null;
int k,n;
String last,postsub,insub;
n=poststr.length();
if(n>0)
{
System.out.print("instr="+instr+"\t poststr="+poststr);
last=poststr.substring(poststr.length()-1,poststr.length());
p=new BinaryNode<String>(last);
k=instr.indexOf(last);
System.out.println("\t last="+last+"\t k="+k);
postsub=poststr.substring(0,k);
insub=instr.substring(0,k);
p.left=create2(insub,postsub);
postsub=poststr.substring(k,n-1);
insub=instr.substring(k+1,n);
p.right=create2(insub,postsub);
}
return p;
}
// 2、以标明空子树的先根序列构造一棵二叉树
public BinaryTree(E[] preorder) //2、以标明空子树的先根序列构造一棵二叉树
{
root=create(preorder);
}
private int i=0;
private BinaryNode<E> create(E[] preorder) //创建一棵子树，当前结点值是preorder[i]
{ //返回所创建子树的根结点
BinaryNode<E> p = null;
if (i<preorder.length)
{
E elem=preorder[i];
i++;
if (elem!=null)
{
p = new BinaryNode<E>(elem); //建立p结点
p.left = create(preorder); //建立p的左子树
p.right = create(preorder); //建立p的右子树
}
}
return p;
}
// 3、以广义表表示建立二叉树
public BinaryTree(String GenListStr)
{
System.out.println("GenListStr="+GenListStr);
if(GenListStr.length()>0)
root=create(GenListStr); //以GenListStr的全部元素建立一棵二叉树
}
public BinaryNode create(String GenListStr) //以GenListStr的部分元素（从i开始）建立一棵子树
{
BinaryNode p=null;
char ch=GenListStr.charAt(i);
if(ch>='A' && ch<='Z') //大写字母
{
p=new BinaryNode<String>(ch+""); //建立结点
i++; //跳过大写字母
ch=GenListStr.charAt(i);
if(ch=='(')
{
i++; //跳过(
p.left=create(GenListStr); //建立左子树
i++; //跳过#
p.right=create(GenListStr); //建立右子树
i++; //跳过）
}
}
if(ch=='#')
i++; //跳过#
return p; //ch非大写字母时，返回null
}
//【例6.2】 输出二叉树中指定结点的所有祖先结点。
//6.3.5 二叉树的插入和删除操作
public void insert(BinaryNode<E> p, E element, boolean leftChild) //插入元素element作为p结点的孩子
{ //若leftChild为true，插入结点作为左孩子，否则作为右孩子
if (p!=null)
{
BinaryNode<E> q = new BinaryNode<E>(element);
if (leftChild)
{
q.left = p.left; //p结点的原左孩子成为q结点的左孩子
p.left = q; //q结点作为p结点的左孩子
}
else
{
q.right = p.right; //p结点的原右孩子成为q结点的右孩子
p.right = q; //q结点作为p结点的右孩子
}
}
}
public void insert(BinaryNode<E> p, E element) //插入元素element作为p结点的左孩子
{
insert(p, element, true);
}
public void remove(BinaryNode<E> p, boolean leftChild) //删除p结点的左/右子树
{ //若leftChild为true，删除左子树，否则删除右子树
if (p!=null)
{
if (leftChild)
p.left = null;
else
p.right = null;
}
}
public void remove(BinaryNode<E> p) //删除p结点的左子树
{
remove(p, true);
}
//6.3.6 二叉树遍历的非递归算法
public void preOrderTraverse() //先根次序遍历二叉树的非递归算法
{
System.out.print("先根次序遍历（非递归）： ");
LinkedStack<BinaryNode<E>> stack = new LinkedStack<BinaryNode<E>>(); //创建一个空栈
BinaryNode<E> p = this.root;
while(p!=null || !stack.isEmpty()) //p非空或栈非空时
if(p!=null)
{
System.out.print(p.data+" "); //访问结点
stack.push(p); //p结点入栈
p=p.left; //进入左子树
}
else //p为空且栈非空时
{
p=stack.pop(); //p指向出栈结点
p=p.right; //进入右子树
}
System.out.println();
}
public void inOrderTraverse() //中根次序遍历二叉树的非递归算法
{
System.out.print("中根次序遍历（非递归）： ");
LinkedStack<BinaryNode<E>> stack = new LinkedStack<BinaryNode<E>>(); //创建一个空栈
BinaryNode<E> p = this.root;
while(p!=null || !stack.isEmpty()) //p非空或栈非空时
if(p!=null)
{
stack.push(p); //p结点入栈
p=p.left; //进入左子树
}
else //p为空且栈非空时
{
p=stack.pop(); //p指向出栈结点
System.out.print(p.data+" "); //访问结点
p=p.right; //进入右子树
}
System.out.println();
}
//后根次序未写
//6.3.7 二叉树的层次遍历
public void levelOrder() //按层次遍历二叉树
{
LinkedQueue<BinaryNode<E>> que=new LinkedQueue<BinaryNode<E>>(); //创建一个空队列
BinaryNode<E> p=this.root;
System.out.print("层次遍历： ");
while(p!=null)
{
System.out.print(p.data+ " ");
if(p.left!=null)
que.enqueue(p.left); //p的左孩子结点入队
if(p.right!=null)
que.enqueue(p.right); //p的右孩子结点入队
p = que.dequeue(); //p指向出队结点
}
System.out.println();
}
//第6章习题
public void leaf() //遍历输出叶子结点
{
leaf(root);
}
private void leaf(BinaryNode<E> p) //先根次序遍历，输出叶子结点，3种遍历次序结果一样
{
if(p!=null)
{
if (p.isLeaf())
System.out.print(p.data+" ");
leaf(p.left);
leaf(p.right);
}
}
public int countLeaf() //求一棵二叉树中所有叶子结点个数
{
return countLeaf(root);
}
private int countLeaf(BinaryNode<E> p) //求以p结点为根的子树的叶子结点个数
{
if (p==null)
return 0;
if (p.isLeaf())
return 1;
return countLeaf(p.left)+countLeaf(p.right);
}
public BinaryTree(BinaryTree<E> bitree) //以已知的bitree构造二叉树
{
this.root = (bitree.root);
}
private BinaryNode<E> (BinaryNode<E> p) //复制以p根的子二叉树
{
BinaryNode<E> q = null;
if(p!=null)
{
q = new BinaryNode<E>(p.data);
q.left = (p.left); //复制左子树
q.right = (p.right); //复制右子树
}
return q; //返回建立子树的根结点
}
public boolean equals(Object obj) //比较两棵二叉树是否相等
{
if (obj == this)
return true;
if (obj instanceof BinaryTree)
{
BinaryTree<E> bitree = (BinaryTree)obj;
return equals(this.root, bitree.root);
}
return false;
}
private boolean equals(BinaryNode<E> p, BinaryNode<E> q) //判断以p和q结点为根的两棵子树是否相等
{ //递归方法
if(p==null && q==null)
return true;
if(p!=null && q!=null)
return (p.data.equals(q.data)) && equals(p.left, q.left) && equals(p.right, q.right);
return false;
}
public boolean replace(E old, E value) //将首次出现的值为old结点值替换为value
{
BinaryNode<E> find=search(old); //查找值为old的结点
if(find!=null)
find.data = value; //替换结点元素值
return find!=null;
}
public void replaceAll(E old, E value) //将值为old的结点全部替换为value
{
replaceAll(root, old, value);
}
private void replaceAll(BinaryNode<E> p, E old, E value) //在以p为根的子树中实现全部替换
{
if(p!=null)
{
if(p.data.equals(old))
p.data = value;
replaceAll(p.left, old, value);
replaceAll(p.right, old, value);
}
}
public static void main(String args[])
{
String[] preorder = {"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","H"};
BinaryTree<String> bitree = new BinaryTree<String>(preorder);
preorder[0]="Z";
bitree.preOrder();
bitree.inOrder();
bitree.postOrder();
System.out.println("\n结点个数： "+bitree.count());
System.out.println("高度： "+bitree.depth());
System.out.print("叶子结点： ");
bitree.leaf();
System.out.println(" , 共"+bitree.countLeaf()+"个");
BinaryTree<String> bitree2 = new BinaryTree<String>(bitree);
System.out.println("两棵二叉树相等? "+bitree.equals(bitree2));
System.out.println("第2棵二叉树替换(\"D\",\"F\")： "+bitree2.replace("D","F"));
System.out.println("两棵二叉树相等? "+bitree.equals(bitree2));
System.out.println("第2棵二叉树全部替换(\"F\",\"Y\") ");
bitree2.replaceAll("F","Y");
bitree2.preOrder();
BinaryNode<String> find = bitree.search("D"); //查找
bitree.insert(find, "Z");
System.out.println("插入Z作为 "+find.data+" 的左孩子\n");
bitree.levelOrder();
bitree.preOrderTraverse();
bitree.inOrderTraverse();
String[] preorder2 = {"A","B",null,null,"C"}; //标明空子树的先根序列
BinaryTree<String> bitree3 = new BinaryTree<String>(preorder2);
bitree3.preOrder();
bitree3.inOrder();
bitree3.postOrder();
/*
BinaryTree<String> bitree4 = new BinaryTree<String>(preorder2);
bitree4.root = bitree4.create(preorder2); //错，i越界，私有化可避免问题
bitree4.preOrder();
*/
String[] preorder3 = {"D","B","A",null,null,"C",null,null,"E"}; //二叉排序树
BinaryTree<String> bitree5 = new BinaryTree<String>(preorder3);
bitree5.inOrder();
System.out.println("\n二叉排序树? "+bitree5.isSorted());
}
//第8章习题
public boolean isSorted() //判断一棵二叉树是否为二叉排序树
{
return isSorted(this.root);
}
public boolean isSorted(BinaryNode<E> p)
{
boolean yes = true;
if (p!=null)
{
if (!(p.data instanceof Comparable))
return false;
Comparable cmpobj = (Comparable)p.data;
if ((p.left==null || p.left!=null && cmpobj.compareTo(p.left.data)>0) &&
(p.right==null || p.right!=null && cmpobj.compareTo(p.right.data)<0))
{
yes = isSorted(p.left);
if (yes)
yes = isSorted(p.right);
}
else
yes = false;
}
return yes;
}
}
/*
程序运行结果如下：
先根序列： A B D G C E F H
中根序列： D G B A E C H F
后根序列： G D B E H F C A
结点个数： 8
高度： 4
叶子结点： G E H , 共3个
两棵二叉树相等? true
第2棵二叉树替换("D","F")： true
两棵二叉树相等? false
第2棵二叉树全部替换("F","Y")
先根序列： A B Y G C E Y H
第1棵二叉树查找： D
层次遍历： A B C D E F Z G H
先根次序遍历（非递归）： A B D Z G C E F H
中根次序遍历（非递归）： Z D G B A E C H F
先根序列： A B D G C E F H
中根序列： D G B A E C H F
后根序列： G D B E H F C A
中根序列： A B C D E
二叉排序树? true
*/
这是二叉树的所有方法 及实现实例
还有就是需要建立节点类 你应该知道怎么建的吧
❿ 数据结构 二叉树
先介绍一下树：
1.树的定义
树是一种常见的非线性的数据结构。树的递归定义如下：
树是n(n>0)个结点的有限集，这个集合满足以下条件：
⑴有且仅有一个结点没有前件（父亲结点），该结点称为树的根；
⑵除根外，其余的每个结点都有且仅有一个前件；
⑶除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后件（儿子结点）；
2、结点的分类
在树中，一个结点包含一个元素以及所有指向其子树的分支。结点一般分成三类
⑴根结点：没有前件的结点。在树中有且仅有一个根结点。
⑵分支结点：除根结点外，有后件的结点称为分支结点。分支结点亦是其子树的根；
⑶叶结点：没有后件的结点称为树叶。由树的定义可知，树叶本身也是其父结点的子树。
根结点到每一个分支结点或叶结点的路径是唯一的。
3、有关度的定义
⑴结点的度：一个结点的子树数目称为该结点的度。显
然，所有树叶的度为0。
⑵树的度：所有结点中最大的度称为该树的度。4、树的深度（高度）
树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。图（b）中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。
5、有序树和无序树
按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。
6、树的表示方法
树的表示方法一般有两种：
⑴自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。
⑵括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式
（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））
7、树的存储结构一般有两种
⑴静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n为树的度)的数组，分别存储该结点的每一个儿子的下标
⑵动态的多重链表。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成
下面是有关二叉树的内容：
二叉树的概念
二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后件，且其子树有左右之分（次序不能任意颠倒）。
1、二叉树的递归定义和基本形态
二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：
⑴有一个特定的结点称为根；
⑵余下的结点分为互不相交的子集L和R，其中R是根的左子树；L是根的右子树；L和R又是二叉树；
由上述定义可以看出，二叉树和树是两个不同的概念
⑴树的每一个结点可以有任意多个后件，而二叉树中每个结点的后件不能超过2；
⑵树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。
2、二叉树的两个特殊形态
⑴满二叉树： 如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。可以验证具有n个叶结点的满二叉树共有2n-1个结点。
⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树
3、二叉树的三个主要性质
性质1：在二叉树的第i（≥1）层上，最多有2i-1个 结点
证明：我们采用数学归纳法证明：当i=1时只有一个根结点，即2i-1=20=1，结论成立。假设第k(i=k)层上最多有2k-1个结点，考虑i=k+1。由归纳假设，在二叉树第k层上最多有2k-1个结点，而每一个结点最多有两个子结点，因此在第k+1层上最多有2．2k-1=2(k+1)-1=2i，结论成立。综上所述，性质1成立。
性质2：在深度为k(k≥1)的二叉树中最多有2k-1个 结点。
证明：由性质1，在二叉树第i层上最多有2i-1个结点，显然，第1层¨第k层的最多结点数为 个结点。证毕。
性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。
证明：设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然n=n0+n1+n2 （1）
由于二叉树中除了根结点外，其余每个结点都有且仅有一个前件。设 b为二叉树的前件个数，n=b+1（2）
所有这些前件同时又为度为1和度为2的结点的后件。因此又有b=n1+2n2 (3)
我们将（3）代入（2）得出n=n1+2n2+1 (4)
比较（1）和（4），得出n0=n2+1,即叶子数比度为2的结点数多1
4、普通有序树转换成二叉树
普通树为有序树T，将其转化成二叉树T’的规则如下：
⑴T中的结点与T’中的结点一一对应，即T中每个结点的序号和值在T’中保持不变；
⑵T中某结点v的第一个儿子结点为v1，则在T’中v1为对应结点v的左儿子结点；
⑶T中结点v的儿子序列，在T’中被依次链接成一条开始于v1的右链；
由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。
5、二叉树的存储结构
将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括
⑴一个数据域（data）；
⑵三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。
满二叉树和完全二叉树一般采用顺序存储结构
对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。如果二叉树的存储需求量超过64Kb，则采用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：
⑴值域： data
⑵左指针域： lch
⑶右指针域： rch
这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点
6、二叉树的遍历
二叉树遍历的定义：按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。
二叉树遍历的顺序：如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。
前序遍历的规则如下：
若二叉树为空，则退出。否则
⑴访问处理根结点；
⑵前序遍历左子树；
⑶前序遍历右子树；
特点：由左而右逐条访问由根出发的树支 （回溯法的基础）
中序遍历的规则：
若二叉树为空，则退出；否则
⑴中序遍历左子树；
⑵访问处理根结点；
⑶中序遍历右子树；
后序遍历的规则如下：
若二叉树为空，则退出；否则
⑴后序遍历左子树；
⑵后序遍历右子树；
⑶访问处理根结点；
特点：可统计任一个结点为根的子树的情况（例如子树的权和，最优策略的选择（博弈数））