精华内容
下载资源
问答
  • 1.二叉树是一种非线性结构,遍历二叉树几乎都是通过递归或用栈辅助实现非递归的遍历,用二叉树作为存储结构时,取到一个节点,只能获取节点的左孩子和右孩子,不能直接得到节点的任一遍历序列的前驱和后继。...

    1.二叉树是一种非线性结构,遍历二叉树几乎都是通过递归或用栈辅助实现非递归的遍历,用二叉树作为存储结构时,取到一个节点,只能获取节点的左孩子和右孩子,不能直接得到节点的任一遍历序列的前驱和后继。

    2.为了保存这种在遍历中需要的信息,我们利用二叉树中指向左右子树的空指针来存放节点的前驱后继信息。

       创建节点:

    enum PointerTag
    {
    	THREAD,
    	LINK,
    };
    template<class T>
    struct BinaryTreeThdNode
    {
    	T _data;                       //数据
    	BinaryTreeThdNode<T>* _letf;   //左孩子
    	BinaryTreeThdNode<T>* _right;  //右孩子
    	PointerTag _letfTag;           //左孩子线索标志
    	PointerTag _rightTag;          //右孩子线索标志
    	BinaryTreeThdNode(const T& data)
    		:_data(data)
    		,_letf(NULL)
    		,_right(NULL)
    	{}
    };

    线索化过程和遍历:

    template<class T>
    class BinaryTreeThd
    {
    	typedef BinaryTreeThdNode<T> Node;
    public:
    	typedef BinaryTreeThdIterator<T,T&,T*> Iterator;
    	BinaryTreeThd();
    	BinaryTreeThd(const T* a,size_t size,const T& invalid)
    		:_root(NULL)
    	{
    		size_t index=0;
    		_root=_GreateTree(a,size,index,invalid);
    	}
    	void InorderThd()   //中序线索化
    	{
    		Node* prev=NULL;
    		_InoderThd(_root,prev);
    	}
    	void prevorderThd()    //前序线索化
    	{
    		Node* prev=NULL;
    		_prevorderThd(_root,prev);
    	}
    	void PostOrderThd()    //后序线索化
    	{
    		Node* prev=NULL;
    		_PostOrderThd(_root,prev);
    	}
    	void prevorder()       //线索化后前序遍历
    	{
    		_prevorder(_root);
    		cout<<endl;
    	}
    	void Inorder()    //线索化后中序遍历
    	{
    		_Inorder(_root);
    		cout<<endl;
    	}
    	void Postorder()   //线索化后后序遍历
    	{
    		Node* cur=_root;
    		Node* prev=NULL;
    		while(cur)
    		{
    			//找最左边节点
    			while(cur&&cur->_letfTag ==LINK)
    			{
    				cur=cur->_letf ;
    			}
    			//访问后继
    			while(cur&&cur->_rightTag ==THREAD)
    			{
    				cout<<cur->_data <<" ";
    				prev=cur;
    			}
    			
    			cur=cur->_right ;
    		}
    	 }
        
    protected:
        void _PostOrderThd(Node* root,Node*& prev)
    	{
    		if(root==NULL)
    			return;
    		_PostOrderThd(root->_letf ,prev);
    		_PostOrderThd(root->_right ,prev);
    
    		if(root->_letf ==NULL)
    		{
    			root->_letfTag =THREAD;
    			root->_letf =prev;
    		}
    		if(prev&&prev->_right ==NULL)
    		{
    			prev->_rightTag =THREAD;
    			prev->_right =root;
    		}
    		prev=root;
    	}
    
    	void _prevorder(Node* root)
    	{
    		while(root)
    		{
    			while(root&&root->_letfTag ==LINK)
    			{
    				cout<<root->_data <<" ";
    				root=root->_letf ;
    			}
    			cout<<root->_data <<" ";
    			root=root->_right ;
    		}
    	}
        void _prevorderThd(Node* root,Node* &prev)
    	{
    		if(root==NULL)
    			return;
    
    		if(root->_letf ==NULL)
    		{
    			root->_letfTag =THREAD;
    			root->_letf =prev;
    		}
    		
    		if(prev&&(prev->_right ==NULL))
    		{
    			prev->_rightTag =THREAD;
    			prev->_right =root;
    		}
    
    		prev=root;
    		if(root->_letfTag ==LINK)
    	 		_prevorderThd(root->_letf ,prev);
    	
    		if(root->_rightTag ==LINK)
    			_prevorderThd(root->_right ,prev);
    	}
    	
    	void _Inorder(Node* root)
    	{
    	     while(root)
    		 {
    			 //找左节点
    			 while(root&&root->_letfTag==LINK)
    			 {
    				 root=root->_letf ;
    			 }
    			 cout<<root->_data <<" ";
    			 //
    			 while(root->_rightTag ==THREAD&&root->_right )
    			 {
    				 root=root->_right ;
    				 cout<<root->_data <<" ";
    			 }
    			 root=root->_right ;
    		 }
    	}
    	void _InoderThd(Node* root,Node* &prev)
    	{
    		if(root==NULL)
    			return;
    		_InoderThd(root->_letf ,prev);      //zuo
    
    		if(root->_letf ==NULL)
    		{
    			root->_letfTag =THREAD;
    			root->_letf =prev;
    		}
    		if(root->_right ==NULL)
    			root->_rightTag =THREAD;
    		if(prev&&prev->_rightTag ==THREAD)
    			prev->_right =root;
    
    		prev=root;
    
    		_InoderThd(root->_right ,prev);      //you
    	}
    	Node* _GreateTree(const T *a,size_t size,size_t& index,const T& invalid)
    	{
    		Node* root=NULL;
    		if(a[index]!=invalid&&index<size)
    		{
    			root=new Node(a[index]);
    			root->_letfTag =LINK;
    			root->_rightTag =LINK;
    			root->_letf =_GreateTree(a,size,++index,invalid);
    			root->_right =_GreateTree(a,size,++index,invalid);
    		}
    		return root;
    	}
    private:
    	Node* _root;
    };
    void TestBinaryTreeThd()
    {
    	int a[10]={1,2,3,'#','#',4,'#','#',5,6};
    	BinaryTreeThd<int> t(a,10,'#');
    	t.InorderThd ();
    	t.Inorder ();
    	//t.prevorderThd ();
    	//t.prevorder ();
    	//t.PostOrderThd ();
    }



    展开全文
  • //先序遍历创建线索二叉树 (递归) void make_preorder_tree(BiThrNode *ptr) { BiThrNode *pre = NULL ; PreOrder_Tree(ptr,pre); } void PreOrder_Tree(BiThrNode *ptr,BiThrNode *pre) { if (ptr != NULL) ...
    //先序遍历创建线索二叉树 (递归)
    
    void make_preorder_tree(BiThrNode *ptr)
    {
    	BiThrNode *pre = NULL ;
    	PreOrder_Tree(ptr,pre);
    }
    void PreOrder_Tree(BiThrNode *ptr,BiThrNode *pre)  
    {  
    	if (ptr != NULL)  
    	{ 
    	if (ptr->leftchild == NULL)  
    	{  
    		ptr->leftchild = pre;     
    		ptr->leftchild = THREAD;  
    	}  
    	if (pre != NULL && pre->rightchild == NULL) 
    	{   
    		pre->rightchild = ptr;  
    		pre->Rtag = THREAD;
    	}  
    	pre = ptr;  
     
    	if (ptr->Ltag == LINK)  
    		PreOrder_Tree(ptr->leftchild,pre);  
    	if (ptr->Rtag == LINK)  
    		PreOrder_Tree(ptr->rightchild,pre); 
    	}
    }  
    
    //后序遍历创建线索二叉树 (递归)
    void Postorder_Tree(BiThrNode *ptr,BiThrNode *pre)  
    {  
    	if (ptr != NULL)  
    	{  
    		Postorder_Tree(ptr->leftchild);  
    		Postorder_Tree(ptr->rightchild);  
    		if (ptr->leftchild == NULL)  
    		{  
    			ptr->leftchild = pre;  
    			ptr->Ltag = THREAD;  
    		}  
    		if (pre!= NULL && pre->rightchild == NULL )  
    		{  
    			pre->rightchild = ptr;  
    			pre->Rtag = THREAD;  
    		}  
    		pre = ptr;  
    	}  
    }  

    展开全文
  • 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树: 3 / \ 9 20 / ...

    根据一棵树的中序遍历与后序遍历构造二叉树。

    注意:
    你可以假设树中没有重复的元素。

    例如,给出

    中序遍历 inorder = [9,3,15,20,7]
    后序遍历 postorder = [9,15,7,20,3]

    返回如下的二叉树:

        3
       / \
      9  20
        /  \
       15   7

    //迭代法
    //逆中序:右根|左    中序:左根|右
    //逆后序:根右|左    先序:根左|右
    //所以,中后序和前中序构造二叉树就只有 遍历顺序 和 左右子树连接 相反即可
    class Solution {//中后序构造二叉树
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            if(inorder.empty())return nullptr;
            TreeNode* root = new TreeNode(postorder[postorder.size()-1]);//  
            TreeNode* cur = nullptr;    
            bool flag=false;
            stack<TreeNode*> s;
            s.push(root);       
            for (int postIndex = postorder.size()-2, inIndex = inorder.size()-1; postIndex >=0; --postIndex) {//逆后序         
                while (s.size() && s.top()->val == inorder[inIndex]) {//逆中序            
                    --inIndex;// 
                    cur=s.top();              
                    s.pop();
                    flag=true;
                }           
                TreeNode* temp = new TreeNode(postorder[postIndex]);          
                if(flag){
                    cur->left=temp;//               
                    flag=false;
                }              
                else
                    s.top()->right=temp;//
                s.push(temp);   
            }
    		return root;
        }
    };
    class Solution {//前中序构造二叉树
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& preorder) {
            if(inorder.empty())return nullptr;
            TreeNode* root = new TreeNode(preorder[0]);//
            TreeNode* cur = nullptr;    
            bool flag=false;
            stack<TreeNode*> s;
            s.push(root);       
            for (int preIndex = 1, inIndex = 0; preIndex < preorder.size(); ++preIndex) {//逆后序         
                while (s.size() && s.top()->val == inorder[inIndex]) {//逆中序            
                    ++inIndex;// 
                    cur=s.top();              
                    s.pop();
                    flag=true;
                }           
                TreeNode* temp = new TreeNode(preorder[preIndex]);          
                if(flag){
                    cur->right=temp;//               
                    flag=false;
                }              
                else
                    s.top()->left=temp;//
                s.push(temp);   
            }
    		return root;
        }
    };

    给定一个二叉树,原地将它展开为链表。

    例如,给定二叉树

        1
       / \
      2   5
     / \   \
    3   4   6

    将其展开为:

    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6

    class Solution {
    public://线索二叉树变形
        void flatten(TreeNode* root) {//morris线索二叉树变形,线索二叉树代码框架在下下面
            TreeNode *cur=root,*temp=nullptr;
            while(cur){
                temp=cur->left;
                if(temp){
                    while(temp->right)
                        temp=temp->right;
                    if(!temp->right){
                        temp->right=cur->right;//
                        cur->right=cur->left;//
                        cur->left=nullptr;//
                        cur=cur->right;//
                        continue;
                    }                    
                }
                cur=cur->right;
            }    
        }
        /*第一遍思路,做不出来
        TreeNode* helper(TreeNode* root){
            if(root->left&&root->right){
                TreeNode* temp=helper(root->left);
                temp->right=root->right;
                root->right=root->left;
                return helper(temp->right);
            }   
            else if(root->left){
                root->right=root->left;
                return helper(root->right);
            }
            else if(root->right)
                return helper(root->right);
            else
                return root;
        }*/
    };

    morris线索二叉树

    morris二叉树遍历:时间复杂度O(n),空间复杂度O(1)
    1)记忆口诀:循环当前,左右到底,右子有无,当前左右,后前前中
    后左尾头,右子反转,next开头,首尾相接,遍历反转
    2) morris遍历时,此时若还有线索未解锁则不能直接返回函数,否则报错
    3)前中后代码框架
        TreeNode *cur=root,*temp=nullptr;
        while(cur){
            temp=cur->left;
            if(temp){
                while(temp->right&&temp->right!=cur)
                    temp=temp->right;
                if(temp->right){
                    temp->right=nullptr;
                    //后序节点处理
                }
                else{
                    temp->right=cur;
                    //前序节点处理
                    cur=cur->left;
                    continue;
                }           
            }
            else
                //前序节点处理
            //中序节点处理
            cur=cur->right;
        }
    4)中序
    void InOrder(TreeNode* root){//morris中序(左,根,右)
        TreeNode *cur=root,*pre=nullptr,*temp=nullptr;
        while(cur){
            temp=cur->left;
            if(temp){
                while(temp->right&&temp->right!=cur)
                    temp=temp->right;
                if(temp->right)
                    temp->right=nullptr;
                else{
                    temp->right=cur;
                    cur=cur->left;
                    continue;
                }
            }
    		operate(cur),pre=cur;//如果需要用到前驱节点则需定义pre,否则不用
            cur=cur->right;
        }
    }
    5)前序
    void PreOrder(TreeNode* root){//morris前序(根,左,右)
        TreeNode *cur=root,*pre=nullptr,*temp=nullptr;
        while(cur){
            temp=cur->left;
            if(temp){
                while(temp->right&&temp->right!=cur)
                    temp=temp->right;
                if(temp->right)
                    temp->right=nullptr;
                else{
                    temp->right=cur;
                    operate(cur),pre=cur;//如果需要用到前驱节点则需定义pre,否则不用
                    cur=cur->left;
                    continue;
                }
            }
            else
    	   		operate(cur),pre=cur;//如果需要用到前驱节点则需定义pre,否则不用
            cur=cur->right;
        }
    }
    6)后序
    void PostOrder(TreeNode* root){//morris前序(左,右, 根)
        TreeNode *cur=root,*pre=nullptr,*temp=nullptr;
            while(cur){
                temp=cur->left;
                if(temp){
                    while(temp->right&&temp->right!=cur)
                        temp=temp->right;
                    if(temp->right){
                        temp->right=nullptr;
    					PostHelper(cur->left);
    				}
                    else{
                        temp->right=cur;
                        cur=cur->left;
                        continue;
                    }
                }     
                cur=cur->right;
            }
    		operate(head)
    }
    
    void PostHelper(TreeNode* root){
    	//1 链表(右)逆序,头节点为root
    	TreeNode *cur=root,*pre=nullptr,*next=nullptr;
    	while(cur){//next开头,首位相接,方便记忆,如下
    		next=cur->right;//next=cur->right=pre=cur=next
    		cur->right=pre;
    		pre=cur;
    		cur=next;
    	}
    	//2 右边界逆序遍历
    	cur=pre;//此时头节点为pre
    	while(cur){
    		operate(cur);
    		cur=cur->right;
    	}
    	//3 链表(右)逆序,头节点为pre
    	cur=pre,pre=nullptr,next=nullptr;
    	while(cur){
    		next=cur->right;
    		cur->right=pre;
    		pre=cur;
    		cur=next;
    	}
    }

    递归/迭代+后序+pre节点

    class Solution {
    public:
        TreeNode* pre=nullptr;
        void flatten(TreeNode* root) {
            //递归/迭代+变形后序(右,左,根)+ pre节点
            if(!root)return;
            flatten(root->right);
            flatten(root->left);
            root->right=pre;
            root->left=nullptr;
            pre=root;
        }
    }

    总结(遇到二叉树问题):

    1考虑前中后序遍历

    2考虑前中后序遍历+pre前驱节点

    3考虑前中后 逆序遍历(+pre),比如逆前序:根左右->右左根

    4考虑前中后 变序遍历(+pre),比如变前序:根左右->根右左

    5考虑递归<迭代(时间空间都O(n))<morris(空间O(1),但不在遍历中途必须线索都解锁了才能返回,否则必须遍历到结束才能返回)

    给定一个非空二叉树,返回其最大路径和。

    本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

    示例 1:

    输入: [1,2,3]

           1
          / \
         2   3

    输出: 6


    示例 2:

    输入: [-10,9,20,null,null,15,7]

       -10
       / \
      9  20
        /  \
       15   7

    输出: 42

    class Solution {
    public:
        long long path=INT_MIN,curmaxpath=LLONG_MIN;
        int maxPathSum(TreeNode* root) {
            helper(root);       
            return curmaxpath;
        }
        int helper(TreeNode* root){
            if(!root)return 0;  
            int l=max(helper(root->left),0);//l=helper(root->left) 易错!!!
            int r=max(helper(root->right),0);//    
            path=root->val+l+r;
            curmaxpath=max(path,curmaxpath);        
            return max(l,r)+root->val;
        }
    };

     

    展开全文
  • 线索二叉树以及遍历线索化二叉树 1.线索二叉树基本介绍 n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域,存放指向该结点在某种遍历次序下的前驱和后继结点的指针...

    线索化二叉树以及遍历线索化二叉树

    1.线索二叉树基本介绍

    1. n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域,存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")
    2. 这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
    3. 一个结点的前一个结点,称为前驱结点
    4. 一个结点的后一个结点,称为后继结点

    2.中序线索二叉树

    将下面的二叉树,进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0FvUJ39Q-1594216798856)(en-resource://database/847:0)]
    说明: 当线索化二叉树后,Node节点的 属性 left 和 right ,有如下情况:

    1. left 指向的是左子树,也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点.
    2. right指向的是右子树,也可能是指向后继节点,比如 ① 节点right 指向的是右子树,而⑩ 节点的right 指向的是后继节点.

    线索化二叉树代码看下面

    3.因为线索化后,各个结点指向有变化,因此原来的遍历方式不能使用,这时需要使用新的方式遍历线索化二叉树,各个节点可以通过线型方式遍历,因此无需使用递归方式,这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致。

    package threadebinarytree;
    
    public class ThreadedBinaryTreeDemo {
        public static void main(String[] args) {
        //测试一把中序线索二叉树的功能
            HeroNode root = new HeroNode(1, "tom");
            HeroNode node2 = new HeroNode(3, "jack");
            HeroNode node3 = new HeroNode(6, "smith");
            HeroNode node4 = new HeroNode(8, "mary");
            HeroNode node5 = new HeroNode(10, "king");
            HeroNode node6 = new HeroNode(14, "dim");
    
            //二叉树,后面我们要递归创建, 现在简单处理使用手动创建
            root.setLeft(node2);
            root.setRight(node3);
            node2.setLeft(node4);
            node2.setRight(node5);
            node3.setLeft(node6);
    
            //测试中序线索化
            ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
            threadedBinaryTree.setRoot(root);
            threadedBinaryTree.threadedBinaryTree();
    
            //测试: 以10号节点测试
            HeroNode leftNode = node5.getLeft();
            HeroNode rightNode = node5.getRight();
            System.out.println("10号结点的前驱结点是 ="  + leftNode); //3
            System.out.println("10号结点的后继结点是="  + rightNode); //1
    
            System.out.println("使用线索化的方式遍历 线索化二叉树: ");
            threadedBinaryTree.threadedList(); // 8, 3, 10, 1, 14, 6
        }
    }
    
    
    //创建线索二叉树类 ThreadedBinaryTree
    class ThreadedBinaryTree{
        private HeroNode root; //父节点
    
        //为了实现线索化,需要创建指向当前结点的前驱结点的指针
        //在递归进行线索化时,pre始终指向前一个结点
        private HeroNode pre = null;
    
        public void setRoot(HeroNode root) {
            this.root = root;
        }
    
        public void threadedBinaryTree(){
            this.threadedBinaryTree(root);
        }
    
        //中序线索化二叉树
        public void threadedBinaryTree(HeroNode node){
            //如果根节点为null则直接返回
            if(node == null){
                return;
            }
    
            //1、线索化左子节点
            threadedBinaryTree(node.getLeft());
    
            //2、线索化当前结点(难点)
            //处理当前结点的前驱结点
            if(node.getLeft() == null){
                //让当前结点的左指针指向前去结点
                node.setLeft(pre);
                //修改当前结点的左指针的类型为1,表示左指针指向前驱结点
                node.setLeftType(1);
            }
    
            //处理当前结点的后继结点
            if(pre != null && pre.getRight() == null){
                //让前驱结点的右指针指向当前结点
                pre.setRight(node);
                //修改前驱结点的右指针类型
                pre.setRightType(1);
            }
            pre = node;
    
            //3、线索化右子结点
            threadedBinaryTree(node.getRight());
        }
    
        //遍历 中序线索化二叉树
        public void threadedList(){
            //定义一个变量,存储当前遍历的结点,从root开始
            HeroNode node = root;
            while (node != null){
                //循环找到leftType == 1 的结点,第一个找到的就是8
                //后面随着遍历而变化,因为当leftType == 1,说明该结点已经线索化过
                //处理后的有效结点
                while (node.getLeftType() == 0){
                    node = node.getLeft();
                }
    
                //打印当前结点
                System.out.println(node);
    
                //如果当前结点的有指针指向的是后继结点,则一直输出
                while (node.getRightType() == 1){
                    //获取到当前结点
                    node = node.getRight();
                    System.out.println(node);
                }
                //替换这个遍历的结点
                node = node.getRight();
            }
        }
    
        //前序遍历
        public void preOrder(){
            if(root != null){
                root.preOrder();
            }else {
                System.out.println(" 二叉树为空,无法遍历");
            }
        }
    
        //中序遍历
        public void infixOrder(){
            if(root != null){
                root.infixOrder();
            }else {
                System.out.println(" 二叉树为空,无法遍历");
            }
        }
    
        //后序遍历
        public void postOrder(){
            if(root != null){
                root.postOrder();
            }else {
                System.out.println(" 二叉树为空,无法遍历");
            }
        }
    
    }
    
    
    //创建结点类
    class HeroNode{
        private int no;
        private String name;
        private HeroNode left; //指向当前结点的左节点,默认为null
        private HeroNode right; //指向当前结点的右结点,默认为null
    
        //如果legtType == 0,表示指向的是左子树,如果leftType == 1则表示指向前驱结点
        //如果rightType == 0,表示指向的是右子树,如果rightType == 1则表示指向后继结点
        private int leftType;
        private int rightType;
    
        public HeroNode(int no, String name) {
            this.no = no;
            this.name = name;
        }
    
        public int getLeftType() {
            return leftType;
        }
    
        public void setLeftType(int leftType) {
            this.leftType = leftType;
        }
    
        public int getRightType() {
            return rightType;
        }
    
        public void setRightType(int rightType) {
            this.rightType = rightType;
        }
    
        public int getNo() {
            return no;
        }
    
        public void setNo(int no) {
            this.no = no;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public HeroNode getLeft() {
            return left;
        }
    
        public void setLeft(HeroNode left) {
            this.left = left;
        }
    
        public HeroNode getRight() {
            return right;
        }
    
        public void setRight(HeroNode right) {
            this.right = right;
        }
    
        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
    
        //前序遍历的递归实现
        public void preOrder(){
            //前输出父节点
            System.out.println(this);
            //递归向左子树前序遍历
            if(this.left != null){
                this.left.preOrder();
            }
            //递归向右子树前序遍历
            if(this.right != null){
                this.right.preOrder();
            }
        }
    
        //中序遍历的递归实现
        public void infixOrder(){
            //递归向左子树中序遍历
            if (this.left != null){
                this.left.infixOrder();
            }
            //输出父节点
            System.out.println(this);
            //递归向右子树中序遍历
            if(this.right != null){
                this.right.infixOrder();
            }
        }
    
        //后序遍历的递归实现
        public void postOrder(){
            //递归向左子树后序遍历
            if(this.left != null){
                this.left.postOrder();
            }
            //递归向右子树后续遍历
            if(this.right != null){
                this.right.postOrder();
            }
            //输出父节点
            System.out.println(this);
        }
    }
    
    • 结果
      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TxvmCHKH-1594216798859)(en-resource://database/849:0)]
    展开全文
  • 一:二叉树的集中遍历方法1:先序遍历根→左→右 先访问根节点,再遍历左子树,最后遍历右子树;并且在遍历左右子树时,仍需先访问根节点,然后遍历左子树,最后遍历右子树。 比如上图,先序遍历的输出如下 : - + ...
  • 文章目录节点信息前序线索化二叉树前序线索化二叉树遍历中序线索化二叉树中序线索化二叉树遍历后序线索化二叉树后序线索化二叉树遍历 节点信息 public class HeroNode { private int no; private String name; ...
  • 线索二叉树后序线索后序遍历输出 一.写码思路 我们要进行后序遍历,需要记录每个结点的 Parent 结点,我之前觉得可能不需要这个,直接用前驱就行了,但是后序遍历结点的前驱不一定是他的 Parent 结点。 ...
  • 文章目录二叉树1、概念1)二叉树2)满二叉树、完全二叉树3)前序遍历、中序遍历、后序遍历2、前中后序遍历代码实现3、顺序存储二叉树代码实现3、线索化二叉树 为什么要引入树? 数组存储方式:由于数组访问元素速度...
  • 遍历线索化二叉树

    2007-11-18 19:22:23
    构造二叉树 递归遍历二叉树(前序、中序、后序) 非递归遍历二叉树(前序、中序) 线索化二叉树(前序、中序) 遍历线索化二叉树(前序、中序) 线索化二叉树还原为非线索化二叉树(中序)
  • 2)这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)根据线索性质的不同,线索二又树可分为前序线索二叉树、中序线索二叉树后序线索二叉树三种 3)一个结点的前一个结点,...
  • C语言 Dev C++ 1 实验题目 通过添加虚结点,为二叉树的每一实结点补足其孩子,再对补足虚结点后的...3)完成后序线索化树上的遍历算法,依次输出该二叉树先序遍历、中序遍历和后序遍历结果。 3 输入输出样例 ...
  • 二叉树遍历的递归和迭代实现前序遍历概念 + 举例习题递归实现迭代实现写法1:只有右孩子入栈 前序遍历 概念 + 举例 前序遍历:对于当前节点,先输出该节点,然后输出他的左孩子,最后输出他的右孩子。 例如: 前序...
  • 目的:设计并实现基于后序线索二叉树后序遍历的非递归算法。 要求: (1)创建二叉树。 (2)转换为后序线索二叉树。 (3)实现后序遍历的非递归算法。 (4)其它要求同课后作业-01要求。 二、实验环境 软件环境:...
  • 二叉树顺序存储基本思路: 二叉树顺序存储代码: ...树.顺序存储二叉树; public class ArrBinaryTreeDemo { public static void main(String[] args)... System.out.println("顺序存储二叉树前序遍历:"); ArrBinaryTre
  • 图解 代码实现 ... /** * @创建人 wdl * @创建时间 2021/3/25 * @描述 ...public class ThreadedBinaryTreeDemo { public static void ... //测试一把中序线索化二叉树的功能 HeroNode root = new HeroNode(1, "tom")
  • 线索二叉树: 当某个节点的左孩子为空时,将_pLeft指针指向他的前一个节点;...后序遍历线索化二叉树 线索二叉树与普通二叉树有什么区别呢?线索二叉树中空的指针域至多2个,至少1个; 普通二叉树中空的指
  • 分析:因为线索后,各个结点指向有变化,因此原来的遍历方式不能使用,这时需要使用新的方式遍历线索化二叉树,各个节点可以通过线型方式遍历,因此无需使用递归方式,这样也提高了遍历的效率。 遍历的次序应当和...
  • [问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
  • 一、线索化二叉树的相关原理: 1.线索化二叉树的原理 对于二叉树来说,一个包含n个节点的二叉树的叶子节点会包含(2n - (n - 1) = n + 1)个空指针是指向null的,即指针资源被浪费。为了实现指针的有效利用,将未...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,057
精华内容 2,022
关键字:

后序遍历线索化二叉树