精华内容
下载资源
问答
  • 二叉树相关的创建或者遍历
    2020-01-11 17:44:01

    一、通过先根遍历和中根遍历数组,构建还原二叉树

    思想:先根遍历数组,第一个元素就会是二叉树的根,然后找到根在中根遍历的位置,则中根遍历左边的就是左孩子,右边的就是右孩子。利用递归思想。

    public Node create(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){
        Node root = new Node(pre[preStart], null, null);
        // 递归结束条件
        if(preStart == preEnd && inStart==inEnd){
            return root;
        }
    
        // 找到根在中根遍历的位置,确定左孩子和右孩子
        int ft = 0;
        for(ft = inStart; ft < inEnd; ft++){
            if(in[ft] == pre[preStart]){
                break;
            }
        }
    
        // 确定左孩子数量
        int left = ft - inStart;
        int rigth = inEnd - ft;
        // 有左孩子,则递归建立左孩子
        if(left > 0 ){
            root.left = create(pre, in, preStart+1, preStart+left, inStart, ft -1);
        }
        
        if(right > 0){
            root.right = create(pre, in, preStart+left+1, preEnd, ft+1, inEnd);
        }
    }

    如果是后跟遍历和中根遍历,方法类似,主要是怎么确定好左孩子和右孩子的关系。

    public Node create(int[] post, int[] in, int postStart, int postEnd, int inStart, int inEnd){
        // 后跟遍历,最后一个节点是跟
        Node root = new Node(post[postEnd], null, null);
        if(postStart == postEnd && inStart == inEnd){
            return root;
        }
    
        // 找到中分点
        int ft = 0;
        for(ft = inStart; ft < inEnd; ft++){
            if(in[ft] == post[postEnd]){
                break;
            }
        }
    
        int left = ft - inStart;
        int right = inEnd - ft;
        if(left > 0){
            root.left = create(post, in, postStart, postStart+left-1, inStart, ft -1);
        }
    
        if(right > 0){
            root.right = create(post, in, postStart+left, postEnd-1, ft+1, inEnd);
        }
    }

     

    更多相关内容
  • } } 后序遍历 后续遍历【最后访问根节点】 后序遍历左子树 后序遍历右子树 再访问根节点 /** * 后跟遍历 * 先访问左子树,再访问右子树 * 最后访问根节点 */ public void postorder(TreeNode p){ if(p!=null){ ...

    度:子节点的个数、
    深度:从根节点到最底层节点的层数称之为深度,根节点在第一层
            一般树:
                任意一个节点的字节点的个数都不限制
            二叉树:
                任意一个子节点的个数最多两个,且节点的位置不可改变
                分类:
                    二叉排序树
                        若它的左子树不空,则左子树的所有关键字均小于根关键字的值
                        若它的右子树不空,则右子树的所有关键字均大于根关键字的值
                        没有键值相等的
                        
                    平均查找的长度与树得高度有关
                    尽可能的让树的高度越矮
                    平衡因子=左子树的高度-右子树的高度
                    若所有的平衡因子的绝对值不超过1,则为平衡二叉树
                    
                    查找前驱节点:小于当前节点的最大值
                    查找后继节点:大于当前节点的最小值

                    1、一般二叉树:
                    2、满二叉树:在不增加树的层数的前提下,无法再多添加一个节点的二叉树就是满二叉树
                    3、完全二叉树:只是删除满二叉树最底层最右边的连续若干个节点的,这样形成的二叉树就是完全二叉树
                    4、平衡二叉树:可以是一棵空树,若不是空树,左右两个子树的高度差不会超过1,并且两个子树都是一颗平衡二叉树
                        4.1、红黑树
                            平衡属性,任意节点左右子树的高度差不大于1
                            1、根节点是黑色,叶子节点是不存储数据的黑色空节点
                            2、任何相邻的两个节点不能同时为红色
                            3、任意节点到其可到达的叶子节点间包含相同数量的黑色节点
            
            树操作
                遍历
                先序遍历
                    先序遍历【先访问根节点】
                    先访问根节点
                    再先序访问左子树
                    再先序访问右子树

     递归版本的进行实现关于二叉树的先序遍历

        /**
         * 先根遍历,先访问根节点
         * 再访问左节点,后访问右节点
         */
        public void preorder(TreeNode p){
            if(p!=null){
                System.out.println(p.val+" ");
                preorder(p.left);
                preorder(p.right);
            }
        }

    非递归实现的代码如下:

                中序遍历
                    中序遍历【中间访问根节点】
                    中序遍历左子树
                    再访问根节点
                    再中序访问右子树

        /**
         * 中根遍历
         * 先访问左子树,再访问根节点,最后访问右子树
         */
        public void inorder(TreeNode p){
            if(p!=null){
                inorder(p.left);
                System.out.println(p.val+" ");
                inorder(p.right);
            }
        }
    


                后序遍历
                    后续遍历【最后访问根节点】
                    后序遍历左子树
                    后序遍历右子树
                    再访问根节点

        /**
         * 后跟遍历
         * 先访问左子树,再访问右子树
         * 最后访问根节点
         */
        public void postorder(TreeNode p){
            if(p!=null){
                postorder(p.left);
                postorder(p.right);
                System.out.println(p.val+" ");
            }
        }


            记住操作:只有通过先序和中序或者是通过中序和后序,才能够确定一个唯一的二叉树
            

     树的应用
        树是操作数据库中的数据组织一种重要的形式
        操纵系统子父进程的关系就是一棵树
        面向对象的继承关系就是一棵树
        哈弗曼树
     

    展开全文
  • 1,先根遍历-递归 由于先根次序遍历规则是递归,采用递归算法实现的递归方法必须有参数,通过不同的实际参数区别递归调用执行中的多个方法。而二叉树类必须提供从根节点开始遍历的成员方法,因此,每种递归的遍历...

    1,先根遍历-递归

    由于先根次序遍历规则是递归,采用递归算法实现的递归方法必须有参数,通过不同的实际参数区别递归调用执行中的多个方法。而二叉树类必须提供从根节点开始遍历的成员方法,因此,每种递归的遍历算法由两个重载的成员方法实现。

    【思路先根遍历,即第一次遇到的结点就开始打印。一直遍历左子树,直到为空,然后开始递归右子树,直到为空。

    【过程】先将1进入方法,2,3执行方法,2先执行,在2中将4,5执行方法,直到发现4无子树,然后轮到5执行方法。直到发现5没有子树,此时2方法结束,轮到3执行方法。

    public void preorder(){        //输出先根次序遍历序列
        preorder(this.root);       //调用先根次序遍历二叉树的递归方法
        System.out.println();
    }    
    private void preorder(BinaryNode<T> p){     //先根次序遍历以p结点为根的子树,递归方法
        if (p!=null){                                      //若二叉树不空
            System.out.print(p.data.toString()+" ");       //先访问当前结点元素
            preorder(p.left);      //按先根次序遍历p的左子树,递归调用,参数为左孩子
            preorder(p.right);     //按先根次序遍历p的右子树,递归调用,参数为右孩子
        }
    }

    2,先根遍历-非递归

    【思路】还是先根遍历,遇到结点就压入栈中,每当发现某个结点无子树,将结点设置为从栈中弹出元素。如果不为空就打印。

    【过程】先将1压入栈中,然后让结点=1.left,1的左子树=2,发现2不为空压入栈中,继续。。。当发现4无子树时,从栈中弹出2,使得p=2,right=5,此时栈中只有1,等发现5没有子树时,p弹栈=1。

    public void preorderTraverse() {
        LinkedStack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>();
    	BinaryNode<T> p = this.root;
    	while (p != null || !stack.isEmpty()) {
    	    if (p != null) {
    		    System.out.print(p.data + " "); // 先根遍历
    			stack.push(p);
    			p = p.left;
    		} else {
    			System.out.print("^ ");
    			p = stack.pop();
    			p = p.right;
    		}
    	}
    }​​

    3,中根遍历-递归

    【思路】开始从跟结点遍历,当第二次遍历到该结点时打印。如何区分是第二次了,在递归中只需要在左右子树中间打印即可。因为但遍历完左子树时,回到父母结点时为第二次遍历到父母结点,第一次为通过父母接到遍历到孩子结点时。

    【过程】从1开始进入遍历方法,发现1不为空,将2,3进入遍历方法。由于2先开始,此时3一直在等待2的结束。2发现4.5不是空,将4,5进入遍历方法,此时没有打印2.当4结束时在通过2进入5之前打印此时结点,即为中根遍历。

    public void inorder(){         //输出中根次序遍历序列
        inorder(this.root);
        System.out.println();
    }    
    private void inorder(BinaryNode<T> p){    //中根次序遍历以p结点为根的子树,递归方法
        if (p!=null){
            inorder(p.left);                  //中根次序遍历p的左子树,递归调用
            System.out.print(p.data.toString()+" ");
            inorder(p.right);             //中根次序遍历p的右子树,递归调用
        }
    }

    4,中根遍历-非递归

    【思路】参考先根遍历中的非递归方法。先根遍历是在第一次遇到非空的时候打印。中根稍有区别,在第一次非空时入栈,不打印,当发现子树为空时,弹栈时回到空子树的父母结点时,打印,此时为第二次访问,即中根遍历。

    【过程】1开始进入while循环,发现1.left=2不为空入栈,此时不要打印,然后4,进入循环,入栈,发现4左子树为空,此时弹栈,弹出4,立即打印,达到中根遍历。其余相似。

    public void inorderTraverse() {
        LinkedStack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>();
    	BinaryNode<T> p = this.root;
    	BinaryNode<T> q1 = null;
    	BinaryNode<T> q2;
    	boolean flag = true;
    	while (p != null || !stack.isEmpty()) {
    	    if (p != null) {
    		    stack.push(p);
    			p = p.left;
    		} else {
    			System.out.print("^ ");
    			p = stack.pop();
    			System.out.print(p.data + " "); // 中跟遍历
    			p = p.right;
    		}
    
    	}
    }

    5,后根遍历-递归

    【思路】现遍历子树,等左右子树都遍历完后,在打印结点。跟之前的类比一下很容易想到。

    【过程】1进入递归,发现2,3非空,然后2进入递归,3等待,2又发现4,5非空,此时4进入递归,5等待,然后4发现左右子树都为空,此时不再进行递归,打印4结点的值。

    public void postorder(){      //输出后根次序遍历序列
        postorder(this.root);
        System.out.println();
    }
    private void postorder(BinaryNode<T> p){        //后根次序遍历以p结点为根的子树,递归方法
        if (p!=null){
            postorder(p.left);
            postorder(p.right);
            System.out.print(p.data.toString()+" ");      //后访问当前结点元素
        }
    }

    6,后根遍历-非递归

    【思路】由于需要确定当前结点被访问过两次,此时需要额外一个结点来储存之前访问的结点。符合打印条件的就一共两种情况,一是无子结点,直接打印。二是当前访问的结点其右子树已被访问,或者右子树不存子,左子树被访问过。

    一定要注意,先将右子树入栈,再将左子树入栈,因为访问时是现访问左子树,在访问右子树。

    public void postorderTraverse() {
        LinkedStack<BinaryNode> stack = new LinkedStack<BinaryNode>();
    	BinaryNode cur, pre = null;       //pre为额外结点,记录前一个结点,用于打印
    	stack.push(this.root);
    	while (!stack.isEmpty()) {
    	    cur = stack.peek();
    		if ((cur.left == null && cur.right == null) || (pre != null && (cur.left == pre || cur.right == pre))) {            //判断是否为上述条件决定是否打印
    		    BinaryNode temp = stack.pop();
    			System.out.print(temp.data + " ");
    			pre = temp;
    		} else {
    			if (cur.right != null) {        //右结点入栈
    			    stack.push(cur.right);
    			}
    			if (cur.left != null) {
    				stack.push(cur.left);
    			}
    		}
    	}
    }

     

    展开全文
  • 二叉树 先根遍历 中跟遍历 后跟遍历 结构体: struct Node{ int val; Node *LC; Node *RC; Node(int k){ this->val=k; LC=NULL; RC=NULL; } }; 函数: void preOrder(Node *root){//先根遍历就是DFS...

    二叉树 先根遍历 中跟遍历 后跟遍历

    结构体:

    struct Node{
    	int val;
    	Node *LC;
    	Node *RC;
    	Node(int k){
    		this->val=k;
    		LC=NULL;
    		RC=NULL;
    	}
    };
    

    函数:

    void preOrder(Node *root){//先根遍历就是DFS呀 递归实现 
    	if(root==NULL){
    		return;
    	}
    	cout<<root->val<<" ";
    	preOrder(root->LC);
    	preOrder(root->RC); 
    }
    void inOrder(Node *root){
    	if(root==NULL){
    		return;
    	}
    	inOrder(root->LC);
    	cout<<root->val<<" ";
    	inOrder(root->RC);
    }
    void postOrder(Node *root){
    	if(root==NULL){
    		return;
    	}
    	postOrder(root->LC);
    	postOrder(root->RC);
    	cout<<root->val<<" ";
    } 
    //迭代实现     先访问,然后去左节点,最后右节点 stack起到了保存的作用。 
    void ppreOrder(Node *root){
    	stack<Node*> s;
        Node *p=root;
        while(p!=NULL||!s.empty())
        {
            while(p!=NULL)
            {
                cout<<p->val<<" ";
                s.push(p);
                p=p->LC;
            }
            if(!s.empty())
            {
                p=s.top();
                s.pop();
                p=p->RC;
            }
        }
    }
    void iinOrder(Node *root){
    	stack<Node *> s;
    	Node *p=root;
    	while(p!=NULL||!s.empty()){
    		while(p!=NULL){
    			s.push(p);
    			p=p->LC;
    		} 
    		if(!s.empty()){
    			p=s.top();
    			cout<<p->val<<" ";
    			s.pop();
    			p=p->RC;
    		}
    	}
    } 
    void ppostOrder(Node *root){  // 后序非递归遍历二叉树的顺序是先访问左子树,再访问右子树,最后访问根节点。当用堆栈来存储节点,必须分清返回根节点时,是从左子树返回的,还从右子树返回的。所以,使用辅助指针r,其指向最近访问过的节点。也可以在节点中增加一个标志域,记录是否已被访问
    	 Node *p = root, *r = NULL;
        stack<Node*> s;
        while (p!=NULL || !s.empty()) {
            if (p!=NULL) {//走到最左边
                s.push(p);
                p = p->LC;
            }
            else {
                p = s.top();
                if (p->RC!=NULL && p->RC != r)//右子树存在,未被访问
                    p = p->RC;
                else {
                    s.pop();
                    cout<<(p->val)<<" ";
                    r = p;//记录最近访问过的节点
                    p = NULL;//节点访问完后,重置p指针
                }
            }//else
        }//while
    }
    

    要写头文件 include<stack>
    Main函数:

    int main(){
    	Node *p=new Node(5);
    	Node *q=new Node(2);
    	Node *l=new Node(6);
    	Node *k=new Node(3);
    	q->RC=k; 
    	p->LC=q;
    	p->RC=l;
    	preOrder(p);
    	cout<<endl;
    	inOrder(p);
    	cout<<endl;
    	postOrder(p);
    	cout<<endl;	
    	ppreOrder(p);
    	cout<<endl;
    	iinOrder(p); 
    	cout<<endl;
    	ppostOrder(p);
    }
    

    结果输出:
    在这里插入图片描述
    先跟遍历和BFS一样,DFS利用queue来实现。
    参考博客:二叉树前序(先序)中序后序遍历 C++递归和非递归实现

    展开全文
  • 主要指非空二叉树,对于空二叉树则结束返回,二叉树的遍历主要包括先序遍历、中序遍历、后序遍历(也称为先跟、中跟、后跟遍历) 先序遍历 首先访问根结点,然后遍历左子树,最后遍历右子树(根->左->右) 顺序:...
  • 先访问根节点后访问左右子树的遍历方式是前序遍历,先访问左右子树最后访问根节点的遍历方式是后序遍历,先访问左子树再访问根节点最后访问右子树的遍历方式是中序遍历,下面详细说明: 前序遍历 遍历顺序是根节点-...
  • L、D、R分别表示遍历左子树、访问根节点及遍历右子树 前序遍历【DLR】:前序遍历也叫先根遍历,先访问根节点然后遍历左子树,最后遍历右子树; // 示例代码 中序遍历【LDR】:中序遍历也叫中根遍历,先遍历左子树...
  • 数据结构与算法之二叉树的遍历 原文来自个人博客(求访问/关注/收藏): https://bbing.com.cn/ CSDN个人博客不定期转载 遍历二叉树的作用 基于二叉树的结构, 衍生出了二叉查找树/平衡二叉查找树/堆等等结构或算法...
  • 二叉树的先中后序遍历实现-递归方式 一、理论讲解 以这棵树二叉树作为例子讲解: 先序遍历 根左右: A B C D E F G H 中序遍历 左根右: C B D A F H E G 后序遍历 左右根: C D B H F G E A 二、代码...
  • 一、前序遍历 根节点-&gt;左子树-&gt;右子树 二、中序遍历 左子树-&gt;根节点-&gt;右子树 三、后序遍历 左子树-&gt;右子树-&gt;根节点 四、层次遍历 按照深度,以从上到下、从左到右的顺序...
  • 前序遍历(DLR),是二叉树遍历的一种,也叫做先跟遍历,先序遍历,前序周游,可记做根左右。前序遍历首先访问根节点然后遍历左子树,最后遍历右子树。 前序遍历首先访问根节点然后遍历左子树,最后遍历右子树。...
  • 二叉树的后序遍历 (牛客网—牛客题霸算法篇—NC192) 题目描述 给定一个二叉树,返回他的后序遍历的序列。 后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。 代码实现 import java.util.*; /* public...
  • 树与二叉树复习一、填空1、由二叉树的(中)序和(前、后)序遍历序列可以唯一确定一棵二叉树。2、任意一棵二叉树,若度为0的结点个数为n0,度为2的结点个数为n2,则n0等于(n0=n2+1 )。3、一棵二叉树的第i(i≥1)层最多有...
  • Python代码实现二叉树 ...大概的思路是用两个类来...把对二叉树的三种遍历方式放到了结点类种。 以下是实现代码: class Node: def __init__(self,id,name): #假设节点中存储的是id, name, 左子节点, 右子节点四个信息
  • 前序中序后序遍历的顺序

    千次阅读 2019-09-22 21:04:36
    这三个我懂,但是给出一棵树,写他们的三序遍历,我就有点蒙了; 给出图之后,我们先画出遍历路径, 此时前序遍历就是遇到结节就访问,中序是从左子树返回时遇到节点就访问,后序是从右子树返回时遇到节点就访问。...
  • B的右子树也按照先序遍历的原则,顺序是D->F ,就可以得到A->B->D->F->C ③:右子树C按照先序遍历的原则处理,顺序是C->E,同理C的子树得遍历顺序E->G->H->I 那么, 这棵树先序遍历的结果就是,A->B->D->F->C->E->G->H...
  • //然后再遍历左子树 只有到达二叉树的左叶子 才会终止循环 } //此刻若栈不为空 那么栈顶必定是 根节点 if(!stack.isEmpty()) { current = stack.pop();//输出当前的栈顶 也就是 左叶子节点 System....
  • 对于二叉树的遍历,分为深度优先遍历与广度优先遍历,广度优先遍历有时又称作层序遍历。而深度优先遍历又分为前序遍历,中序遍历和后序遍历。三者之间的区别主要在于根结点的遍历顺序。前序遍历的顺序是根结点-&...
  • 二叉树的前序中序后序遍历图示
  • } 创建的二叉树如下图所示 先根遍历:先根遍历就是先遍历根节点,然后遍历左子树,再然后右子树 即输出8->4->2->1->3->6->7->12->10->9->11->14->13->15 public void firstRoot() { System.out.print(data + " ");...
  • 关于先序遍历、中序遍历、后序遍历的定义可以参考这篇博客二叉树的遍历规则。 目前能够百度到的问题大多都是根据(先序&amp;amp;中序)或(中序&amp;amp;后序)序列构建唯一二叉树,其中贴出一些提供思路的...
  • 图解二叉树先根、中根、后根遍历

    千次阅读 2020-09-02 09:23:17
    原理:先遍历根节点,再遍历左子树,最后遍历右子树; 中根遍历 结果:CBEDFAGH 原理:先遍历左子树,再遍历根节点,最后遍历右子树; 后根遍历 结果:CEFDBHGA 原理:遍历左子树,再遍历右子树,最后遍历根节点; ...
  • #include #include #include #include char s1[1000],s2[1000],s3[1000],s4[1000];... //printf("二叉树的中序序列和层次遍历序列相同\n"); return 0; } 转载于:https://www.cnblogs.com/-xss/p/6011924.html
  • 二叉树的后序遍历-递归和非递归算法

    万次阅读 多人点赞 2018-11-16 15:14:49
    后序递归遍历算法 void PostOrder(BiTree bt){ if(bt){ PostOrder(bt-&gt;lchild); PostOrder(bt-&gt;rchild); cout&lt;&lt;bt-&gt;data&lt;&lt;" "; } } 后序非...
  • 然后输入一个字符,输出该字符在先、中、后序遍历中的访问次序(访问次序从1开始)以及先、中、后序遍历结果。若输入的字符不在二叉树中,输出相应提示信息。要求程序可以反复输入字符并输出访问次序及遍历结果,...
  • 二叉树中的前序遍历是先访问根结点,再访问左子树,右子树。 中序遍历是先访问左子树,再是根结点,最后是右子树。 后序遍历是先访问左子树,再是右子树,最后是根结点。 算法思路是先根据前序遍历的第一个结点...
  • 以中根和后根遍历序列构造二叉树,替换所有与pattern匹配的子树为bitree。 public class BinaryTree { public BinaryNoderoot; public BinaryTree() { this.root = null; } public boolean isEmpty() //判断是否...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,142
精华内容 4,456
关键字:

后跟遍历