求二叉树的层次遍历代码,求高手!!!
发布网友
发布时间：2022-04-24 10:03
共3个回答
懂视网
时间：2022-05-14 22:06
function BST(){
this.root = null
this.insert = insert
this.find = find
this.mirror = mirror;
}
function Node(data,left,right){
this.data = data
this.left = left
this.right = right
this.show = show
}
function show() {
return this.data;
}
function mirror(root){
if(root == null){
return
}
if(root.left == null && root.right == null){
return
}
let temp = root.left;
root.left = root.right;
root.right = temp;
mirror(root.left)
mirror(root.right)
}
function insert(data){
var n = new Node(data,null,null)
if(this.root == null){
this.root = n
}else{
var current = this.root
while(true){
if(data < current.data){
if(current.left == null){
current.left = n
break
}
current = current.left
}else{
if(current.right == null){
current.right = n
break
}
current = current.right
}
}
}
}
function find(data){
var current = this.root
while(true){
if(data == current.data){
return current
}
current = data < current.data ? current.left : current.right
if(current == null){
return null
}
}
}
function inorder(node){
if(!(node == null)){
inorder(node.left)
console.log(node.show())
inorder(node.right)
}
}
var nums = new BST()
nums.insert(23)
nums.insert(22)
nums.insert(16)
nums.insert(5)
nums.insert(3)
nums.insert(99)
nums.insert(22)
inorder(nums.root)
mirror(nums.root)
console.log(nums.root)很简单的 看就完了。
热心网友
时间：2022-05-14 19:14
//二叉链表的存储typedef struct BiTNode { Datatype data; struct BiTNode *lchild,*rchild;//左右孩子指针}BiTreeNode,*BiTree;
//三叉链表的存储typedef struct BiTNode { Datatype data; struct BiTNode *lchild,*rchild,*parent;}BiTreeNode,*BiTree;
//算法3.1：二叉树的先序遍历递归算法void PreOrder(BiTree bt){ if(bt!=NULL){ visit(bt->data);//访问根结点 PreOrder(bt->lchild); PreOrder(bt->rchild); }}
//算法3.2：二叉树的中序遍历递归算法void InOrder(BiTree bt){ if(bt!=NULL){ InOrder(bt->lchild); visit(bt->data); InOrder(bt->rchild); }}
//算法3.3：二叉树的后序遍历递归算法void InOrder(BiTree bt){ if(bt!=NULL){ InOrder(bt->lchild); InOrder(bt->rchild); visit(bt->data); }}
//算法3.4：二叉树的层次遍历算法void LevelOrder(BiTree bt){ BiTreeNode Queue[MAXNODE]; //定义队列 int front,rear; if(bt==NULL) return //空二叉树，遍历结束 front=-1; rear=0; Queue[rear]=bt; //根结点入队 while(rear!=front){ //队列不空，继续遍历；否则，遍历结束 front++; //出队 visit(Queue[front]->data); //访问刚出队的元素 if(Queue[front]->lchild!=NULL){ //如果有左孩子，左孩子入队 rear++; Queue[rear]=Queue[front]->lchild; } if(Queue[front]->rchild!=NULL){ //如果有右孩子，右孩子入队 rear++; Queue[rear]=Queue[front]->rchild; } }}
//算法3.5：中序遍历的非递归算法void NRInOrder(BiTree bt){ BiTree S[MAXNODE],p=bt;//定义栈 int top=-1; if(bt==NULL) return;//空二叉树，遍历结束 while(!(p==NULL&&top==0)){ while(p!=NULL){ if(top<MAXNODE-1) S[top++]=p;//当前指针p入栈 else{printf("栈溢出\n");return;} p=p->lchild;//指针指向p的左孩子结点 } if(top==-1) return //栈空，结束 else{ p=S[--top];//弹出栈顶元素 visit(p->data);//访问结点的数据域 p=p->rchild;//指向p的右孩子结点 } }}
//算法3.6：根据先序与中序遍历结果建立二叉树void PreInOrd(char preord[],char inord[],int i,int j,int k,int h,BiTree *t)//先序序列从i到j,中序序列从k到h，建立一个二叉树放到t中{ int m; (*t)=new BTNode; (*t)->data=preord[i];//二叉树的根 m=k; while (i[m]!=preord[i])m++;//在中序序列中定位树根 /********递归调用建立左子树******/ if(m==k)(*t)->left=NULL; else PreInOrd(preord,inord,i+1,i+m-k,k,m-1,&(*t)->left); /********递归调用建立左子树******/ if(m==k)(*t)->right=NULL; else PreInOrd(preord,inord,i+1,i+m-k,k,m-1,&(*))->right);}BTree * createBT(char preord[],char inord[],int n,BTree root)//n为二叉树接点的个数，建立的二叉树放在root中{ if(n<=0) root=NULL; else PreInOrd(preord,inord,1,n,1,n,&root) return root;}
//算法3.7：统计二叉树的叶子结点算法int BitreeLeaf(BTree bt) if(bt==NULL) return 0; if(bt->left==NULL & bt->right==NULL) return 1; return (BitreeLeaf(bt->left)+BirLeaf(bt->right));}
//算法3.8：求二叉树深度算法int BitreeDepth (BiTree bt){ if(bt==NULL) return 0; if(bt->lchild==NULL & bt->rchild==NULL) return1; depthL=BitreeDepth(bt->lchild); depthR=BitreeDepth(bt->rchild); return 1+max(depthL,depthR);}
//算法3.12：二叉树的查找算法BiTree SearchBST(BiTree bt,KeyType key){ if(bt==NULL || key==bt->data.key) return bt; if(key<bt->data.key) return SearchBST(bt->lchild,key); else return SearchBST(bt->rchild,key);}
//算法3.13：在二叉树中插入结点int InseartBST(BiTreeNode **bt,Datatype e){ BiTreeNode *qq=new BiTreeNode(),*pp=new BiTreeNode(); BiTreeNode **qq=&qq,*s,**p=&pp; *q=OxO; *p=OxO; if(SearchBST(*bt,e.key,p,q)==0)//待查结点是否在二叉排序树中 { s=new BiTreeNode(); s->data=e;s->lchild=s->rchild=OxO;//待查结点 if(!(*q)) *bt=s;//二叉树的根 else if(e.key<(*q)->data.key) (*q)->lchild=s;//作为左儿子插入 else(*q)->rchild=s;//作为右儿子插入 return 1; } else return 0;}
//算法3.14：在二叉排序树中删除结点int DeleteNode(BitreeNode **t,int key){ BiTreeNode *pp=new BiTreeNode(),*ff=new BiTreeNode; BiTreeNode **p=&pp,*s,*q,**f=&ff; *p=OxO;*f=OxO; int flag=0; if(SearchBST(*t,key,f,p)!=0){ flag=1;//查找成功，置删除标记，待删除结点为p if(!((*p)->rchild)){//结点无右儿子，结点只有一个分支或为叶子结点 if((*f)->lchild==*p) (*f)->lchild=(*P)->lchild; else (*f)->rchild=(*p)->lchild; } else{//结点有右儿子 if(!((*p)->lchild)){//结点无左儿子，一个分支 if((*f)->lchild==*p) (*f)->lchild=(*P)->rchild; else (*f)->rchild=(*p)->rchild; } else {//结点有左二子，两个分支 q=*p; s=(*p)->lchild; while(s->rchild){q=s;s=s->rchild;}//在结点p的左分支上沿右指针域往下找，直到右指针域为空时为止 (*p)->data=s->data; if(q!=*p){(q)->rchild=s->lchild;} else(q)->lcild=s->lchild; } } } return flag;}
热心网友
时间：2022-05-14 20:32
