精华内容
下载资源
问答
  • 二叉树的创建

    2014-12-10 21:10:23
    二叉树的创建
    /************************************************************************
    * Create Date                   :2014/12/10
    * Author                        :zhuang_569 
    * Description                   :二叉树的创建
    *************************************************************************/
    #include "iostream"
    using namespace std;
    typedef char ELEM_TYPE;
    typedef struct	BiTNode
    	{
    	    ELEM_TYPE	data;
    	    struct BiTNode *lchild;
    	    struct BiTNode *rchild;	
    	}BiTNode,*pBiTNode;
    
    //函数声明
    pBiTNode CreateBeTree(void);
    void PreOrderTraverse(pBiTNode pRoot);
    void InOrderTraverse(pBiTNode pRoot);
    void PostOrderTraverse(pBiTNode pRoot);
    int main(void)
    {
    	pBiTNode pBeTreeRoot;
    	pBeTreeRoot = CreateBeTree();	//创建二叉树根节点
    	cout<<"二叉树先序输出:";
    	PreOrderTraverse(pBeTreeRoot);
    	cout<<"\n"<<"二叉树中序输出:";
    	InOrderTraverse(pBeTreeRoot);
    	cout<<"\n"<<"二叉树后序输出:";
    	PostOrderTraverse(pBeTreeRoot);
    	return 0;
    }
    
    //利用先序遍历建立二叉树
    pBiTNode CreateBeTree(void)
    {
    	pBiTNode pRoot;			
    	ELEM_TYPE ch;
    	cin >> ch;	
    	if('@' == ch)
    	{
    		pRoot = NULL;
    	}
    	else
    	{
    		pRoot = new BiTNode;	//为新的节点分配内存空间
    		pRoot->data = ch;
    		pRoot->lchild = CreateBeTree();
    		pRoot->rchild = CreateBeTree();
    	}
    		return pRoot;			//返回根节点的地址
    }
    
    //先序遍历二叉树
    void PreOrderTraverse(pBiTNode pRoot)
    {
    	if(NULL != pRoot)
    	{
    	 	cout << pRoot->data;
    		PreOrderTraverse(pRoot->lchild);
    		PreOrderTraverse(pRoot->rchild);
    	}
    }
    
    //中序遍历二叉树
    void InOrderTraverse(pBiTNode pRoot)
    {
    	if(NULL != pRoot)
    	{
    		InOrderTraverse(pRoot->lchild);
    		cout << pRoot->data;
    		InOrderTraverse(pRoot->rchild);
    	}
    }
    
    //后序遍历二叉树
    void PostOrderTraverse(pBiTNode pRoot)
    {
    	if(NULL != pRoot)
    	{
    		PostOrderTraverse(pRoot->lchild);
    		PostOrderTraverse(pRoot->rchild);
    		cout << pRoot->data;
    	}
    }
    
    

    树:



    测试结果:





    展开全文
  • 线索二叉树的创建添加虚结点补足成完全二叉树,对补足虚结点后的二叉树按层次遍历次序输入,并输出前序和中序遍历结果。构建上述二叉树的后序线索化二叉树,输出后序遍历结
  • 二叉树的创建和遍历

    2018-08-30 16:43:29
    关于二叉树的创建及遍历,代码实现功能。二叉树的创建和遍历 主要完成二叉树的创建以及二叉树的先序、中序、后序遍历
  • java二叉树的创建

    2020-11-26 19:51:13
    二叉树的创建一、二叉树二、二叉树的创建 一、二叉树 二叉树是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别...

    一、二叉树

    二叉树是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树 。
    二叉树

    二、二叉树的创建

    思路分析
    使用创建Java创建二叉树时,创建二叉树节点,通过节点递归生成二叉树
    源码
    创建节点

    package tree;
    
    public class NodeTree {
    	//定义数据域
    	int data;
    	//定义左子树
    	NodeTree leftChild;
    	//定义右子树
    	NodeTree rightChild;
    	
    	public NodeTree(int data) {
    		data = -1;
    		leftChild = null;
    		rightChild = null;
    	}
    
    
    
    	public int getData() {
    		return data;
    	}
    
    	public void setData(int data) {
    		this.data = data;
    	}
    
    	public NodeTree getLeftChild() {
    		return leftChild;
    	}
    
    	public void setLeftChild(NodeTree leftChild) {
    		this.leftChild = leftChild;
    	}
    
    	public NodeTree getRightChild() {
    		return rightChild;
    	}
    
    	public void setRightChild(NodeTree rightChild) {
    		this.rightChild = rightChild;
    	}
    
    
    	public void addNode(NodeTree newNode,int data) {
    		//小于根节点放左边
    		if(this.data>newNode.data) {
    			if(this.leftChild==null) {
    				this.leftChild=newNode;
    			}else {
    				this.leftChild.addNode(newNode, data);
    			}
    		}
    		//大于根节点放右边
    		if(this.data<=newNode.data) {
    			if(this.rightChild==null) {
    				this.rightChild=newNode;
    			}else {
    				this.rightChild.addNode(newNode, data);
    			}
    		}
    	}
    
    }
    
    

    创建树

    package tree;
    
    public class BinTree {
    	//根节点
    	NodeTree root;
    	
    	public void add(int data) {
    	//调用节点类
    		NodeTree newTree = new NodeTree(data);
    		if(root ==null) {
    			this.root = newTree;
    		}else {
    			this.root.addNode(newTree, data);
    		}
    		System.out.println("插入成功");
    	}
    	
    }
    
    

    测试类

    package tree;
    
    public class test {
    	public static void main(String[] args) {
    		int[] arr = {34,6,53,76,345,32,2};
    		BinTree binTree = new BinTree();
    		for(int i=0;i<arr.length;i++) {
    			binTree.add(arr[i]);	
    		}
    		System.out.println("添加成功");
    	}
    }
    
    
    展开全文
  • 二叉树_二叉树的创建

    2019-07-30 14:14:28
    二叉树的创建 方法一:给定二叉树的数组元素序列和大小创建二叉树 BtNode * CreateBin(ElemType *ar,int left,int right); BtNode * CreateBinary(ElemType *ar,int n) { if(NULL == ar || n < 1) return NULL;...

    二叉树的创建
    方法一:给定二叉树的数组元素序列和大小创建二叉树
    BtNode * CreateBin(ElemType *ar,int left,int right);
    BtNode * CreateBinary(ElemType *ar,int n)
    {
        if(NULL == ar || n < 1)
            return NULL;
        else
            return CreateBin(ar,0,n-1);
    }
    BtNode * CreateBin(ElemType *ar,int left,int right)
    {
        BtNode *s = NULL;
        if(left <= right)
        {
            int mid = (right - left + 1)/2 + left;
            s = Buynode();
            s->data = ar[mid];
            s->leftchild = CreateBin(ar,left,mid-1);
            s->rightchild = CreateBin(ar,mid+1,right);
        }
        return s;
    }
    BtNode * CreateBinary(ElemType *ar,int n)
    {
        if(NULL == ar || n < 1)
            return NULL;
        else
            return CreateBin(ar,0,n-1);
    }

    方法二:给定二叉树的数组元素序列和大小创建二叉树
    BtNode * CreateTree(ElemType *&str)
    {
        BtNode *s = NULL;
        if(NULL != str && *str != END)
        {
            s = Buynode();
            s->data = *str;
            s->leftchild = CreateTree(++str);
            s->rightchild = CreateTree(++str);
        }
        return s;
    }

    方法三:客户端输入数组元素序列创建二叉树
    BtNode * CreateTree1()
    {
        BtNode *s = NULL;
        ElemType item;
        cin>>item;
        if(item != '#')
        {
            s = Buynode();
            s->data = item;
            s->leftchild = CreateTree1();
            s->rightchild = CreateTree1();
        }
        return s;
    }

    //根据前序遍历和中序遍历创建二叉树
    BtNode * CreatePI(ElemType *ps,ElemType *is,int n);
    BtNode * CreateTreePI(ElemType *ps,ElemType *is,int n)
    {
        if(NULL == ps || NULL == is || n < 1)
            return NULL;
        else
            return CreatePI(ps,is,n);
    }
    BtNode * CreatePI(ElemType *ps,ElemType *is,int n)
    {
        BtNode *s = NULL;
        if(n > 0)
        {
            s = Buynode();
            s->data = ps[0];
            int pos = FindPos(is,ps[0],n);
            if(pos == -1) exit(1);
            s->leftchild = CreatePI(ps+1,is,pos);
            s->rightchild = CreatePI(ps+pos+1,is+pos+1,n - pos - 1);
        }
        return s;
    }

    //根据中序遍历和后序遍历创建二叉树
    BtNode * CreateIL(ElemType *is,ElemType *ls,int n);
    BtNode * CreateTreeIL(ElemType *is,ElemType *ls,int n)
    {
        if(NULL == is || NULL == ls || n < 1)
            return NULL;
        else
            return CreateIL(is,ls,n);
    }
    BtNode * CreateIL(ElemType *is,ElemType *ls,int n)
    {
        BtNode *s = NULL;
        if(n > 0)
        {
            s = Buynode();
            s->data = ls[n-1];
            int pos = FindPos(is,ls[n-1],n);
            if(pos == -1) exit(1);
            s->leftchild = CreateIL(is,ls,pos);
            s->rightchild = CreateIL(is+pos+1,ls+pos,n-pos-1);
        }
        return s;
    }
    BtNode * CreateTreeIL(ElemType *is,ElemType *ls,int n)
    {
        if(NULL == is || NULL == ls || n < 1)
            return NULL;
        else
            return CreateIL(is,ls,n);
    }

    //根据前序遍历和后序遍历创建二叉树  (前序和后续不能唯一确定一种二叉树)
    BtNode * CreatePL(ElemType *ps,ElemType *ls,int pstat ,int pend ,int lstat ,int lend);
    BtNode * CreateTreePL(ElemType *ps,ElemType *ls,int n)
    {
        if(NULL == ps || NULL == ls || n < 1)
            return NULL;
        else
            return CreatePL(ps,ls,0,n-1,0,n-1);
    }
    BtNode * CreatePL(ElemType *ps,ElemType *ls,int pstat ,int pend ,int lstat ,int lend)
    {
        if(pstat>pend || lstat>lend)
                return NULL;
            BtNode *s = Buynode();

            s->data = ps[pstat];
            if(pstat +1 >pend)
            return s;
            int val = ps[pstat +1];
            int index = lstat;
            for(;index <pend && ls[index]!=val;index++);
            int length = index-lstat;
            s->leftchild = CreatePL(ps,ls,pstat+1,pstat+1+length ,lstat ,index);
            s->rightchild = CreatePL(ps,ls,pstat+length+2,pend ,index+1 ,lend-1);
            return s;}
     

    展开全文
  • 二叉树的创建&遍历1:创建二叉树 谈二叉树,如果二叉树都没有正确的创建出来,那岂不是纸上谈兵!! 创建方法1:由括号表达式创建 括号表达式: 表示方法: 1.括号:括号内的东西是括号前的元素的孩子 2.逗号:...

    二叉树的创建&遍历1:创建二叉树

    谈二叉树,如果二叉树都没有正确的创建出来,那岂不是纸上谈兵!!

    创建方法1:由括号表达式创建

    括号表达式:

    在这里插入图片描述

    表示方法:

    1.括号:括号内的东西是括号前的元素的孩子
    2.逗号:逗号是为了区分左右孩子

    算法分析:

    给出一个如上的括号表达式:A(B(D(,G)),(E,F)),再利用栈这个数据结构,分析一下:
    扫描整个括号表示的字符串,这个字符串中只有四种字符:'(',')',',','other'
    ①:如果遇到了’(’:表示前面刚刚创建的节点是有孩子节点的,需要把它压入栈中,因为我们的栈的功能实际上是为了保存父节点而便于去寻找孩子节点,然后开始创建孩子节点,第一个创建的一定是左孩子,所以设一个控制左右孩子的变量:k = 0;//k = 0 时是左孩子,k = 1 是右孩子
    ②:如果遇到了’)’:表示以栈顶元素为根节点的子树创建完毕,退出栈中
    ③:如果遇到了’,’:表示左孩子创建完毕,需要创建右孩子,此时k = 1//改变创建对象的状态
    ④:如果遇到了其他元素,也就是遇到了节点的内容,此时我们应该创建节点,并且根据当前需要创建的是左孩子还是右孩子,有选择有方向的去创建当前的节点并准确与其父节点链接

    核心代码展示:

    const int maxn = 1005;
    char str[maxn];
    struct BTNode{
    	char data;
    	BTNode* Lchild;
    	BTNode* Rchild;
    };
    
    BTNode* CreatBT(BTNode *&Root){
    	char ch;
    	int book = 0, j = 0, top = -1;
    	BTNode *pNode = Root = NULL, *Stack[maxn];
    	ch = str[j];
    	while('\0' != ch){
    		switch(ch){
    			case '(':
    				Stack[++top] = pNode;
    				book = 0;
    				break;
    			case ')':
    				--top;
    				break;
    			case ',':
    				book = 1;
    				break;
    			default:
    				pNode = new BTNode;
    				pNode->data = ch;
    				pNode->Lchild = pNode->Rchild = NULL;
    				if(NULL == Root)
    					Root = pNode;
    				else{
    					if(book)
    						Stack[top]->Rchild = pNode;
    					else
    						Stack[top]->Lchild = pNode;
    				}
    		}
    		ch = str[++j];
    	}
    	return Root;
    }
    

    代码分析:

    这里贯彻了一个思想:栈与队列在二叉树的操作中起到的作用就是保存根节点以便于查找子节点
    然后注意一下指针操作:一开始初始化的时候,一定要把所有未操作却已经定义了的指针指向NULL!

    创建方法二:层次创建二叉树

    之前括号表示法创建二叉树利用了栈的结构,这里我们要运用队列的结构

    问题引入:

    在这里插入图片描述
    上面这幅图,用层序遍历得到的结果是:5 4 8 11 # 13 4 7 2 # # # 1
    那如果我们得到上面这个序列,如何还原创建出二叉树呢?

    算法分析:

    给出一个层序结果,为空的地方是用‘#’表示,我们可以借助一个队列,来保存根节点,以便于链接它的对应子树,然后设置一个判定当前子树是左还是右的标记:book,如果book % 2 = 0则是左子树,反之则是右子树,算法步骤如下:
    ①:先让5入队,建立起第一层(根),然后把book设为0,表示接下来该创建左子树了
    ②:在队列不为空的情况下,取出队首元素,然后开始准备连上它的左右孩子,这时会有两种情况,一种是当前的book是奇数,这种情况是要添加左孩子,否则添加右孩子,然后在添加孩子的时候还需要判断这个孩子是否是存在的,如果是‘#’则是不存在,给当前的这个孩子赋予一个NULL,否则就连上这个孩子,并且把这个孩子push入队,因为它还可能是其他孩子的父亲!然后处理完左右孩子之后,我们才pop队首!

    核心代码展示:

    BTNode* CreatBT2(BTNode *&Root){
    	queue<BTNode* > q;
    	int book = 0;
    	Root->data = str2[book++];
    	Root->Lchild = Root->Rchild = NULL;
    	q.push(Root);
    	while(!q.empty()){
    		BTNode *temp = q.front();
    		if(book % 2){
    			if('#' == str2[book])
    				temp->Lchild = NULL;
    			else{
    				BTNode *p = new BTNode;
    				p->data = str2[book];
    				p->Lchild = p->Rchild = NULL;
    				temp->Lchild = p;
    				q.push(p);
    			}
    		}
    		else{
    			if('#' == str2[book])
    				temp->Rchild = NULL;
    			else{
    				BTNode *p = new BTNode;
    				p->data = str2[book];
    				p->Lchild = p->Rchild = NULL;
    				temp->Rchild = p;
    				q.push(p);
    			}
    			q.pop();
    		}
    		book++;
    	}
    	return Root;
    }
    

    创建方法三:根据某两序遍历唯一建树

    只能通过:
    ①:已知前序序列 + 已知中序序列 => 唯一建树
    ②:已知中序序列 + 已知后序序列 => 唯一建树
    然而,已知前序和后序是不能唯一建树的,这个随便举个例子就能得出,不做赘述

    算法分析:

    建树的过程如下:以已知前中序推导后序为例
    前序遍历的一个数是整棵树的根,然后在中序序列中找到根的对应位置,分治递归,找到每一个节点,建树

    核心代码展示:

    void CreatBT3(BTNode *&Root, int &pos, int l, int r){
    	int flag = -1;
    	for(int i = l;i <= r;i++){
    		if(in[i] == pre[pos])
    			break;// pos 就是当前子树的根 
    	}
    	if(-1 == flag)	return ;
    	Root = new BTNode;
    	Root->data = in[flag];
    	Root->Lchild = Root->Rchild = NULL;
    	pos++;
    	if(flag > l)
    		CreatBT3(Root->Lchild, pos, l, flag - 1);`
    	if(flag < r)
    		CreatBT3(Root->Rchild, pos, flag + 1, r);
    }
    
    展开全文
  • Python 实现二叉树的创建、添加、删除、修改、查找
  • C++二叉树的创建与遍历实验报告 作者: 日期 ? 二叉树的创建与遍历 一 实验目的 1.学会实现二叉树结点结构和对二叉树的基本操作 2.掌握对二叉树每种操作的具体实现学会利用递归和非递归方法编写对二叉树这种递归数据...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,882
精华内容 3,552
关键字:

二叉树的创建