精华内容
下载资源
问答
  • 只移动树的左右指针将二叉树转换成双向链表,链表遍历和二叉树中序遍历一致。过程不能创建新的对象。 思路: 将一棵树的都抽象为父节点,节点,右节点。中序遍历的遍历顺序是 中右。所以: 1. 从根节点开始先...

    题目要求:

    只移动树的左右指针将二叉树转换成双向链表,链表遍历和二叉树中序遍历一致。过程不能创建新的对象。

    思路:

    将一棵树的都抽象为父节点,左节点,右节点。中序遍历的遍历顺序是 左中右。所以:

    1. 从根节点开始先检索左子树,一直检索到某个节点A的子节点是叶子节点(C、D)。对A的左以下操作:

    • 将C的右节点指向其父节点A
    • 将D的左指针指向A

    2. 将CAD作为一个整体即一个节点1,节点1的右指针是D 的右指针。节点1的做指针就是C的做指针。

    同时将原来A 的兄弟节点做以上同样的操作得到节点2(acd)。同样将1、2和他们的父节点k做以上的两个步骤。

    以下是代码实现:

    假设二叉树对象是:

    public class TestObject {
        private int data;
        private TestObject left;
        private TestObject right;
    }

    实现是: 

      /**
         * 二叉树变为双向链表
         * @param last 双向链表的最后一个元素,初始为null;
         * @param tree 当前解析的左中右  的中节点 初始为树的根节点
         * @return
         */
    /**
         * 二叉树变为双向链表
         * @param last 双向链表的最后一个元素,初始为null;
         * @param tree 当前解析的左中右  的中节点 初始为树的根节点
         * @return
         */
        public static TestObject testMethod1(TestObject last, TestObject tree) {
            if (tree == null) {
                return null;
            }
            TestObject left = tree.getLeft();
            TestObject right = tree.getRight();
    
            //左边的元素已经是变化过的 左中右的  左
            if (left != null) {
                //子节点是叶子节点时 就是链表的最后一个节点
                if(left.getLeft() == null && left.getRight() == null){
                    if(last != null){
                        last.setRight(left);
                        left.setLeft(last);
                    }
                    last = left;
                } else {
                    //非叶子节点,获取节点的左边序列  leftTreeLast为左边序列的最后一个元素
                    TestObject leftTreeLast = testMethod1(last, left);
                    //最后一个节点中加入左边的节点
                    if (last != null) {
                        if (leftTreeLast != null) {
                            last.setRight(leftTreeLast);
                            leftTreeLast.setLeft(last);
                            leftTreeLast.setRight(null);
                            last = leftTreeLast;
                        }
                    } else {
                        if (leftTreeLast != null) {
                            leftTreeLast.setRight(last);
                            last = leftTreeLast;
                            last.setRight(null);
                        }
                    }
                }
            }
    
            //序列的最后一个元素直线当前节点,即左中右的  中
            if(last != null) {
                last.setRight(tree);
                //根节点的左指针指向双向链表的最后节点
                tree.setLeft(last);
                last = last.getRight();
                last.setRight(null);
            } else {
                //走到这里表示,左边没有子节点
                last = tree;
            }
    
            //序列的最后一个元素直线当前节点,即左中右的  右
            TestObject rightTreeLast = null;
            //获取右节点
            if (right != null) {
                //子节点是叶子节点时 就是链表的最后一个节点
                if(right.getLeft() == null && right.getRight() == null){
                    if(last != null){
                        last.setRight(right);
                        right.setLeft(last);
                    }
                    last = right;
                } else {
                    //非根节点,获取右边的序列
                    last = testMethod1(last, right);
                }
            }
    
            last.setRight(null);
            return last;
        }

    上面的代码还是太复杂,优化之后是:

    /**
         * 二叉树变为双向链表
         * @param last 双向链表的最后一个元素,初始为null;
         * @param tree 当前解析的左中右  的中节点 初始为树的根节点
         * @return
         */
        public static TestObject testMethod(TestObject last, TestObject tree) {
            if (tree == null) {
                return null;
            }
    
            TestObject left = tree.getLeft();
            TestObject right = tree.getRight();
    
            //子节点是叶子节点时,则设置双向链表最新的元素时该元素
            if(left == null && right == null){
                if(last != null){
                    last.setRight(tree);
                    tree.setLeft(last);
                }
                last = tree;
                return last;
            }
    
            //左中右的  左
            //获取左节点的
            if (left != null) {
                //非根节点,获取左边的序列
                last = testMethod(last, left);
            }
    
            //即左中右的  中
            //序列的最后一个元素直线当前节点,即左中右的  中
            if(last != null) {
                last.setRight(tree);
                //根节点的左指针指向双向链表的最后节点
                tree.setLeft(last);
                last = last.getRight();
                last.setRight(null);
            } else {
                //走到这里表示,左边没有子节点
                last = tree;
            }
    
            即左中右的  右
            if (right != null) {
                //非根节点,获取右边的序列
                last = testMethod(last, right);
            }
            last.setRight(null);
            return last;
        }

    接下来就可以使用测试方法了:

    package com.zhong.demo.usultestdemo.testdemo.demo_3;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    /**
     * @author yi xiangxuehai
     * @date 2021/3/30-14:28
     */
    public class TestMethod {
    
        public static void main(String[] args) {
    
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
    
            System.out.println("根节点值:");
            try {
                String value = br.readLine();
                if(!value.equals("0")) {
                    TestObject testObject = new TestObject();
                    testObject.setData(Integer.valueOf(value));
                    inputTree(testObject, br);
                    System.out.print("中序遍历 ");
                    centerScan(testObject);
                    System.out.println();
                    TestObject linked = testMethod(null, testObject);
                    System.out.print("链表 ");
                    linkedScan(linked);
                    System.out.println();
    
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    
        //输入二叉树,先中再左,再右。以0表示不需要子节点
        public static void inputTree(TestObject testObject,  BufferedReader br){
    
            try {
                    System.out.println("请输入"+ testObject.getData() +"的左节点值(0表示无):");
                    String value = br.readLine();
                    if(!value.equals("0")) {
                        TestObject left = new TestObject();
                        testObject.setLeft(left);
                        left.setData(Integer.valueOf(value));
                        inputTree(left, br);
                    }
    
                    System.out.println("请输入"+ testObject.getData() +"的右节点值(0表示无):");
                    value = br.readLine();
                    if(!value.equals("0")) {
                        TestObject right = new TestObject();
                        right.setData(Integer.valueOf(value));
                        testObject.setRight(right);
                        inputTree(right, br);
                    }
    
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    
        //中序遍历
        public static void centerScan(TestObject tree) {
            if (tree.getLeft() != null) {
                centerScan(tree.getLeft());
            }
            System.out.print(tree.getData() + " ");
    
            if (tree.getRight() != null) {
                centerScan(tree.getRight());
            }
        }
    
    //遍历链表
        public static void linkedScan(TestObject tree){
            TestObject testObject = tree;
            while(testObject.getLeft() != null){
                testObject = testObject.getLeft();
            }
    
            while (testObject != null){
                System.out.print(testObject.getData()+ " ");
                testObject = testObject.getRight();
            }
        }
    
    }
    

    测试结果如下:

    根节点值:
    5
    请输入5的左节点值:
    4
    请输入4的左节点值:
    2
    请输入2的左节点值:
    0
    请输入2的右节点值:
    0
    请输入4的右节点值:
    3
    请输入3的左节点值:
    0
    请输入3的右节点值:
    0
    请输入5的右节点值:
    6
    请输入6的左节点值:
    7
    请输入7的左节点值:
    0
    请输入7的右节点值:
    0
    请输入6的右节点值:
    0
    中序遍历:2 4 3 5 7 6 
    链表:2 4 3 5 7 6 

    展开全文
  • 双向链表的特性:元素的由他的值和链各个指针组成,左指针指向上一元素, 右指针指向下一元素 class Node(object): def __init__(self, item): self.item = item self.next = None self.prev = None class ...

    双向链表的特性:元素的由他的值和链各个指针组成,左指针指向上一元素, 右指针指向下一元素

    class Node(object):
        def __init__(self, item):
            self.item = item
            self.next = None
            self.prev = None
    
    
    class DoubleLink(object):
        def __init__(self):
            self.head = None
    
        def is_empty(self):
            return self.head == None
    
        def lenght(self):
            cur = self.head
            count = 0
            while cur != None:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历单链表"""
            if self.is_empty():
                return None
            else:
                cur = self.head
                while cur is not None:
                    cur = cur.next
    
        def add(self, item):
            """向单链表头部添加节点"""
            node = Node(item)
            if self.is_empty():
                self.head = node
            else:
                node.next = self.head
                self.head.prev = node
                self.head = node
    
        def append(self, item):
            """向单链表尾部添加节点"""
            node = Node(item)
            if self.is_empty():
                self.head = node
            else:
                cur = self.head
                while cur.next is not None:
                    cur = cur.next
                cur.next = node
                node.prev = cur
    
        def insert(self, item, pos):
            if pos >= self.lenght():
                self.append(item)
            elif pos <= 0:
                self.add(item)
            else:
                cur = self.head
                node = Node(item)
                count = 0
                while count < pos - 1:
                    count += 1
                    cur = cur.next
                node.next = cur.next
                node.prev = cur
                cur.next.prev = node
                cur.next = node
    
        def search(self, item):
            if self.is_empty():
                return None
            else:
                cur = self.head
                while cur is not None:
                    if cur.item == item:
                        return True
                    cur = cur.next
                return False
    
        def remove(self, item):
            if self.is_empty():
                return Node
            else:
                cur = self.head
                if cur.item == item:
                    if cur.next is None:
                        self.head = Node
                    else:
                        cur.next.prev = None
                        self.head = cur.next
                    return True
                while cur is not None:
                    if cur.item == item:
                        cur.prev.next = cur.next
                        cur.next.prev = cur.prev
                        break
                    cur = cur.next
    
    
    if __name__ == '__main__':
        dl = DoubleLink()
        print(dl.is_empty())
        print(dl.lenght())
        dl.add(1)
        dl.add(2)
        dl.add(3)
        dl.append(4)
        dl.append(5)
        dl.insert(6, 4)
        dl.insert(7, 5)
        dl.insert(7, 9)
        dl.insert(8, 0)
        dl.remove(8)
        dl.travel()
        print(dl.search(8))

     

    展开全文
  • java中将指针封装之后,也可以实现双向链表,创建对象时产生栈,使用内存空间 参考代码 package Test; class Link{ //存放的数据 public int data; //节点 public Link prior; //右节点 public Link next; ...

    java中将指针封装之后,也可以实现双向链表,创建对象时产生栈,使用内存空间
    参考代码

    package Test;
    
    class Link{
    	//存放的数据
    	public int data;
    	//左节点
    	public Link prior;
    	//右节点
    	public Link next;
    	
    	public Link(int data) {
    		this.data = data;
    	}
    	
    	public void print() {
    		System.out.print(data +" ");
    	}
    }
    public class test3 {
    	public Link first;
    	public Link last;
    	//初始化
    	public test3() {
    		this.first = null;
    		this.last = null;
    	}
    	public boolean isEmpty() {
    		//判断头节点是否为空
    		return first == null;
    	}
    	//插入头节点
    	public void addFirst(int data) {
    		Link link = new Link(data);
    		if(isEmpty()) {
    			last = link; 
    		}else {
    			first.prior = link;
    		}
    			link.next = first;
    			first = link;
    		
    	}
    	//插入尾节点
    	public void addLast(int data) {
    		Link link = new Link(data);
    		if(isEmpty()) {
    			first = link;
    		}else {
    			last.next = link;
    			link.prior = last;
    			last = link;
    		}
    	}
    	//定向插入
    	public boolean add(int insertData , int key) {
    		Link temp = first;
    		//对链表中的数据进行遍历
    		while(temp.data != key) {
    			temp = temp.next;
    			if(temp==null) {
    				return false;
    			}
    		}
    		Link link = new Link(insertData);
    		link.next = temp.next;
    		temp.next.prior = link;
    		link.prior = temp;
    		temp.next = link;
    		return true;
    	}
    	//删除头节点
    	public Link deleteFirst() {
    		//是否只有一个节点
    		Link temp = first;
    		if(first.next == null) {
    			last = null;
    		}else {
    			//将头节点引用置空
    			first.next.prior = null;
    		}
    		first = first.next;
    		return temp;
    		}
    	//删除尾节点
    	public Link deleteLast() {
    		//判断是否只有一个节点
    		Link temp = last;
    		if(first.next == null){
    			last = null;
    		}else {
    			last.prior.next = null;
    		}
    		last = last.prior;
    		return temp;
    	}
    	//定向删除
    	public Link deleteData(int key) {
    		Link temp = first;
    		while(temp.data != key) {
    			temp = temp.next;
    			if(temp == null) {
    				return null;
    			}
    		}
    		//删除头节点
    		temp.next.prior = temp.prior;
    		temp.prior.next = temp.next;
    		return temp;
    	}
    	public void showData() {
    		Link temp = first;
    		while(temp != null) {
    			temp.print();
    			temp = temp.next;
    			
    		}
    	}
    	public void show() {
    		Link temp = last;
    		while(temp != null) {
    			temp.print();
    			temp = temp.prior;
    		}
    	}
    	public static void main(String [] args) {
    		test3 test = new test3();
    		test.addFirst(1);
    		test.addFirst(2);
    		test.addFirst(3);
    		test.show();
    		
    	}
    }
    
    
    展开全文
  • 2-34 遍历输出异或指针双向链表 void PrintXorList(XorLinkedList A,int direction)//2-34 遍历输出异或指针双向链表 { XorPointer p,pre=NULL,q=NULL; if(direction==LEFT)p=A.Left; //从左边开始遍历 else p=A...

    一、异或指针双向链表的定义和原理

    首先值得注意的是书上的定义写错了,注意应该是struct XorNode *LRPtr,星号必不可少!

    typedef struct XorNode
    {
    	int data;
    	struct XorNode *LRPtr;
    } XorNode, *XorPointer;
    

    这是一个双向链表,常规双向链表的方案是一个结点有两个指针域,分别指向这个结点的前驱和后继。但这个题里面的链表每个结点只有一个指针域,里面存放的是这个结点L前驱的地址值A与这个结点后驱的地址值B进行异或运算后的结果,就是L->LPPtr=A ^ B,所以在访问的时候,如果要访问L的后继,就用L的前驱地址值A与L指针域里的数进行异或运算,就是A ^ (A ^ B)=B,反过来,如果要访问L的前驱,就用L后继的地址值B与L指针域里的数进行异或运算,就是B^ (A ^ B)=A,这样就实现了节省空间,用每个结点只有一个指针域实现双向链表。

    typedef struct
    {
    	XorPointer Left,Right;
    }XorLinkedList;
    

    二、2-34 遍历输出异或指针双向链表

    void PrintXorList(XorLinkedList A,int direction)//2-34 遍历输出异或指针双向链表 
    {
    	XorPointer p,pre=NULL,q=NULL;
    	if(direction==LEFT)p=A.Left;  //从左边开始遍历
    	else p=A.Right;               //从右边开始遍历
    	int count =0;
    	while(p!=NULL)                //最后一个结点输出后,最后一个结点的指针域的值和它的前驱的地址值相同,                         
    	{                             //异或结果为0,返回NULL指针,下次while判断退出循环 
    	    count++;
    		//cout<<p->data<<endl;  
    		printf("%d\n",p->data);
    		q=Xorp(pre,p->LRPtr);
    		pre=p;
    		p=q;
    	}
    }
    

    三、2-35在异或指针双向链表第i个结点前插入结点a

    Status InsertXorList(XorLinkedList &A,int i,XorPointer a)//2-35在异或指针双向链表第i个结点前插入结点a
    {                                                        //此处a结点需要提前malloc再进入函数 
    	XorPointer prev=NULL,q=NULL;
    	XorPointer p=A.Left;
    	int count=1;//用于移动计数 
    	if(i<=0) return ERROR;
    	if(p==NULL)//空表 
    	{
    		A.Left=A.Right=a;
    		a->LRPtr=NULL;
    		return OK;
    	}
    	else if(i==1)//在第一个位置加入 
    	{
    		q=Xorp(prev,p->LRPtr);
    		a->LRPtr=Xorp(prev,p);
    		p->LRPtr=Xorp(a,q);
    		A.Left=a;
    		return OK;
    	}
    	while(count<i&&p!=NULL)//移动到第i个位置,第i个位置为p 
    	{
    		q=Xorp(prev,p->LRPtr);
    		prev=p;
    		p=q;
    		count++;
    	} 
    	if(q==NULL)//在最后一个位置插入
    	{
    		if(count<i) return ERROR;//没有那么多结点,返回错误 
    		prev=NULL;
    		p=A.Right;
    		q=Xorp(prev,p->LRPtr);
    		p->LRPtr=Xorp(q,a);
    		a->LRPtr=A.Right;
    		A.Right=a;
    		return OK;
    	} 
    	else//在一般位置插入 
    	{
    		XorPointer pprev,pp; //即在prev和p之间插入a,pp是p的后继,pprev是prev的前驱 
    		pprev=Xorp(p,prev->LRPtr);
    		pp=Xorp(prev,p->LRPtr);
    		prev->LRPtr=Xorp(pprev,a);
    		p->LRPtr=Xorp(pp,a);
    		a->LRPtr=Xorp(prev,p);
    		return OK;
    	}
    	return ERROR;//上述操作均未return,则返回错误 
    }
    

    四、完整代码,供读者自行验证

    编译器:DEVC++。

    #include<iostream>
    #include<stdlib.h>
    using namespace std;
    #define Status int 
    #define ElemType int
    #define OK 1
    #define INFEASIBLE -1
    #define ERROR -1
    #define LEFT 1
    #define RIGHT 2
    typedef struct XorNode
    {
    	int data;
    	struct XorNode *LRPtr;
    } XorNode, *XorPointer;
    
    typedef struct
    {
    	XorPointer Left,Right;
    }XorLinkedList;
    
    XorPointer Xorp(XorPointer p,XorPointer q)//返回指针p和q的异或结果
    {
    	long long x,y,z;
    	x=(long long) p;
    	y=(long long) q;
    	z=x^y;
    	return (XorPointer)z;
    } 
    
    // cast from 'XorPointer {aka XorNode*}' to 'long unsigned int' loses precision [-fpermissive]
    Status InitXorLinkList(XorLinkedList &L,int number)  //生成一个链表用于调试,包含数值0-5 
    {
    	int count=1;
    	XorPointer p,q,prev;
    	for(int i=0;i<=number;i++)
    	{
    		p=(XorPointer)malloc(sizeof(XorNode));
    		p->data=i;
    		p->LRPtr=NULL;
    		if(i==0)
    		{
    			L.Left=p;
    			prev=NULL;
    			q=p;
    		}
    		else if(i!=number)
    		{
    			q->LRPtr=Xorp(prev,p);
    			prev=q;
    			q=p;
    		}
    		else if(i==number)
    		{
    			L.Right=p;
    			q->LRPtr=Xorp(prev,p);
    			p->LRPtr=Xorp(q,NULL);             //是q和NULL异或,不是prev和p异或,脑残了,调试了好久! 
    		}
    	}
    } 
    
    void PrintXorList(XorLinkedList A,int direction)//2-34 遍历输出异或指针双向链表 
    {
    	XorPointer p,pre=NULL,q=NULL;
    	if(direction==LEFT)p=A.Left;  //从左边开始遍历
    	else p=A.Right;               //从右边开始遍历
    	int count =0;
    	while(p!=NULL)                //最后一个结点输出后,最后一个结点的指针域的值和它的前驱的地址值相同,                         
    	{                             //异或结果为0,返回NULL指针,下次while判断退出循环 
    	    count++;
    		//cout<<p->data<<endl;  
    		printf("%d\n",p->data);
    		q=Xorp(pre,p->LRPtr);
    		pre=p;
    		p=q;
    	}
    }
    
    Status InsertXorList(XorLinkedList &A,int i,XorPointer a)//2-35在异或指针双向链表第i个结点前插入结点a
    {                                                        //此处a结点需要提前malloc再进入函数 
    	XorPointer prev=NULL,q=NULL;
    	XorPointer p=A.Left;
    	int count=1;//用于移动计数 
    	if(i<=0) return ERROR;
    	if(p==NULL)//空表 
    	{
    		A.Left=A.Right=a;
    		a->LRPtr=NULL;
    		return OK;
    	}
    	else if(i==1)//在第一个位置加入 
    	{
    		q=Xorp(prev,p->LRPtr);
    		a->LRPtr=Xorp(prev,p);
    		p->LRPtr=Xorp(a,q);
    		A.Left=a;
    		return OK;
    	}
    	while(count<i&&p!=NULL)//移动到第i个位置,第i个位置为p 
    	{
    		q=Xorp(prev,p->LRPtr);
    		prev=p;
    		p=q;
    		count++;
    	} 
    	if(q==NULL)//在最后一个位置插入
    	{
    		if(count<i) return ERROR;//没有那么多结点,返回错误 
    		prev=NULL;
    		p=A.Right;
    		q=Xorp(prev,p->LRPtr);
    		p->LRPtr=Xorp(q,a);
    		a->LRPtr=A.Right;
    		A.Right=a;
    		return OK;
    	} 
    	else//在一般位置插入 
    	{
    		XorPointer pprev,pp; //即在prev和p之间插入a,pp是p的后继,pprev是prev的前驱 
    		pprev=Xorp(p,prev->LRPtr);
    		pp=Xorp(prev,p->LRPtr);
    		prev->LRPtr=Xorp(pprev,a);
    		p->LRPtr=Xorp(pp,a);
    		a->LRPtr=Xorp(prev,p);
    		return OK;
    	}
    	return ERROR;//上述操作均未return,则返回错误 
    }
    int main()
    {
    	XorLinkedList A;
    	InitXorLinkList(A,5);
    	cout<<"已生成一个异或指针双向链表,共六个节点,包含数值0-5."<<endl;
    	cout<<"左端输出:"<<endl; 
    	PrintXorList( A,LEFT);
    	cout<<"右端输出:"<<endl;
    	PrintXorList( A,RIGHT);
    	XorPointer a;
    	cout<<"先执行插入操作,从左端插入"<<endl;
    	cout<<"result 结果为1则插入成功,为-1为插入失败"<<endl; 
    	while(1)
    	{
    		int i;
    		cout<<"请输入插入的位置:"<<endl;
    		cin>>i;
    		a=(XorPointer)malloc(sizeof(XorNode));
    		cout<<"请输入结点数值:"<<endl;
    		cin>>a->data;
    		int judge= InsertXorList(A,i,a);
    		cout<<"the result is "<<judge<<endl;
    		cout<<"左端输出:"<<endl; 
    		PrintXorList( A,LEFT); 
    	}	
    }
    
    展开全文
  • 双向链表

    2020-10-08 17:44:56
    双向链表 双向链表数据结构 具有前后指针的链表结构 题目链接 https://www.acwing.com/problem/content/829/ 操作分析 注意: 插入操作默认是从k的后面插入 0 和 1 是左右边界,不是具体的值 0是边界, 1 是右边...
  • 指针异或运算实战二、异或指针双向链表的实现 一、异或运算的基本知识 1. 什么是异或运算 假设二进制数10跟二进制数01进行异或运算的时候,即10 ^ 01,从右往依次进行运算,相同情况的异或结果为0,否则为1。...
  • 比如输入下图中二叉搜索树,则输出转换后的排序双向链表在二叉搜索树中,每个结点都有两个分别指向其、右子树的指针子树结点的值总是小于父结点的值,右子树结点的值总是大于父结点的值。在双向链表中,每个...
  • 题目中并没有明确说明是转化为从小到大排序的双向链表还是从大到小的双向链表,所以估摸着应该都对,这里是从小到大排序的。 定义一个全局变量,用来指向子树的最后一个结点 # -*- coding:utf-8 -*- class TreeNo
  • 二叉搜索树与双向链表//题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。//要求不能创建任何新的节点,只能调整树中结点指针的指向。比如,输入图4.15中左边的二叉搜索树,//输出转换之后的排序...
  • 26. 二叉树搜索与双向链表 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。1、思路举例说明: 二叉搜索树如上图所示,我们将其转换为配需...
  • 7.5 链表-双向链表

    2016-06-14 06:34:18
    考虑顺序表中总是可以...双向链表的结点有三个域:链接指针(llink),数据域(info),右链接指针域(rlink)。 双向链表经常采用带头结点的循环链表方式,如下图所示。(查看动画演示) 图7.10 带表头结点的
  • C++双向链表

    2017-02-07 17:03:37
    双向链表的结点有三个域:链接指针(llink),数据域(info),右链接指针域(rlink)。 双向链表经常采用带头结点的循环链表方式,如下图所示。(查看动画演示) 图7.10 带表头结点的双向循环链表
  • 题目描述:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。分析:在二叉搜索树中,根节点的子树的值都比根节点的值小,根节点的右子树的值...
  • 面试题27:二叉搜索树与双向链表 1.题目描述 输入一棵二叉搜索树,将该二又搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。比如输入下图中左边的二又搜索树,则输出转换...
  • 题目输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。思路二叉搜索树、排序链表,想到使用中序遍历。要实现双向链表,必须知道当前结点的前一...
  • 1、中序遍历,当前结点,以及左侧排好序的双向链表,再调整当前结点的指针指向最前结点/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL...
  • 题目描述输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。思路1.二叉搜索树满足子树的值<根结点的值<右子树的值,所以对二叉树进行...
  • #题目描述#思路排序链表即可以考虑到中序遍历(即子树调用递归函数,处理中间节点,右子树调用递归函数)即将当前节点... left = pre即可完成二叉搜索树变为双向链表的转换#实现class Solution { public: TreeNod...
  • 双向链表实现结点类

    2018-04-11 08:47:19
    (b)链表左插入结点insertRight(DNode* p); (c)链表右插入结点insertLeft(DNode* p); (d)删除结点DNode* deleteNode(); (e)获取左侧相邻节点地址DNode* nextNodeRight(); (f)获取右侧相邻节点的地址DNode* ...
  • 当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。 下图显示了转化后的二叉搜索树,实线表示后继关系,虚线表示前驱关系。 ...
  • 双向链表的节点来说,有本身的值域,有指向上一个节点和下一个节点的指针。在结构上,两种结构有相似性,现在有一棵搜索二叉树,请将其转换为一个有序的双向链表。 例如,节点定义为: public static class Node {...
  • 双向链表有指向上一级和下一级的两个指针。 先将链表分成中右部分。先将左边部分转换成双向链表,左边部分的最右节点与根节点进行相连,根节点的上一级也指向左边部分的最右节点。将右边部分也转换成双向链表,...
  • 输入一棵二叉搜索树,现在要将该二叉搜索树转换成一个排序的双向链表。而且在转换的过程中,不能创建任何新的结点,只能调整树中的结点指针的指向来实现。 解析: 借助二叉树中序遍历,因为中序遍历二叉搜索树的...
  • 二叉树转双向链表

    2021-03-20 13:49:54
    输入一棵二叉搜索树,将该二叉...递归将子树转换成双向链表; 将根节点尾插到子树链表的末尾; 递归将右子树转成链表; 将根节点头插到右子树链表前面。 代码实现: /** public class TreeNode { int val = 0;
  • 题目要求:将一个二叉树转化成双向链表,但是不能创建任何新的结点,只能通过调整指针来达到目的 解题思路:将二叉树的子树变成一个双向链表,并将左双向链表的尾节点和根节点双向链接;将右子树的变成双向链表,...
  • 可以将左右孩子指针作为双向循环链表的前驱和后继指针。 我们希望将这个二叉搜索树转化为双向循环链表链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点...

空空如也

空空如也

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

双向链表左指针